Java代码实现哈希表（google 公司的上机题）

也想出现在这里？点击联系我~

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 {
3. public static void main(String[] args) {
5. HashTable hashTable = new HashTable(7);
7. String key = "";
8. Scanner scanner = new Scanner(System.in);
9. while(true) {
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:退出");
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();
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;
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. }
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. }
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. }
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{
4. private EmpLinkedList[] empLinkedListArr;
5. private int size;
6. public HashTable(int size) {
7. super();
8. this.size = size;
9. empLinkedListArr = new EmpLinkedList[size];
11. for(int i = 0; i < size; i++){
12. empLinkedListArr[i] = new EmpLinkedList();
13. }
14. }
16. // 添加雇员
17. public void add(Emp emp) {
18. // 根据员工的id得到改员工应该添加到哪条链表
19. int empLinkedListNo = hashFun(emp.id);
20. // 将emp添加到对应的链表中
21. empLinkedListArr[empLinkedListNo].add(emp);
22. }
24. public void list() {
25. for (int i = 0; i < empLinkedListArr.length; i++) {
26. empLinkedListArr[i].list(i);
27. }
28. }
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. }
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. }
49. }
51. public int hashFun(int id) {
52. return id %size;
53. }
54. }

注意：不要把链表的第一个节点（头节点）删除了，不然整条链表没了。（还可以改良）

思考：如果 id 不是从低到高插入，但要求各条链表仍是从低到高，怎么解决?

到此这篇关于Java 哈希表（google 公司的上机题）的文章就介绍到这了,更多相关java哈希表内容请搜索快网idc以前的文章或继续浏览下面的相关文章希望大家以后多多支持快网idc！

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