HashMap 基于 hashing 原理，我们通过 put() 和 get() 方法储存和获取对象。当我们将键值对传递给 put() 方法时，它调用键对象的 hashCode() 方法来计算 hashcode，让后找到 bucket 位置来储存值对象。当获取对象时，通过键对象的 equals() 方法找到正确的键值对，然后返回值对象。HashMap 使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap 在每个链表节点中储存键值对对象。

以上是哈希表的通用原理，但 JDK8 的 HashMap 远不止”数组+链表”这么简单。下面按结构、put 流程、扩容、线程安全四个层面拆透。

结构：数组 + 链表 + 红黑树

JDK8 中 HashMap 的桶（bucket）里挂的节点有两种形态：

  • 链表：冲突少时的默认形态，查找 O(n)
  • 红黑树：当链表长度 ≥ 8 且数组长度 ≥ 64 时树化，查找退化为 O(logN)

树化阈值 8 不是拍脑袋：泊松分布下链表长度达到 8 的概率约千万分之六，所以树化是”极端冲突的保险”，正常情况几乎不触发；而数组不足 64 时优先扩容而非树化，因为扩容能直接降低冲突率。

put 流程拆解

  1. 对 key 的 hashCode 做扰动：(h = key.hashCode()) ^ (h >>> 16)，让高 16 位参与运算，减少低位碰撞
  2. 用 (n - 1) & hash 定位桶下标（这就是容量必须为 2 的幂的原因：与运算代替取模，更快）
  3. 桶空则直接放新节点；不空则按 equals 逐个比较：命中则覆盖旧值，未命中则尾插到链表或插入红黑树
  4. 插入后 ++size > threshold（capacity × loadFactor，默认 0.75）则扩容

get 流程对称：定位桶 → 比较首节点 → 遍历链表或走树查找。

扩容：resize 的细节

扩容为 2 倍容量后，每个节点的新下标要么不变、要么是”原下标 + 旧容量”——取决于 hash 新增的那一个 bit 是 0 还是 1。JDK8 利用这一点避免重新计算所有 hash，只需一次与运算判断高位，把链表拆成 lo/hi 两条链各自搬迁。

负载因子 0.75 是空间与时间的折中：太小浪费内存且频繁扩容，太大冲突率上升。除非有明确依据，不要改它。

手写一个最小哈希表

理解原理最直接的方式是自己实现核心逻辑：

class MyHashMap<K, V> {
    private Node<K, V>[] table = new Node[16];
    private int size = 0;

    static class Node<K, V> {
        K key; V value; Node<K, V> next;
        Node(K k, V v, Node<K, V> n) { key = k; value = v; next = n; }
    }

    private int index(K key) {
        int h = key.hashCode() ^ (key.hashCode() >>> 16);
        return h & (table.length - 1);
    }

    void put(K key, V value) {
        int i = index(key);
        for (Node<K, V> p = table[i]; p != null; p = p.next) {
            if (p.key.equals(key)) { p.value = value; return; }
        }
        table[i] = new Node<>(key, value, table[i]);
        if (++size > table.length * 0.75) resize();
    }

    V get(K key) {
        for (Node<K, V> p = table[index(key)]; p != null; p = p.next) {
            if (p.key.equals(key)) return p.value;
        }
        return null;
    }

    private void resize() { /* 容量翻倍，节点按高位 bit 拆两条链搬迁 */ }
}

线程不安全的代价

并发 put 在 JDK7 可能造成链表成环（头插法 + 扩容搬迁），CPU 直接 100%；JDK8 改为尾插解决了成环，但仍有覆盖丢失（两个线程同时插入同一空桶）与扩容期间数据不一致问题。所以并发场景唯一正确选择是 ConcurrentHashMap，而不是 Collections.synchronizedMap 包一层了事——后者锁住整张表，吞吐退化严重。

HashMap 的每个设计点（扰动函数、2 的幂、0.75、树化阈值 8/64）都是对”冲突概率、内存开销、操作耗时”三者权衡的结果，把这些权衡记清楚，比背流程图有用得多。