跳到主要内容

哈希表

哈希表(HashMap)以键值对形式存储数据,通过哈希函数将 key 映射到数组下标,理想情况下提供 O(1) 的插入、查找与删除性能,是最常用的数据结构之一。

哈希函数设计原则​

一个好的哈希函数应满足三点:确定性(同一 key 必产生同一索引)、均匀性(输出尽量均匀分布到整个桶数组)与高效性(计算速度快,常使用位运算与乘法)。Java String.hashCode() 使用多项式累加 s[0]*31^(n-1) + s[1]*31^(n-2) + ...,常数 31 是奇素数,既减少碰撞又便于 JVM 优化。最终索引通过对桶数取模(或更快的按位与 n - 1)得到。

冲突处理​

不同 key 映射到同一桶的现象称为哈希冲突,常用两类策略解决。

  • 链地址法(Separate Chaining):每个桶维护一个链表(或树),冲突元素依次追加。实现简单、删除方便,但需要额外指针空间。
  • 开放寻址法(Open Addressing):冲突时按探测序列(线性探测、二次探测、双重哈希)寻找下一个空槽。空间紧凑、缓存友好,但易产生聚集,删除时需墓碑标记。

负载因子与扩容​

负载因子(load factor)定义为 size / capacity,衡量哈希表填充程度。负载因子过大会增加冲突,过小则浪费空间。Java HashMap 默认负载因子为 0.75,当元素数量超过 capacity * loadFactor 时触发扩容,容量翻倍并重新哈希(rehash)所有键,以摊销 O(1) 的成本维持性能。

Java HashMap 内部实现​

JDK 8 之后的 HashMap 采用数组 + 链表 + 红黑树的三段式结构:

  • 主体是 Node<K,V>[] table,每个桶指向一个链表头。
  • 当链表长度 ≥ 8 且数组容量 ≥ 64 时,链表转换为红黑树,将最坏情况下的查找复杂度从 O(n) 降为 O(log n)。
  • 当树节点数 ≤ 6 时,退化为链表,避免小规模数据下树结构带来的额外开销。
// 简化示意:JDK8 HashMap 的 put 流程
public V put(K key, V value) {
    int hash = key.hashCode() ^ (key.hashCode() >>> 16); // 高低位混合
    int idx = hash & (capacity - 1);                    // 等价于取模
    Node<K,V> head = table[idx];
    if (head == null) {
        table[idx] = new Node<>(hash, key, value, null);
    } else {
        // 遍历链表/树,key 存在则覆盖,否则追加
        // 长度达到 8 时调用 treeifyBin() 转为红黑树
    }
    if (++size > threshold) resize();                   // 容量翻倍 + rehash
    return value;
}

理解哈希表的关键,在于把握哈希函数、冲突处理、负载因子三者如何协同保证均摊 O(1) 的时间复杂度,以及 JDK 8 为何在长链路上引入红黑树。