哈希表的核心在于哈希函数设计和冲突处理策略。理解链地址法、开放地址法和负载因子的关系，是掌握 HashMap/HashSet 底层原理的关键。
一、哈希函数设计
Mermaid · 渲染中（下方为源码）
graph LR A[键] --> B[哈希函数] B --> C[桶下标] C --> D[冲突? 链地址/开放地址]
好的哈希函数应满足：
- 均匀性：输出均匀分布在桶中
- 确定性：相同输入 → 相同输出
- 高效性：计算快
常见哈希方法
// 1. 除留余数法
int hash = key % tableSize; // tableSize 取质数
// 2. 乘法哈希
int hash = (int)((key * 0.6180339887) % 1 * tableSize);
// 3. Java String.hashCode()
int hash = 0;
for (char c : s.toCharArray()) {
hash = 31 * hash + c; // 31 是质数，且 31*i == (i<<5)-i
}
// 4. Java HashMap 的扰动函数
static int hash(Object key) {
int h = key.hashCode();
return h ^ (h >>> 16); // 高 16 位异或低 16 位
}二、冲突处理
链地址法（Separate Chaining）
每个桶是一个链表（Java 8+ 超过 8 个转红黑树）：
class HashMap<K, V> {
Node<K,V>[] table; // 桶数组
void put(K key, V value) {
int idx = hash(key) & (table.length - 1);
Node<K,V> node = table[idx];
while (node != null) {
if (node.key.equals(key)) { node.value = value; return; }
node = node.next;
}
table[idx] = new Node<>(key, value, table[idx]); // 头插
}
}