前文 哈希表核心原理 中我介绍了哈希表的核心原理和几个关键概念，其中提到了解决哈希冲突的方法主要有两种，分别是拉链法和开放寻址法（也常叫做线性探查法）：
本文就来具体介绍一下拉链法的实现原理和代码。
拉链法的简化版实现
哈希表核心原理 已经介绍过哈希函数和 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 数组的大小在创建哈希表时就固定，不考虑负载因子和动态扩缩容的问题。
简化版代码
这里直接给出简化版的代码实现，你可以先看看，后面将通过可视化面板展示增删查改的过程
import java.util.LinkedList;
// 用拉链法解决哈希冲突的简化实现
public class ExampleChainingHashMap {
// 链表节点，存储 key-value 对儿
// 注意这里必须存储同时存储 key 和 value
// 因为要通过 key 找到对应的 value
static class KVNode {
int key;
int value;
// 为了简化，我这里直接用标准库的 LinkedList 链表
// 所以这里就不添加 next 指针了
// 你当然可以给 KVNode 添加 next 指针，自己实现链表操作
public KVNode(int key, int value) {
this.key = key;
this.value = value;
}
}
// 底层 table 数组中的每个元素是一个链表
private LinkedList<KVNode>[] table;
public ExampleChainingHashMap(int capacity) {
table = new LinkedList[capacity];
}
private int hash(int key) {
return key % table.length;
}
// 查
public int get(int key) {
int index = hash(key);
if (table[index] == null) {
// 链表为空，说明 key 不存在
return -1;
}
LinkedList<KVNode> list = table[index];
// 遍历链表，尝试查找目标 key，返回对应的 value
for (KVNode node : list) {
if (node.key == key) {
return node.value;
}
}
// 链表中没有目标 key
return -1;
}
// 增/改
public void put(int key, int value) {
int index = hash(key);
if (table[index] == null) {
// 链表为空，新建一个链表，插入 key-value
table[index] = new LinkedList<>();
table[index].add(new KVNode(key, value));
return;
}
// 链表不为空，要遍历一遍看看 key 是否已经存在
// 如果存在，更新 value
// 如果不存在，插入新节点
LinkedList<KVNode> list = table[index];
for (KVNode node : list) {
if (node.key == key) {
// key 已经存在，更新 value
node.value = value;
return;
}
}
// 链表中没有目标 key，添加新节点
// 这里使用 addFirst 添加到链表头部或者 addLast 添加到链表尾部都可以
// 因为 Java LinkedList 的底层实现是双链表，头尾操作都是 O(1) 的
// https://labuladong.online/algo/data-structure-basic/linkedlist-implement/
list.addLast(new KVNode(key, value));
}
// 删
public void remove(int key) {
LinkedList<KVNode> list = table[hash(key)];
if (list == null) {
return;
}
// 如果 key 存在，则删除
// 这个 removeIf 方法是 Java LinkedList 的方法，可以删除满足条件的元素，时间复杂度 O(N)
list.removeIf(node -> node.key == key);
}
}
有了上面的铺垫，我们现在来看一个比较完善的 Java 代码实现，主要新增了以下几个功能：
1、使用了泛型，可以存储任意类型的 key 和 value。
2、底层的 table 数组会根据负载因子动态扩缩容。
3、使用了 哈希表基础 中提到的 hash 函数，利用 key 的 hashCode() 方法和 table.length 来计算哈希值。
4、实现了 keys() 方法，可以返回哈希表中所有的 key。
为了方便，我直接使用 Java 标准库的 LinkedList 作为链表，这样就不用自己手动处理增删链表节点的操作了。当然如果你愿意的话，可以参照前文 单/双链表代码实现 自己编写操作 KVNode 的逻辑。
import java.util.LinkedList;
public class MyChainingHashMap {
// 拉链法使用的单链表节点，存储 key-value 对
private static class KVNode<K, V> {
K key;
V value;
// 因为我们使用了内置的 LinkedList 类，所以不用 next 指针
// 不用我们自己实现链表的逻辑
KVNode(K key, V val) {
this.key = key;
this.value = val;
}
}
// 哈希表的底层数组，每个数组元素是一个链表，链表中每个节点是 KVNode 存储键值对
private LinkedList<KVNode<K, V>>[] table;
// 哈希表中存入的键值对个数
private int size;
// 底层数组的初始容量
private static final int INIT_CAP = 4;
public MyChainingHashMap() {
this(INIT_CAP);
}
public MyChainingHashMap(int initCapacity) {
size = 0;
// 初始化哈希表
table = (LinkedList<KVNode<K, V>>[]) new LinkedList[initCapacity];
for (int i = 0; i < table.length; i++) {
table[i] = new LinkedList<>();
}
}
/***** 增/改 *****/
// 添加 key -> val 键值对
// 如果键 key 已存在，则将值修改为 val
public void put(K key, V val) {
if (key == null) {
throw new IllegalArgumentException("key is null");
}
LinkedList<KVNode<K, V>> list = table[hash(key)];
// 如果 key 之前存在，则修改对应的 val
for (KVNode<K, V> node : list) {
if (node.key.equals(key)) {
node.value = val;
return;
}
}
// 如果 key 之前不存在，则插入，size 增加
list.add(new KVNode<>(key, val));
size++;
// 如果元素数量超过了负载因子，进行扩容2N
if (size >= table.length * 0.75) {
resize(table.length * 2);
}
}
/***** 删 *****/
// 删除 key 和对应的 val
public void remove(K key) {
if (key == null) {
throw new IllegalArgumentException("key is null");
}
LinkedList<KVNode<K, V>> list = table[hash(key)];
// 如果 key 存在，则删除，size 减少
for (KVNode<K, V> node : list) {
if (node.key.equals(key)) {
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);
System.out.println(map.get(2)); // null
System.out.println(map.keys()); // [1, 3]（顺序可能不同）
}
}
