原文鏈接傳送門(mén)

哈希表(散列)-Google上機(jī)題

看一個(gè)實(shí)際需求，google公司的一個(gè)上機(jī)題:

有一個(gè)公司,當(dāng)有新的員工來(lái)報(bào)道時(shí),要求將該員工的信息加入(id,性別,年齡,住址…),當(dāng)輸入該員工的id時(shí),要求查找到該員工的 所有信息.

要求: 不使用數(shù)據(jù)庫(kù),盡量節(jié)省內(nèi)存,速度越快越好=>哈希表(散列)

散列表（Hash table，也叫哈希表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。 15 111 % 15

哈希表就是數(shù)組里面存儲(chǔ)鏈表

google公司的一個(gè)上機(jī)題:

有一個(gè)公司,當(dāng)有新的員工來(lái)報(bào)道時(shí),要求將該員工的信息加入(id,性別,年齡,名字,住址…),當(dāng)輸入該員工的id時(shí),要求查找到該員工的 所有信息.

要求:

不使用數(shù)據(jù)庫(kù),速度越快越好=>哈希表(散列) 添加時(shí)，保證按照id從低到高插入 [課后思考：如果id不是從低到高插入，但要求各條鏈表仍是從低到高，怎么解決?]

使用鏈表來(lái)實(shí)現(xiàn)哈希表, 該鏈表不帶表頭[即: 鏈表的第一個(gè)結(jié)點(diǎn)就存放雇員信息]

思路分析并畫(huà)出示意圖

代碼實(shí)現(xiàn)[增刪改查(顯示所有員工，按id查詢)]

// 哈希表之所以能夠提高效率,是因?yàn)樗軌蛲瑫r(shí)管理多個(gè)鏈表

Emp

/*** 表示一個(gè)雇員*/ class Emp{public int id;public String name;public Emp next;//next 默認(rèn)為空public Emp(int id, String name) {this.id = id;this.name = name;} }

HashTab

///創(chuàng)建hashTab 管理多條鏈表class HashTab{// 數(shù)組里面放的是鏈表private EmpLinkedList[] empLinkedListArray;//private Integer size = 7;// 構(gòu)造器public HashTab(int size) {// 初始化empLinkedListArrayempLinkedListArray = new EmpLinkedList[size];// ? 留一個(gè)坑// 這里能直接用么/** add:添加雇員list:顯示雇員exit:退出雇員add輸入idtomException in thread "main" java.util.InputMismatchExceptionat java.util.Scanner.throwFor(Scanner.java:864)at java.util.Scanner.next(Scanner.java:1485)at java.util.Scanner.nextInt(Scanner.java:2117)at java.util.Scanner.nextInt(Scanner.java:2076)at com.atguigu.hashtab.HashTabDemo.main(HashTabDemo.java:30)Process finished with exit code 1* */// 這個(gè)時(shí)候不要忘了, 分別初始化 每個(gè)鏈表for (int i = 0; i < size; i++) {// 數(shù)組中的每一個(gè)元素都需要?jiǎng)?chuàng)建一把empLinkedListArray[i] = new EmpLinkedList();}}// 添加雇員public void add(Emp emp) {// 根據(jù)員工的id,得到該員工應(yīng)當(dāng)加入到,哪條鏈表int empLinkedListNO = hashFun(emp.id);// 將emp 添加到對(duì)應(yīng)的鏈表中empLinkedListArray[empLinkedListNO].add(emp);}// 不管你是什么操作,總是要找鏈表// 遍歷所有的鏈表public void list() {// 遍歷Hash表for (int i = 0; i < size; i++) {empLinkedListArray[i].list(i);}}// 編寫(xiě)一個(gè)散列函數(shù)// 散列函數(shù)有很多種寫(xiě)法// 這里使用簡(jiǎn)單的方法-取模法public int hashFun(int id) {return id % size;}/*** 更根據(jù)輸入的id,查找雇員* @param id*/public void findEmpById(int id) {// 使用散列函數(shù)確定到哪條鏈表查找int empLinkedListNO = hashFun(id);Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);if (emp != null) {// 說(shuō)明找到了System.out.println("找到了該雇員");System.out.printf("在第%d條鏈表中找到了該雇員,id = %d",id,empLinkedListNO+1);} else {System.out.println("在哈希表中,沒(méi)有找到該雇員~");}} }

EmpLinkedList

class EmpLinkedList{// 頭指針, 執(zhí)行第一個(gè)Emp,因此我們這個(gè)鏈表的head,是直接 指向第一個(gè)Empprivate Emp head;//添加雇員到鏈表// 說(shuō)明.// 1. 假定,當(dāng)添加雇員的時(shí)候,id是自增長(zhǎng)的,即id 的分配總是從小到大public void add(Emp emp) {// 如果是添加第一個(gè)雇員if (head == null) {head = emp;return;}// 如果不是添加第一個(gè)雇員,則使用一個(gè)輔助的指針,幫助定位到最后Emp currEmp = head;while (true) {if (currEmp.next == null) {// 說(shuō)明到鏈表最后break;}// 后移currEmp = currEmp.next;}// 退出時(shí),直接將emp 加入鏈表currEmp.next = emp;}// 遍歷鏈表的雇員信息public void list(int no) {// 判斷是否為空if (head == null) {// 說(shuō)明鏈表為空System.out.println("當(dāng)前鏈"+no+"表為空!");return;}// 沒(méi)有空 // 打印信息System.out.println("當(dāng)前鏈"+no+"表的信息為");// 輔助指針Emp currEmp = head;while (true) {System.out.printf("=> id =%d name = %s\t",currEmp.id,currEmp.name);if (currEmp.next == null) {// 說(shuō)明,currEmp 已經(jīng)是最后節(jié)點(diǎn)break;}// 后移 遍歷currEmp = currEmp.next;}System.out.println();}/*** // 根據(jù)id 查找雇員* // 如果查找到 ,就返回Emp,如果沒(méi)有找打到,就返回null* @param id* @return*/public Emp findEmpById(int id) {// 判斷鏈表是否為空if (head == null) {System.out.println("鏈表為空");return null;}//輔助指針Emp curEmp = head;while (true) {//if (curEmp.id == id) {// 找到break;// 這個(gè)時(shí)候,currEmp就指向了要查找的雇員}// 退出if (curEmp.next == null) {// 說(shuō)明遍歷當(dāng)前鏈表沒(méi)有找到該雇員curEmp = null;}// 后移curEmp = curEmp.next;}return curEmp;} }

主函數(shù)

public static void main(String[] args) {// 創(chuàng)建哈希表HashTab hashTab = new HashTab(7);// 寫(xiě)一個(gè)簡(jiǎn)單的菜單來(lái)測(cè)試String key = "";Scanner scanner = new Scanner(System.in);while (true) {System.out.println("add:添加雇員");System.out.println("list:顯示雇員");System.out.println("find:查找雇員");System.out.println("exit:退出雇員");key = scanner.next();switch (key) {case "add":System.out.println("輸入id");int id = scanner.nextInt();System.out.println("輸入名字");String name = scanner.next();// 創(chuàng)建雇員Emp emp = new Emp(id, name);hashTab.add(emp);break;case "list":hashTab.list();break;case "find":System.out.println("輸入id");int findId = scanner.nextInt();hashTab.findEmpById(findId);break;case "exit":scanner.close();System.exit(0);default:break;}} } add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 add 輸入id 1 輸入名字 tom add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 add 輸入id 2 輸入名字 jack add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 add 輸入id 3 輸入名字 pin add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 add 輸入id 6 輸入名字 nanc add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 list 當(dāng)前鏈0表為空! 當(dāng)前鏈1表的信息為 => id =1 name = tom 當(dāng)前鏈2表的信息為 => id =2 name = jack 當(dāng)前鏈3表的信息為 => id =3 name = pin 當(dāng)前鏈4表為空! 當(dāng)前鏈5表為空! 當(dāng)前鏈6表的信息為 => id =6 name = nanc add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 add 輸入id 123 輸入名字 sme add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 list 當(dāng)前鏈0表為空! 當(dāng)前鏈1表的信息為 => id =1 name = tom 當(dāng)前鏈2表的信息為 => id =2 name = jack 當(dāng)前鏈3表的信息為 => id =3 name = pin 當(dāng)前鏈4表的信息為 => id =123 name = sme 當(dāng)前鏈5表為空! 當(dāng)前鏈6表的信息為 => id =6 name = nanc add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 add 輸入id 678 輸入名字 vicr add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 list 當(dāng)前鏈0表為空! 當(dāng)前鏈1表的信息為 => id =1 name = tom 當(dāng)前鏈2表的信息為 => id =2 name = jack 當(dāng)前鏈3表的信息為 => id =3 name = pin 當(dāng)前鏈4表的信息為 => id =123 name = sme 當(dāng)前鏈5表為空! 當(dāng)前鏈6表的信息為 => id =6 name = nanc => id =678 name = vicr add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 add 輸入id 389 輸入名字 wef add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 add 輸入id 9 輸入名字 zho add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 list 當(dāng)前鏈0表為空! 當(dāng)前鏈1表的信息為 => id =1 name = tom 當(dāng)前鏈2表的信息為 => id =2 name = jack => id =9 name = zho 當(dāng)前鏈3表的信息為 => id =3 name = pin 當(dāng)前鏈4表的信息為 => id =123 name = sme => id =389 name = wef 當(dāng)前鏈5表為空! 當(dāng)前鏈6表的信息為 => id =6 name = nanc => id =678 name = vicr add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 add 輸入id 34 輸入名字 mach add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 list 當(dāng)前鏈0表為空! 當(dāng)前鏈1表的信息為 => id =1 name = tom 當(dāng)前鏈2表的信息為 => id =2 name = jack => id =9 name = zho 當(dāng)前鏈3表的信息為 => id =3 name = pin 當(dāng)前鏈4表的信息為 => id =123 name = sme => id =389 name = wef 當(dāng)前鏈5表為空! 當(dāng)前鏈6表的信息為 => id =6 name = nanc => id =678 name = vicr => id =34 name = mach add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 find 輸入id 8 Exception in thread "main" java.lang.NullPointerExceptionat com.atguigu.hashtab.EmpLinkedList.findEmpById(HashTabDemo.java:237)at com.atguigu.hashtab.HashTab.findEmpById(HashTabDemo.java:128)at com.atguigu.hashtab.HashTabDemo.main(HashTabDemo.java:44)Process finished with exit code 1

最后這里置空要 加上break

if (curEmp.next == null) {// 說(shuō)明遍歷當(dāng)前鏈表沒(méi)有找到該雇員curEmp = null;break;}

這下就可以了

add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 add 輸入id 1 輸入名字 tom add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 add 輸入id 2 輸入名字 nancy add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 add4 add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 add 輸入id 4 輸入名字 victor add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 list 當(dāng)前鏈0表為空! 當(dāng)前鏈1表的信息為 => id =1 name = tom 當(dāng)前鏈2表的信息為 => id =2 name = nancy 當(dāng)前鏈3表為空! 當(dāng)前鏈4表的信息為 => id =4 name = victor 當(dāng)前鏈5表為空! 當(dāng)前鏈6表為空! add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 find 輸入id 6 鏈表為空 在哈希表中,沒(méi)有找到該雇員~ add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員 find 輸入id 4 找到了該雇員 在第4條鏈表中找到了該雇員,id = 5add:添加雇員 list:顯示雇員 find:查找雇員 exit:退出雇員

完整代碼

package com.atguigu.hashtab;import java.util.Scanner;/*** ClassName: <br/>* Description: <br/>* Date: 2021-02-24 13:10 <br/>* <br/>* @project data_algorithm* @package com.atguigu.hashtab*/ public class HashTabDemo {public static void main(String[] args) {// 創(chuàng)建哈希表HashTab hashTab = new HashTab(7);// 寫(xiě)一個(gè)簡(jiǎn)單的菜單來(lái)測(cè)試String key = "";Scanner scanner = new Scanner(System.in);while (true) {System.out.println("add:添加雇員");System.out.println("list:顯示雇員");System.out.println("find:查找雇員");System.out.println("exit:退出雇員");key = scanner.next();switch (key) {case "add":System.out.println("輸入id");int id = scanner.nextInt();System.out.println("輸入名字");String name = scanner.next();// 創(chuàng)建雇員Emp emp = new Emp(id, name);hashTab.add(emp);break;case "list":hashTab.list();break;case "find":System.out.println("輸入id");int findId = scanner.nextInt();hashTab.findEmpById(findId);break;case "exit":scanner.close();System.exit(0);default:break;}}} }///創(chuàng)建hashTab 管理多條鏈表class HashTab{// 數(shù)組里面放的是鏈表private EmpLinkedList[] empLinkedListArray;//private Integer size = 7;// 構(gòu)造器public HashTab(int size) {// 初始化empLinkedListArrayempLinkedListArray = new EmpLinkedList[size];// ? 留一個(gè)坑// 這里能直接用么/** add:添加雇員list:顯示雇員exit:退出雇員add輸入idtomException in thread "main" java.util.InputMismatchExceptionat java.util.Scanner.throwFor(Scanner.java:864)at java.util.Scanner.next(Scanner.java:1485)at java.util.Scanner.nextInt(Scanner.java:2117)at java.util.Scanner.nextInt(Scanner.java:2076)at com.atguigu.hashtab.HashTabDemo.main(HashTabDemo.java:30)Process finished with exit code 1* */// 這個(gè)時(shí)候不要忘了, 分別初始化 每個(gè)鏈表for (int i = 0; i < size; i++) {// 數(shù)組中的每一個(gè)元素都需要?jiǎng)?chuàng)建一把empLinkedListArray[i] = new EmpLinkedList();}}// 添加雇員public void add(Emp emp) {// 根據(jù)員工的id,得到該員工應(yīng)當(dāng)加入到,哪條鏈表int empLinkedListNO = hashFun(emp.id);// 將emp 添加到對(duì)應(yīng)的鏈表中empLinkedListArray[empLinkedListNO].add(emp);}// 不管你是什么操作,總是要找鏈表// 遍歷所有的鏈表public void list() {// 遍歷Hash表for (int i = 0; i < size; i++) {empLinkedListArray[i].list(i);}}// 編寫(xiě)一個(gè)散列函數(shù)// 散列函數(shù)有很多種寫(xiě)法// 這里使用簡(jiǎn)單的方法-取模法public int hashFun(int id) {return id % size;}/*** 更根據(jù)輸入的id,查找雇員* @param id*/public void findEmpById(int id) {// 使用散列函數(shù)確定到哪條鏈表查找int empLinkedListNO = hashFun(id);Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);if (emp != null) {// 說(shuō)明找到了System.out.println("找到了該雇員");System.out.printf("在第%d條鏈表中找到了該雇員,id = %d",id,empLinkedListNO+1);} else {System.out.println("在哈希表中,沒(méi)有找到該雇員~");}} }/*** 表示一個(gè)雇員*/ class Emp{public int id;public String name;public Emp next;//next 默認(rèn)為空public Emp(int id, String name) {this.id = id;this.name = name;} }class EmpLinkedList{// 頭指針, 執(zhí)行第一個(gè)Emp,因此我們這個(gè)鏈表的head,是直接 指向第一個(gè)Empprivate Emp head;//添加雇員到鏈表// 說(shuō)明.// 1. 假定,當(dāng)添加雇員的時(shí)候,id是自增長(zhǎng)的,即id 的分配總是從小到大public void add(Emp emp) {// 如果是添加第一個(gè)雇員if (head == null) {head = emp;return;}// 如果不是添加第一個(gè)雇員,則使用一個(gè)輔助的指針,幫助定位到最后Emp currEmp = head;while (true) {if (currEmp.next == null) {// 說(shuō)明到鏈表最后break;}// 后移currEmp = currEmp.next;}// 退出時(shí),直接將emp 加入鏈表currEmp.next = emp;}// 遍歷鏈表的雇員信息public void list(int no) {// 判斷是否為空if (head == null) {// 說(shuō)明鏈表為空System.out.println("當(dāng)前鏈"+no+"表為空!");return;}// 沒(méi)有空 // 打印信息System.out.println("當(dāng)前鏈"+no+"表的信息為");// 輔助指針Emp currEmp = head;while (true) {System.out.printf("=> id =%d name = %s\t",currEmp.id,currEmp.name);if (currEmp.next == null) {// 說(shuō)明,currEmp 已經(jīng)是最后節(jié)點(diǎn)break;}// 后移 遍歷currEmp = currEmp.next;}System.out.println();}/*** // 根據(jù)id 查找雇員* // 如果查找到 ,就返回Emp,如果沒(méi)有找打到,就返回null* @param id* @return*/public Emp findEmpById(int id) {// 判斷鏈表是否為空if (head == null) {System.out.println("鏈表為空");return null;}//輔助指針Emp curEmp = head;while (true) {//if (curEmp.id == id) {// 找到break;// 這個(gè)時(shí)候,currEmp就指向了要查找的雇員}// 退出if (curEmp.next == null) {// 說(shuō)明遍歷當(dāng)前鏈表沒(méi)有找到該雇員curEmp = null;break;}// 后移curEmp = curEmp.next;}return curEmp;} }

擴(kuò)展

刪除功能???

原文鏈接傳送門(mén)

總結(jié)

以上是生活随笔為你收集整理的哈希表思路图解和代码实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。