哈希表原理与冲突解决

一、哈希表概述

1.1 核心思想

哈希表通过哈希函数将键映射到数组索引，实现平均 ( O(1) ) 的查找、插入和删除。

键(key) → 哈希函数 → 索引(index) → 数组存储

1.2 理想情况

[ \text{index} = hash(key) % \text{array.length} ]

二、哈希函数

2.1 好的哈希函数标准

1. 确定性：相同输入得到相同输出
2. 均匀性：输出均匀分布，减少冲突
3. 高效性：计算速度快

2.2 Java String的hashCode

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + value[i];  // 31是质数，可被优化为位运算
        }
        hash = h;
    }
    return h;
}

2.3 哈希值转索引

// Java 8之前
index = (hashCode) % table.length;

// Java 8优化：位运算替代取模（要求容量为2的幂）
index = (table.length - 1) & hash;

三、哈希冲突

3.1 什么是冲突

不同键通过哈希函数得到相同索引：
[ hash(k_1) % m = hash(k_2) % m ]

3.2 冲突解决方法

链地址法(Separate Chaining)

每个桶是一个链表，冲突元素链入链表。

索引:  [0]      [1]      [2]
      +----+   +----+   +----+
      |    |   | A  |-->| A' |-->null
      |    |   +----+   +----+
      |    |
      +----+

优点：

• 实现简单
• 容量可以无限增长

缺点：

• 冲突严重时退化为链表 ( O(n) )

开放寻址法(Open Addressing)

冲突时探测下一个可用位置。

线性探测：
[ h(k, i) = (hash(k) + i) % m ]

二次探测：
[ h(k, i) = (hash(k) + c_1 i + c_2 i^2) % m ]

双重哈希：
[ h(k, i) = (hash_1(k) + i \cdot hash_2(k)) % m ]

优点：

• 缓存友好（数据连续）

缺点：

• 删除复杂（需要标记删除）
• 聚集问题

四、Java HashMap实现

4.1 核心字段

transient Node<K,V>[] table;     // 哈希桶数组
transient int size;               // 键值对数量
int threshold;                    // 扩容阈值 = capacity * loadFactor
final float loadFactor;           // 负载因子，默认0.75

4.2 节点结构

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;  // 链表指针
}

4.3 put方法流程

1. 计算key的hash值
2. 定位桶位置：(n - 1) & hash
3. 桶为空：直接插入
4. 桶非空：遍历链表/红黑树
   • key已存在：覆盖value
   • key不存在：尾插法插入
5. 检查是否需要扩容

4.4 扩容机制

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        newCap = oldCap << 1;  // 容量翻倍
        newThr = oldThr << 1;  // 阈值翻倍
    }
    
    // 迁移数据：重新计算索引或保持原索引/原索引+oldCap
}

扩容优化：

• 容量为2的幂，新索引只可能是原索引或原索引+oldCap
• 通过(hash & oldCap) == 0判断

4.5 链表转红黑树

static final int TREEIFY_THRESHOLD = 8;   // 链表长度≥8转红黑树
static final int UNTREEIFY_THRESHOLD = 6; // 树节点≤6转链表

转换条件：

1. 链表长度 ≥ 8
2. 数组长度 ≥ 64（否则优先扩容）

五、负载因子(Load Factor)

5.1 定义

[ \text{负载因子} = \frac{\text{元素个数}}{\text{桶数量}} ]

5.2 默认值0.75的含义

• 空间与时间的平衡
• 过高：冲突增加，查询变慢
• 过低：空间浪费

5.3 调整策略

• 内存敏感：降低负载因子
• 速度敏感：保持或适当提高

六、ConcurrentHashMap

6.1 JDK 1.7 - 分段锁

Segment[16]
  ├── HashEntry[]
  └── HashEntry[]

6.2 JDK 1.8 - CAS + synchronized

transient volatile Node<K,V>[] table;

final V putVal(K key, V value, boolean onlyIfAbsent) {
    // 使用CAS初始化或synchronized锁住头节点
}

锁粒度：只锁链表/红黑树的头节点。

七、总结

特性	HashMap	Hashtable	ConcurrentHashMap
线程安全	否	是(synchronized)	是(CAS+锁)
允许null	key/value	否	否
扩容	2倍	2倍+1	2倍
遍历	fail-fast	fail-fast	弱一致性

哈希表的设计精髓在于哈希函数与冲突处理的平衡。理解HashMap的实现细节，对编写高效代码和排查问题都有重要帮助。