哈希表（Hashtable），也称为散列表，是一种常见的数据结构，用于实现关联数组。它通过将关键字（key）映射到哈希表中的一个位置来实现快速的数据查找、插入和删除操作。哈希表通常由一个数组和一组哈希函数组成。
在哈希表中，每个关键字都经过哈希函数处理后得到一个索引值，该索引值指示了关键字在数组中的位置。理想情况下，哈希函数能够将关键字均匀地分布在数组中的不同位置，从而实现较好的性能。然而，在实际情况中，由于哈希函数的限制和数据分布的不均匀性，可能会出现哈希冲突，即多个关键字映射到了同一个位置。解决哈希冲突的方法包括链地址法（Chaining）、开放寻址法（Open Addressing）等。
注意：
要求：数组长度是 2 的 n 次方 hash % 数组长度 等价于 hash & (数组长度-1) 推荐使用求模运算替换为位运算，性能更好
1.基本框架
哈希表（HashTable）类，内部类 Entry 作为节点类。
package com.dreams.hashtable;
import com.google.common.hash.Hashing;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;
public class HashTable {
// 节点类
static class Entry {
int hash; // 哈希码
Object key; // 键
Object value; // 值
Entry next;
public Entry(int hash, Object key, Object value) {
this.hash = hash;
this.key = key;
this.value = value;
}
}
}
哈希表（HashTable）类也有自己的属性。
package com.dreams.hashtable;
import com.google.common.hash.Hashing;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;
public class HashTable {
// 摘要算法
// 散列算法
// 节点类
static class Entry {
//......
}
Entry[] table = new Entry[16];
int size = 0; // 元素个数
//哈希表的负载因子
float loadFactor = 0.75f; // 12 是16阈值
//保存阈值，不必重复计算
int threshold = (int) (loadFactor * table.length);
}
2.get方法
通过哈希码确定键值对的存储位置，然后在对应位置的链表中查找目标键。
// 根据 hash 码获取 value
Object get(int hash, Object key) {
int idx = hash & (table.length - 1);
if (table[idx] == null) {
return null;
}
Entry p = table[idx];
while (p != null) {
if (p.key.equals(key)) {
return p.value;
}
p = p.next;
}
return null;
}
3.put方法
代码：
// 向 hash 表存入新 key value，如果 key 重复，则更新 value
void put(int hash, Object key, Object value) {
int idx = hash & (table.length - 1);
if (table[idx] == null) {
// 1. idx 处有空位, 直接新增
table[idx] = new Entry(hash, key, value);
} else {
// 2. idx 处无空位, 沿链表查找 有重复key更新，否则新增
Entry p = table[idx];
while (true) {
if (p.key.equals(key)) {
p.value = value; // 更新
return;
}
if (p.next == null) {
break;
}
p = p.next;
}
p.next = new Entry(hash, key, value); // 新增
}
size++;
if (size > threshold) {
resize();
}
}代码解释：
1.根据哈希码计算出在哈希表数组中的索引 idx。
2.然后，检查哈希表数组中该索引处是否有节点。如果没有，说明该位置没有键值对，直接在该位置新增一个节点存储新的键值对。
3.如果该索引处有节点，则遍历该链表，逐个比较节点的键与目标键是否相等：
- 如果找到了相同的键，则更新对应节点的值为新值，并返回。
- 如果遍历完链表仍未找到相同的键，则在链表末尾新增一个节点存储新的键值对。
4.最后，更新哈希表的大小 size，并检查是否需要进行扩容操作。
4.扩容
哈希表的负载因子（Load Factor）是一个重要的衡量指标，它定义为哈希表中已存储的元素数量与哈希表大小的比值。当负载因子超过一定阈值时，就需要进行负载均衡操作。
n 是哈希表中已存储的元素数量。
m 是哈希表数组的长度。
负载因子超过一定阈值（通常为 0.75）时，表示哈希表已经达到了扩容的条件，需要进行负载均衡操作。
private void resize() {
//乘2相当于左乘一位
Entry[] newTable = new Entry[table.length << 1];
for (int i = 0; i < table.length; i++) {
Entry p = table[i]; // 拿到每个链表头
if (p != null) {
Entry a = null;
Entry b = null;
Entry aHead = null;
Entry bHead = null;
while (p != null) {
if ((p.hash & table.length) == 0) {
if (a != null) {
a.next = p;
} else {
aHead = p;
}
a = p; // 分配到a
} else {
if (b != null) {
b.next = p;
} else {
bHead = p;
}
b = p; // 分配到b
}
p = p.next;
}
// 规律： a 链表保持索引位置不变，b 链表索引位置+table.length
if (a != null) {
a.next = null;
newTable[i] = aHead;
}
if (b != null) {
b.next = null;
newTable[i + table.length] = bHead;
}
}
}
table = newTable;
threshold = (int) (loadFactor * table.length);
}代码解释：
1.首先，创建一个新的数组 newTable，其大小是原数组的两倍（table.length << 1）。
2.然后，遍历原数组 table 中的每个元素（每个元素是一个链表的头节点）。
3.对于每个链表头节点 p，根据其哈希值重新计算其在新数组中的位置，具体分为两组：
- 如果 (p.hash & table.length) == 0，说明 p 应该留在原来的位置不变（记为组 a）。
- 如果 (p.hash & table.length) != 0，说明 p 的位置应该在原来的基础上加上原数组的长度，即移到新数组的后半部分（记为组 b）。
4.将每个链表按照上述规则分别连接到新数组的对应位置上，并更新新数组中的链表头节点。
5.最后，更新哈希表的数组为新数组，并重新计算扩容后的阈值。
5.删除方法
代码
// 根据 hash 码删除，返回删除的 value
Object remove(int hash, Object key) {
int idx = hash & (table.length - 1);
if (table[idx] == null) {
return null;
}
Entry p = table[idx];
Entry prev = null;
while (p != null) {
if (p.key.equals(key)) {
// 找到了, 删除
if (prev == null) { // 链表头
table[idx] = p.next;
} else { // 非链表头
prev.next = p.next;
}
size--;
return p.value;
}
prev = p;
p = p.next;
}
return null;
}代码解释：
1.首先，根据哈希码计算出在哈希表数组中的索引 idx。
2.然后，检查哈希表数组中该索引处是否有节点。如果没有，说明该位置没有键值对，直接返回 null。
3.如果该索引处有节点，则遍历该链表，逐个比较节点的键与目标键是否相等：
- 如果找到了相同的键，则删除对应节点，并返回被删除的值。
- 如果未找到相同的键，则继续遍历链表。
4.如果遍历完链表仍未找到相同的键，则返回 null。
6.哈希算法
MurmurHash是一种广泛使用的非加密哈希函数。
加入依赖：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>30.1-jre</version>
</dependency>代码：
public Object get(Object key) {
int hash = hash(key);
return get(hash, key);
}
public void put(Object key, Object value) {
int hash = hash(key);
put(hash, key, value);
}
public Object remove(Object key) {
int hash = hash(key);
return remove(hash, key);
}
private static int hash(Object key) {
if (key instanceof String) {
String k = (String) key;
return Hashing.murmur3_32().hashString(k, StandardCharsets.UTF_8).asInt();
}
int hash = key.hashCode();
return hash ^ (hash >>> 16);
}
参考
