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

1) 看一個實際需求，google 公司的一個上機題:
2) 有一個公司,當有新的員工來報道時,要求將該員工的信息加入(id,性別,年齡,住址..),當輸入該員工的 id 時,要求查
找到該員工的 所有信息.
3) 要求: 不使用數據庫,盡量節省內存,速度越快越好=>哈希表(散列)

2 哈希表的基本介紹

散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通
過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組
叫做散列表。

3. google 公司的一個上機題:

有一個公司,當有新的員工來報道時,要求將該員工的信息加入(id,性別,年齡,名字,住址..),當輸入該員工的 id 時,
要求查找到該員工的 所有信息.
要求:
　　1) 不使用數據庫,,速度越快越好=>哈希表(散列)
　　2) 添加時，保證按照 id 從低到高插入
　　3) 使用鏈表來實現哈希表, 該鏈表不帶表頭[即: 鏈表的第一個結點就存放雇員信息]
　　4) 思路分析并畫出示意圖

　　5) 代碼實現

1. public class HashTableDemo {
2.  
3. public static void main(String[] args) {
4.  
5. HashTable hashTable = new HashTable(7);
6.  
7. String key = "";
8. Scanner scanner = new Scanner(System.in);
9. while(true) {
10.  
11. System.out.println("add:添加雇員");
12. System.out.println("list:查看雇員");
13. System.out.println("find:查找雇員");
14. System.out.println("del:刪除雇員");
15. System.out.println("exit:退出");
16.  
17. key = scanner.next();
18. switch (key) {
19. case "add":
20. System.out.println("請輸入id：");
21. int id = scanner.nextInt();
22. System.out.println("請輸入名字:");
23. String name = scanner.next();
24.  
25. Emp emp = new Emp(id, name);
26. hashTable.add(emp);
27. break;
28. case "list":
29. hashTable.list();
30. break;
31. case "find":
32. System.out.println("請輸入id:");
33. int id2 = scanner.nextInt();
34. hashTable.findEmpById(id2);
35. break;
36. case "del":
37. System.out.println("請輸入id:");
38. int id3 = scanner.nextInt();
39. hashTable.del(id3);
40. break;
41. case "exit":
42. System.exit(10);
43. default:
44. break;
45. }
46. }
47. }
48. }

1. // emp
2. class Emp{
3. public int id;
4. public String name;
5. public Emp next;
6. public Emp(int id, String name) {
7. super();
8. this.id = id;
9. this.name = name;
10. }
11. }

1. // EmpLinkedList
2. class EmpLinkedList{
3. // 頭指針，執行第一個Emp，因此我們這個鏈表的head，是直接指向第一個Emp
4. private Emp head;
5.  
6. // id是自增長的
7. public void add(Emp emp) {
8. // 如果是添加一個雇員
9. if(head == null) {
10. head = emp;
11. return;
12. }
13. // 如果不是第一個
14. Emp curEmp = head;
15. while(true) {
16. if(curEmp.next == null) {
17. break;
18. }
19. curEmp = curEmp.next;
20. }
21. curEmp.next = emp;
22. }
23.  
24. public void list(int no) {
25. if(head == null) {
26. System.out.println("第" + (no+1) + "條鏈表為空！");
27. return;
28. }
29. System.out.println("第" + (no+1) + "條鏈表信息為：");
30. Emp curEmp = head;
31. while(true) {
32. System.out.printf("=> id=%d name=%s\t",curEmp.id,curEmp.name);
33. if(curEmp.next == null) {
34. break;
35. }
36. curEmp = curEmp.next;
37. }
38. System.out.println();
39. }
40.  
41. // 根據id查找雇員
42. public Emp findEmpByid(int id) {
43. if(head == null) {
44. System.out.println("鏈表為空");
45. return null;
46. }
47. Emp curEmp = head;
48. while(true) {
49. if(curEmp.id == id) {
50. break;
51. }
52. if(curEmp.next == null) {
53. System.out.println("遍歷完了，沒有找到！");
54. curEmp = null;
55. break;
56. }
57. curEmp = curEmp.next;
58. }
59. return curEmp;
60. }
61.  
62. // 根據id進行刪除
63. public boolean del(int id) {
64. boolean flag = false;
65. if(head == null) {
66. System.out.println("當前鏈表為空！");
67. return flag;
68. }
69. if(head.id == id) {
70. head = null;
71. flag = true;
72. return flag;
73. }
74. Emp curEmp = head;
75. while(true) {
76. // 找到了改雇員
77. if(curEmp.next.id == id) {
78. curEmp.next = curEmp.next.next;
79. curEmp.next = null;
80. return (flag == false);
81. }
82. // 沒有找到
83. if(curEmp.next == null) {
84. System.out.println("沒有找改雇員！");
85. curEmp = null;
86. return flag;
87. }
88. curEmp = curEmp.next;
89. }
90. }
91. }

1. // 哈希表
2. class HashTable{
3.  
4. private EmpLinkedList[] empLinkedListArr;
5. private int size;
6. public HashTable(int size) {
7. super();
8. this.size = size;
9. empLinkedListArr = new EmpLinkedList[size];
10.  
11. for(int i = 0; i < size; i++){
12. empLinkedListArr[i] = new EmpLinkedList();
13. }
14. }
15.  
16. // 添加雇員
17. public void add(Emp emp) {
18. // 根據員工的id得到改員工應該添加到哪條鏈表
19. int empLinkedListNo = hashFun(emp.id);
20. // 將emp添加到對應的鏈表中
21. empLinkedListArr[empLinkedListNo].add(emp);
22. }
23.  
24. public void list() {
25. for (int i = 0; i < empLinkedListArr.length; i++) {
26. empLinkedListArr[i].list(i);
27. }
28. }
29.  
30. public void findEmpById(int id) {
31. int empLinkedListNo = hashFun(id);
32. Emp emp = empLinkedListArr[empLinkedListNo].findEmpByid(id);
33. if(emp != null) {
34. System.out.println("在第" + (empLinkedListNo+1) + "條鏈表中找到id = " + id + "雇員");
35. } else {
36. System.out.println("在哈希表中沒有找到");
37. }
38. }
39.  
40. public void del(int id) {
41. int empLinkedListNo = hashFun(id);
42. boolean flag = empLinkedListArr[empLinkedListNo].del(id);
43. if(flag == true) {
44. System.out.println("在第" + (empLinkedListNo+1) + "條鏈表中刪除了id = " + id + "雇員");
45. } else {
46. System.out.println("在哈希表中沒有找到");
47. }
48.  
49. }
50.  
51. public int hashFun(int id) {
52. return id %size;
53. }
54. }

注意：不要把鏈表的第一個節點（頭節點）刪除了，不然整條鏈表沒了。（還可以改良）

思考：如果 id 不是從低到高插入，但要求各條鏈表仍是從低到高，怎么解決?

到此這篇關于Java 哈希表（google 公司的上機題）的文章就介紹到這了,更多相關java哈希表內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！

原文鏈接：https://www.cnblogs.com/linzm14/archive/2021/03/07/14495883.html