数据结构–哈希表（Java）
博客说明
文章所涉及的资料来自互联网整理和个人总结，意在于个人学习和经验汇总，如有什么地方侵权，请联系本人删除，谢谢！
介绍
哈希表底层是数组加链表或者是数组加二叉树，一个数组里面有多个链表，通过散列函数来提高效率
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
| package cn.guizimo.hashtab;
import java.util.Scanner;
public class HashTabDemo {
public static void main(String[] args) {
HashTab hashTab = new HashTab(7);
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();
Emp emp = new Emp(id, name);
hashTab.add(emp);
break;
case "list":
hashTab.list();
break;
case "find":
System.out.println("请输入id");
id = scanner.nextInt();
hashTab.find(id);
break;
case "exit":
scanner.close();
System.exit(0);
default:
break;
}
}
}
}
class Emp{
public int id;
public String name;
public Emp next;
public Emp(int id, String name) {
super();
this.id = id;
this.name = name;
}
}
class HashTab{
private EmpLinkedList[] empLinkedListArray;
private int size;
public HashTab(int size){
this.size = size;
empLinkedListArray = new EmpLinkedList[size];
for (int i = 0; i < size; i++) {
empLinkedListArray[i] = new EmpLinkedList();
}
}
public void add(Emp emp){
int empLinkedListNo = hashFun(emp.id);
empLinkedListArray[empLinkedListNo].add(emp);
}
public void find(int id){
int empLinkedListNo = hashFun(id);
Emp emp = empLinkedListArray[empLinkedListNo].find(id);
if (emp != null){
System.out.printf("在第%d条链表中找到id=%d\n",(empLinkedListNo+1),id);
}else {
System.out.println("没有找到");
}
}
public void list(){
for (int i = 0; i < size; i++) {
empLinkedListArray[i].list(i);
}
}
public int hashFun(int id){
return id % size;
}
}
class EmpLinkedList{
private Emp head;
public void add(Emp emp){
if(head == null){
head = emp;
return;
}
Emp curEmp = head;
while (true){
if(curEmp.next == null){
break;
}
curEmp = curEmp.next;
}
curEmp.next = emp;
}
public void list(int no){
if(head == null){
System.out.println("第"+(no+1)+"条链表为空");
return;
}
System.out.print("第"+(no+1)+"条链表信息");
Emp curemp = head;
while (true){
System.out.printf("id=%d,name=%s\t",curemp.id,curemp.name);
if(curemp.next == null){
break;
}
curemp = curemp.next;
}
System.out.println();
}
public Emp find(int id){
if(head == null){
System.out.println("链表为空");
return null;
}
Emp curEmp = head;
while (true){
if(curEmp.id == id){
break;
}
if(curEmp.next == null){
curEmp = null;
break;
}
curEmp = curEmp.next;
}
return curEmp;
}
}
|
感谢
尚硅谷
万能的网络
以及勤劳的自己
