zzTzz的博客

面试高频问题

面试官最爱问："HashMap 的底层实现原理是什么？" 或者 "HashMap 的 put 过程是怎样的？"

这些问题看似简单，但要回答完整、准确，还是需要对源码有深入理解的。

HashMap 数据结构

JDK 1.8 之后，HashMap 采用 数组 + 链表 + 红黑树 的复合结构：

数组:  [0]    [1]    [2]    [3]    ...    [15]
       ↓      ↓      ↓      ↓             ↓
     null   Node   Node   null         Node
                     ↓                   ↓
                   Node               TreeNode
                     ↓
                   null

核心属性解析

put() 方法源码解析

执行流程图

put(key, value)
    ↓
计算 hash = hash(key) → (h = key.hashCode()) ^ (h >>> 16)
    ↓
计算索引 index = (n - 1) & hash
    ↓
数组该位置为空？
    ├── 是 → 创建新节点直接放入
    └── 否 → 发生哈希冲突
              ↓
        遍历链表/红黑树
              ↓
        找到相同key？
            ├── 是 → 覆盖旧值
            └── 否 → 尾插法插入新节点
                          ↓
                    链表长度 ≥ 8？
                        ├── 是 → 数组长度 ≥ 64？
                        │           ├── 是 → 转红黑树
                        │           └── 否 → 扩容
                        └── 否 → 保持链表

核心源码（简化版）

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 扰动函数 - 让高位也参与运算，减少冲突
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 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;
    
    // 1. 数组为空或长度为0，初始化扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 2. 计算索引，该位置为空则直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    else {
        Node<K,V> e; K k;
        
        // 3. 第一个节点key相同，覆盖
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        
        // 4. 红黑树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        // 5. 链表遍历
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    
                    // 链表长度>=8，转红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                
                p = e;
            }
        }
        
        // 6. 覆盖旧值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    ++modCount;
    
    // 7. 超过阈值，扩容
    if (++size > threshold)
        resize();
    
    afterNodeInsertion(evict);
    return null;
}

扩容机制（resize）

扩容触发条件

• 元素数量 > 容量 × 负载因子 (0.75)
• 单个链表长度 ≥ 8，但数组长度 < 64

扩容过程

1. 创建新数组，容量为原来的 2倍
2. 将旧数组中的节点重新散列到新数组

重新散列的巧妙之处

// 原索引: hash & (n-1)
// 新索引: hash & (2n-1) = hash & (n-1) 或 hash & (n-1) + n

// 判断是否需要移动位置
if ((e.hash & oldCap) == 0) {
    // 位置不变
} else {
    // 位置：原索引 + 旧容量
}

高频面试题速查

Q1: HashMap 和 Hashtable 的区别？

Q2: 为什么用红黑树而不是AVL树？

红黑树牺牲了部分平衡性（树高最多是2logn），换取了更少的旋转操作，在频繁插入删除的场景下性能更好。

Q3: 为什么容量必须是2的幂？

• 位运算替代取模：hash % n → hash & (n-1)，性能更高
• 扩容时只需判断 hash & oldCap 是否为0，简化重散列

总结

掌握 HashMap 源码是 Java 面试的"必修课"。建议重点理解：

1. 扰动函数的作用 - 让高位也参与运算
2. 链表转红黑树的触发条件 - 长度≥8且容量≥64
3. 扩容机制 - 2倍扩容，重新散列时的高低位判断
4. 线程安全问题 - 并发环境下使用 ConcurrentHashMap

面试技巧：回答时先从整体架构讲起，再深入 put 流程，最后扩展到扩容、线程安全等延伸问题，展现你的深度思考。