数据结构之哈希表的介绍和代码实现
1 哈希表
1.1 介绍
- 哈希表（Hash Table）：也称为散列表，是根据key-value而直接进行访问的数据结构。通过key值快速映射到表中的一个位置来访问记录，以加快查找的速度。用来映射函数叫做散列函数，存放记录的数组叫做散列表
1.2 应用场景
1.3 实现思路
- Hash表的实现思路和HashMap的底层相似
- 通过数组 + 链表的形式来实现
- 数组来存放链表，在添加一个数据的时候，通过散列函数对key进行一定的计算，确定数据的分区，然后在该分区以链表的形式添加数据
1.4 代码
- 下面的代码只是简单的实现HashTable的添加数据 和 查找数据功能，还有很多细节没有写。例如重复的key名如何处理，修改数据，和删除数据等功能没有实现
- （1）代码实现
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
156
157
158
159
160public class HashTable {
//子类 -- 链表结点
private class Node {
String key; //关键词
Object value; //数据
Node next; //下一个节点
public Node(String key, Object value) {
this.key = key;
this.value = value;
}
public String toString() {
return '{' + key + ':' + value + '}';
}
}
//---------------------------------------------------------------------
//子类 -- 单链表
private class LinkedList{
Node headNode; //头结点
/**
* 添加数据（尾插法）
* @param key 关键词
* @param data 数据
*/
public void add(String key, Object data) {
Node node = new Node(key, data);
//头结点没有数据，直接赋值给头结点
if (headNode == null) {
headNode = node;
return;
}
Node temp = headNode;
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}
/**
* 通过关键词获取数据
* @param key 关键词
* @return Object
*/
public Object get(String key) {
//头结点为null，链表没数据
if (headNode == null) {
System.out.println("该数据不存在!");
return null;
}
//遍历链表，寻找与key相同的数据
Node temp = headNode;
while (temp != null) {
if (temp.key.equals(key)) {
return temp.value;
}
temp = temp.next;
}
//循环退出，即找不到相同的key
System.out.println("该数据不存在!");
return null;
}
/**
* 打印链表
*/
public void print() {
if (headNode == null) {
return;
}
Node temp = headNode;
while (temp != null) {
System.out.print(temp + " ");
temp = temp.next;
}
}
}
//---------------------------------------------------------------------
private int size; //数组长度
private LinkedList[] linkedList; //链表数组
public HashTable() {
this(5); //默认数组长度为5
}
public HashTable(int size) {
this.size = size;
linkedList = new LinkedList[size];
}
/**
* 添加数据
* @param key 关键词
* @param data 数据
*/
public void add(String key, Object data) {
//通过散列函数分配数组index
int index = hashFun(key);
//链表为空，就先创建一个链表
if (linkedList[index] == null) {
linkedList[index] = new LinkedList();
}
linkedList[index].add(key, data);
}
/**
* 通过关键词获取数据
* @param key 关键词
* @return Object
*/
public Object get(String key) {
//通过散列函数分配数组index
int index = hashFun(key);
//链表为空，一定不存在数据
if (linkedList[index] == null) {
System.out.println("数据不存在！");
return null;
}
return linkedList[index].get(key);
}
/**
* 打印数据
*/
public void print() {
//遍历数组打印链表
for (LinkedList list : linkedList) {
if (list != null) {
list.print();
}
}
System.out.println();
}
/**
* 散列函数
* @param key 关键词
* @return int
*/
private int hashFun(String key) {
//每个类会有一个与之对应的hashCode
int code = key.hashCode();
//取模，是最简单的散列函数
return code % size;
}
}
- （2）测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void hashTableTest() {
//创建哈希表，并添加数据
HashTable hashTable = new HashTable();
hashTable.add("id", 1);
hashTable.add("name", "C酱");
hashTable.add("age", 18);
hashTable.add("sex", "女");
hashTable.print();
//通过关键词获取数据
Object sex = hashTable.get("sex");
System.out.println(sex);
}
