HashMap 高频面试题全解：null key、遍历顺序、线程安全

static final int hash(Object key) {
    int h;
    // key == null → 直接返回 0，不调用 hashCode()，无空指针风险
    return (key == null) ? 0
         : (h = key.hashCode()) ^ (h >>> 16);  // 高 16 位与低 16 位异或，让高位参与散列
}

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;                 // 懒加载：第一次 put 才建表
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);  // 桶空 → 直接挂新节点（null key 也走这里）
    else {
        // 桶非空：链表/红黑树查找，命中则覆盖 value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            ...
    }
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {   // 定位桶
        if (first.hash == hash && ((k = first.key) == key
            || (key != null && key.equals(k))))        // null key：引用比较命中
            return first;
        if ((e = first.next) != null) { // 桶内继续：链表或红黑树
            ...
        }
    }
    return null;   // 表为空 / 桶为空 / 没找到 → 返回 null
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null)
        throw new NullPointerException();  // 没有任何商量
    ...
}

Map<String, Integer> map = new HashMap<>();
map.put("apple",  1);
map.put("banana", 2);
map.put("cherry", 3);
map.put("date",   4);

// 遍历：从 table[0] 开始逐桶扫描，桶内按链表/树顺序
// 结果取决于每个 key 的 (n-1) & hash —— 可能是 banana, apple, date, cherry
for (String key : map.keySet()) {
    System.out.println(key + " → " + map.get(key));
}

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;  // 双向链表的前后指针
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

++modCount;                      // 结构性修改计数
if (++size > threshold)          // 超过阈值 → 扩容
    resize();
afterNodeInsertion(evict);       // 给 LinkedHashMap 的钩子（LRU）
return null;                     // put 返回旧 value，没有则 null

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) {          // 1 << 30，极限保护
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY   // 左移一位 = ×2
                 && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;                         // 阈值也翻倍
    }
    ...
    // 新建 newTab = new Node[newCap]，然后逐桶搬运（见下方拆分逻辑）
}

for (int j = 0; j < oldCap; ++j) {
    Node<K,V> e;
    if ((e = oldTab[j]) != null) {
        oldTab[j] = null;                 // 顺手置空旧桶，帮助 GC
        if (e.next == null)               // 桶里只有一个节点
            newTab[e.hash & (newCap - 1)] = e;   // 直接算新位置
        else if (e instanceof TreeNode)
            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 红黑树拆分
        else {
            Node<K,V> loHead = null, loTail = null;  // 低位链：hash&oldCap==0
            Node<K,V> hiHead = null, hiTail = null;  // 高位链：hash&oldCap==1
            Node<K,V> next;
            do {
                next = e.next;
                if ((e.hash & oldCap) == 0) {      // 关键判断：新的一位是 0
                    if (loTail == null) loHead = e;
                    else loTail.next = e;               // 尾插法，保持原顺序
                    loTail = e;
                } else {
                    if (hiTail == null) hiHead = e;
                    else hiTail.next = e;
                    hiTail = e;
                }
                e = next;
            } while (e != null);
            if (loTail != null) { loTail.next = null; newTab[j] = loHead; }        // 原地
            if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }  // +oldCap
        }
    }
}

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while (null != e) {
            Entry<K,V> next = e.next;          // ① 先记下下一个节点
            if (rehash) e.hash = ...;
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];            // ② 新节点的 next 指向当前桶头 → 头插
            newTable[i] = e;                 // ③ 当前节点成为新桶头
            e = next;                           // ④ 处理下一个
        }
    }
}

// 典型事故场景：全局缓存使用 HashMap（JDK 1.7 时代）
public class CacheService {
    // ❌ 错误：多线程环境用了 HashMap
    private Map<String, Object> cache = new HashMap<>();

    public void refreshCache(List<Config> configs) {
        // 多个线程同时调用 → 并发 put → 触发并发 resize → 成环
        configs.forEach(c -> cache.put(c.getKey(), c.getValue()));
    }
}

// 修复方案：替换为 ConcurrentHashMap（或扩容前加锁）
private Map<String, Object> cache = new ConcurrentHashMap<>();

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;                    // 写点①：两个线程可能各自 resize
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);    // 写点②：空桶并发写入，后写覆盖先写
    else {
        // 桶非空：链表/树内插入或覆盖（写点③：链表结构被并发破坏）
        ...
    }
    ++modCount;
    if (++size > threshold)                          // 写点④：++size 非原子，计数丢失
        resize();
    ...
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    for (Node<K,V>[] tab = table;;) {
        ...
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                break;                    // 空桶：CAS 原子写入，谁先成功谁赢，不会互相覆盖
        }
        else {
            synchronized (f) { ... }       // 桶非空：锁桶头节点，串行化桶内操作
        }
    }
    addCount(1L, binCount);             // 计数：baseCount + CounterCell[]，原子累加
    return null;
}

class User {
    String name;
    int age;

    User(String name, int age) {
        this.name = name; this.age = age;
    }

    // 只重写了 equals，没重写 hashCode —— 这是一个 Bug
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User u = (User) o;
        return age == u.age && name.equals(u.name);
    }
    // hashCode() 继承 Object —— 基于内存地址，每次 new 都不同
}

Map<User, String> map = new HashMap<>();
User u1 = new User("Alice", 25);
User u2 = new User("Alice", 25);

map.put(u1, "VIP");
System.out.println(u1.equals(u2));        // true —— equals 认为相等
System.out.println(map.get(u2));           // null —— 但 HashMap 找不到！
// 原因：u1 和 u2 的 hashCode 不同，落到了不同的桶

class Key {
    String value;
    public int hashCode() { return value.hashCode(); }
    public boolean equals(Object o) {
        return o instanceof Key && value.equals(((Key)o).value);
    }
}

Map<Key, String> map = new HashMap<>();
Key k = new Key();
k.value = "hello";
map.put(k, "world");

k.value = "changed";    // 修改了影响 hashCode 的字段
System.out.println(map.get(k));  // null —— 找不到！
// 原因：put 时 k 在 hash("hello") 对应的桶里
// get 时用 hash("changed") 去查，去了完全不同的桶

Map<String, String> m = new HashMap<>();
String r1 = m.put("k", "v1");   // null —— 之前没有该 key
String r2 = m.put("k", "v2");   // "v1" —— 返回被覆盖的旧值
// 注意：如果旧值本身就是 null，返回值也是 null，无法区分"新增"与"覆盖为 null"
// 想区分必须用 containsKey() 先判断（单线程下可靠）

// ❌ 默认容量 16，存 1000 个元素会触发多次扩容（每次都要搬运+rehash）
Map<String, Object> bad = new HashMap<>();

// ✅ 正确：预估元素数量，指定初始容量
int expectedSize = 1000;
Map<String, Object> good = new HashMap<>(
    (int)(expectedSize / 0.75f) + 1
);

// ✅ 更简洁：Google Guava（内部同样按 0.75 反推）
Map<String, Object> guava = Maps.newHashMapWithExpectedSize(1000);

// Java 9+ Map.of() —— 不可变，不允许 null key/value
Map<String, Integer> config = Map.of(
    "timeout",  3000,
    "retries",  3,
    "poolSize", 10
);

// Map.copyOf() —— 从已有 Map 创建不可变副本
Map<String, Integer> snapshot = Map.copyOf(config);

// config.put("new", 1)  → UnsupportedOperationException
// Map.of("key", null)   → NullPointerException（与 CHM 同一哲学）