Java：关于哈希表

Java 中关于哈希表（HashMap / Hashtable）的全面讲解

Java 中最常用的哈希表实现就是 HashMap（JDK 1.8 及以后）和 Hashtable。下面从原理、源码、优化、区别等方面系统说明（以 JDK 1.8+ 为主，结合最新知识）。

1. 哈希表核心概念

哈希表（Hash Table）通过哈希函数将 Key 映射到数组索引，实现平均 O(1) 的增删改查。

• 解决哈希冲突：Java 使用链地址法（每个桶是一个链表/红黑树）。
• 负载因子（loadFactor）：默认 0.75。当 size > capacity × 0.75 时触发扩容。

2. HashMap 底层数据结构（JDK 1.8+）

数组 + 链表 + 红黑树（数组称为“哈希桶” Node[] table）。

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

• 当单个桶链表长度 ≥ 8 且 table.length ≥ 64 时，链表转为红黑树（TreeNode）。
• 红黑树节点数 ≤ 6 时退回链表（避免频繁转换）。

为什么阈值是 8？

• 泊松分布下，正常 hash 时单个桶有 8 个元素的概率 < 千万分之一。
• 链表长度 8 时，查询 O(n) 已明显变慢；红黑树查询 O(log n)（log₂8=3），收益超过树结构开销。
• 阈值设为 6（而非 7）是为了留出缓冲区，避免在 7~8 附近反复树化/退化。

重要常量（JDK 1.8+）：

• DEFAULT_INITIAL_CAPACITY = 16（必须是 2 的幂）
• DEFAULT_LOAD_FACTOR = 0.75f
• TREEIFY_THRESHOLD = 8
• UNTREEIFY_THRESHOLD = 6
• MIN_TREEIFY_CAPACITY = 64

3. 哈希函数（扰动函数）—— 减少冲突的关键

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 先取 key.hashCode()（32 位）。
• 高 16 位与低 16 位异或（让高位也参与索引计算）。
• 定位索引：(n - 1) & hash（n=table.length，位运算代替 %，更快）。

这比 JDK 1.7 的多次移位异或更简洁高效。

4. put 操作完整流程（核心源码逻辑）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;           // 1. 初始化或扩容

    if ((p = tab[i = (n - 1) & hash]) == null) // 2. 桶为空，直接插入
        tab[i] = newNode(hash, key, value, null);
    else {
        // 3. 冲突处理
        if (p.hash == hash && (p.key == key || key.equals(p.key))) // key 已存在
            // 覆盖 value
        else if (p instanceof TreeNode)          // 红黑树
            ((TreeNode)p).putTreeVal(...);
        else {                                   // 链表
            int binCount = 0;
            for (...) {
                if (p.next == null) {
                    p.next = newNode(...);       // 尾插
                    if (binCount >= 7)           // ≥8 转树
                        treeifyBin(tab, hash);
                    break;
                }
                if (key 重复) break;
                p = p.next;
                binCount++;
            }
        }
    }
    if (++size > threshold) resize();            // 4. 扩容检查
}

5. 扩容机制（resize）—— JDK 1.8 最大优化

• 容量翻倍（newCap = oldCap << 1）。
• 无需重新计算 hash：根据 hash & oldCap 判断原位置还是原位置+oldCap。
• 链表被拆成两条（低位链表 + 高位链表），效率远高于 JDK 1.7 的全部 rehash。
• 红黑树在扩容时也会 split，可能退化回链表。

6. get 操作（类似 put，极简）

1. 计算 hash → 定位桶。
2. 桶头节点匹配 → 直接返回。
3. 是红黑树 → 树查找 O(log n)。
4. 是链表 → 遍历 O(n)（最坏）。

7. HashMap vs Hashtable 区别（面试高频）

维度	HashMap	Hashtable
线程安全	非线程安全	线程安全（所有方法加 synchronized）
Null 值	key/value 都可为 null	key/value 都不允许 null
初始容量	16（2 的幂）	11
扩容	翻倍（×2）	翻倍 +1（old×2 + 1）
哈希计算	(n-1) & hash	(hash & 0x7FFFFFFF) % length
迭代器	fail-fast（快速失败）	不 fail-fast
性能	高（无锁）	低（全表锁）
继承	AbstractMap，实现 Map	继承 Dictionary，实现 Map
推荐使用	日常开发（多线程用 ConcurrentHashMap）	极少使用（遗留类）

多线程推荐：ConcurrentHashMap（JDK 1.8 后用 CAS + synchronized，锁粒度更细，性能远超 Hashtable）。

8. 使用建议 & 常见坑

• 初始化：已知容量时用 new HashMap<>(initialCapacity)，避免频繁扩容。
• 负载因子：默认 0.75 最好，不要随意改。
• Key 类型：重写 hashCode() 和 equals() 必须同时重写，且满足一致性。
• 避免攻击：恶意构造相同 hash 的 key 会导致链表极长（DoS），JDK 1.8 红黑树已缓解。
• 遍历：用 entrySet() 最快，避免 keySet() 二次查找。

9. 手写简易 HashMap（理解原理）

如果你想练习，可以自己实现一个数组+链表版本（不含红黑树），核心就是上面 putVal 的逻辑。

想看完整源码注释版或JDK 1.7 vs 1.8 详细对比图，或者想让我画一个 HashMap put/resize 的流程图？随时告诉我！

这套知识点覆盖了几乎所有 Java 面试中关于“哈希表”的问题，掌握后可以自信应对字节、阿里、腾讯等大厂。有什么具体想深入的部分（比如红黑树 split 代码、TreeNode 结构）再问我～