前文 哈希表核心原理 中我介绍了哈希表的核心原理和几个关键概念，其中提到了解决哈希冲突的方法主要有两种，分别是拉链法和开放寻址法（也常叫做线性探查法）：
本文就来具体介绍一下拉链法的实现原理和代码。
拉链法的简化版实现
哈希表核心原理 已经介绍过哈希函数和 key 的类型的关系，其中 hash 函数的作用是在 O(1)O(1) 的时间把 key 转化成数组的索引，而 key 可以是任意不可变的类型。
但是这里为了方便诸位理解，我先做如下简化：
1、我们实现的哈希表只支持 key 类型为 int，value 类型为 int 的情况，如果 key 不存在，就返回 -1。
2、我们实现的 hash 函数就是简单地取模，即 hash(key) = key % table.length。这样也方便模拟出哈希冲突的情况，比如当 table.length = 10 时，hash(1) 和 hash(11) 的值都是 1。
3、底层的 table 数组的大小在创建哈希表时就固定，不考虑负载因子和动态扩缩容的问题。
简化版代码
这里直接给出简化版的代码实现，你可以先看看，后面将通过可视化面板展示增删查改的过程
有了上面的铺垫，我们现在来看一个比较完善的 Java 代码实现，主要新增了以下几个功能：
1、使用了泛型，可以存储任意类型的 key 和 value。
2、底层的 table 数组会根据负载因子动态扩缩容。
3、使用了 哈希表基础 中提到的 hash 函数，利用 key 的 hashCode() 方法和 table.length 来计算哈希值。
4、实现了 keys() 方法，可以返回哈希表中所有的 key。
为了方便，我直接使用 Java 标准库的 LinkedList 作为链表，这样就不用自己手动处理增删链表节点的操作了。当然如果你愿意的话，可以参照前文 单/双链表代码实现 自己编写操作 KVNode 的逻辑。
Java
运行代码
复制代码
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
import java.util.LinkedList;
list.remove(node);
size--;
// 缩容，当负载因子小于 0.125 时，缩容
if (size <= table.length / 8) {
resize(table.length / 4);
}
return;
}
}
}
/***** 查 *****/
// 返回 key 对应的 val，如果 key 不存在，则返回 null
public V get(K key) {
if (key == null) {
throw new IllegalArgumentException("key is null");
}
LinkedList<KVNode<K, V>> list = table[hash(key)];
for (KVNode<K, V> node : list) {
if (node.key.equals(key)) {
return node.value;
}
}
return null;
}
// 返回所有 key
public List<K> keys() {
List<K> keys = new LinkedList<>();
for (LinkedList<KVNode<K, V>> list : table) {
for (KVNode<K, V> node : list) {
keys.add(node.key);
}
}
return keys;
}
/***** 其他工具函数 *****/
public int size() {
return size;
}
// 哈希函数，将键映射到 table 的索引
private int hash(K key) {
return (key.hashCode() & 0x7fffffff) % table.length;
}
private void resize(int newCap) {
// 构造一个更大容量的 HashMap
MyChainingHashMap<K, V> newMap = new MyChainingHashMap<>(newCap);
// 穷举当前 HashMap 中的所有键值对
for (LinkedList<KVNode<K, V>> list : table) {
for (KVNode<K, V> node : list) {
// 将键值对转移到新的 HashMap 中
newMap.put(node.key, node.value);
}
}
// 将当前 HashMap 的底层 table 换掉
this.table = newMap.table;
}
public static void main(String[] args) {
MyChainingHashMap<Integer, Integer> map = new MyChainingHashMap<>();
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
System.out.println(map.get(1)); // 1
System.out.println(map.get(2)); // 2
map.put(1, 100);
System.out.println(map.get(1)); // 100
map.remove(2);
