Java 面试精讲：HashMap 底层原理与源码剖析

引言

HashMap 是 Java 集合框架中最常用的数据结构之一，也是面试中的高频考点。从线程安全问题到扩容机制，从哈希冲突到红黑树转换，每一个知识点都可能成为面试中的杀手锏。本文将深入剖析 HashMap 的底层原理，帮助你从容应对面试。

---

一、HashMap 数据结构概述

1.1 核心结构

HashMap 在 JDK 1.8 中采用了数组 + 链表 + 红黑树的复合数据结构：

HashMap 结构示意：

  数组 (Node<K,V>[] table)
  +---+---+---+---+---+---+---+---+
  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
  +---+---+---+---+---+---+---+---+
              |       |
              v       v
           链表/红黑树

• 数组：存储哈希桶（bucket），通过 (n - 1) & hash 定位索引
• 链表：处理哈希冲突，采用头插法（JDK 1.7）或尾插法（JDK 1.8）
• 红黑树：链表长度超过 8 时转换为红黑树，提升查询效率

1.2 核心参数

// 默认初始容量（必须是 2 的幂）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824

// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转红黑树阈值
static final int TREEIFY_THRESHOLD = 8;

// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;

// 最小树化容量（表容量需达到 64）
static final int MIN_TREEIFY_CAPACITY = 64;

---

二、核心方法源码解析

2.1 哈希算法

HashMap 的哈希算法非常精妙，通过高位与低位混合计算，减少哈希冲突：

static final int hash(Object key) {
    int h;
    // key 的 hashCode 与高 16 位做异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

为什么需要这样计算？

当数组长度较小时（如默认的 16），hash & (n-1) 实际上只使用了 hash 的低几位，高位信息被忽略。通过 hash ^ (hash >>> 16) 将高位信息混入低位，减少冲突。

2.2 put 方法

put 方法是 HashMap 的核心，流程如下：

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

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;
            }
        }
        // key 已存在，更新 value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 检查是否需要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

2.3 扩容机制 (resize)

当元素数量超过 capacity * loadFactor 时触发扩容：

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) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 容量翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 阈值翻倍
    }
    else if (oldThr > 0)
        newCap = oldThr;
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    // 数据迁移（旧表不为空时）
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                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;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null) loHead = e;
                            else loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null) hiHead = e;
                            else hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

---

三、面试高频问题解析

Q1: HashMap 和 Hashtable 的区别？

特性	HashMap	Hashtable
线程安全	否	是
性能	更高	较低
是否允许 null 键/值	允许一个 null 键，多个 null 值	都不允许
出现版本	JDK 1.2	JDK 1.0

线程安全的替代方案：

1. Collections.synchronizedMap(new HashMap<>())
2. ConcurrentHashMap（推荐，分段锁机制，性能更高）

Q2: 为什么 String/Integer 适合作为 HashMap 的键？

原因：

1. 不可变性：String 和 Integer 都是不可变的，保证了 hashCode 的不变性
2. 已重写 hashCode() 和 equals()：确保相等的对象有相同的哈希值
3. 计算高效：String 的 hashCode 有缓存机制

自定义对象作为键的注意事项：

public class Key {
    private final String field;
    
    @Override
    public int hashCode() {
        return Objects.hash(field);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Key key = (Key) obj;
        return Objects.equals(field, key.field);
    }
}

Q3: HashMap 扩容时为什么是 2 的幂次方？

原因：

1. 位运算高效：hash % n 可以用 hash & (n-1) 替代，位运算比取模快

2. 均匀分布：2 的幂次方减 1 的二进制全是 1（如 15 = 1111），可以充分利用 hash 的所有位

3. 扩容迁移优化：扩容时只需判断 hash 的高一位是 0 还是 1，快速确定新位置

旧容量: 16  (10000)
新容量: 32  (100000)

hash:  0001 0101  (21)
       
旧位置: 21 & 15 = 5
新位置: 21 & 31 = 21

判断: 21 & 16 = 16 > 0 → 新位置 = 原位置 + 16

Q4: 链表转红黑树的阈值为什么是 8？

源码注释的解释：

/* Because TreeNodes are about twice the size of regular nodes, we
 * use them only when bins contain enough nodes to warrant use
 * (see TREEIFY_THRESHOLD). And when they become too small (due to
 * removal or resizing) they are converted back to plain bins.
 */

原因分析：

1. 权衡空间与性能：TreeNode 的大小是普通 Node 的 2 倍，需要权衡内存开销

2. 泊松分布统计：根据源码注释，假设 hash 函数均匀分布，链表长度达到 8 的概率已经很低（约 0.006%）

3. 查询性能：

   • 链表平均查询复杂度：O(n/2)
   • 红黑树查询复杂度：O(log n)
   • 当 n=8 时，链表平均 4 次，红黑树约 3 次，差距不大
   • 当 n 更大时，红黑树优势明显

转回链表阈值为什么是 6？

防止在 8 附近频繁转换（树化阈值 8，反树化阈值 6），留出缓冲区间。

---

四、实战代码示例

自定义线程安全的 HashMap

import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * 使用读写锁实现的线程安全 HashMap
 * 读多写少场景下性能优于 synchronized
 */
public class SafeHashMap<K, V> {
    private final HashMap<K, V> map = new HashMap<>();
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    
    public V put(K key, V value) {
        lock.writeLock().lock();
        try {
            return map.put(key, value);
        } finally {
            lock.writeLock().unlock();
        }
    }
    
    public V get(K key) {
        lock.readLock().lock();
        try {
            return map.get(key);
        } finally {
            lock.readLock().unlock();
        }
    }
    
    public V remove(K key) {
        lock.writeLock().lock();
        try {
            return map.remove(key);
        } finally {
            lock.writeLock().unlock();
        }
    }
    
    public int size() {
        lock.readLock().lock();
        try {
            return map.size();
        } finally {
            lock.readLock().unlock();
        }
    }
}

高性能缓存实现

/**
 * 基于 HashMap 的 LRU 缓存实现
 * 使用 LinkedHashMap 简化实现
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        // accessOrder = true 按访问顺序排序
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
    
    public static void main(String[] args) {
        LRUCache<String, String> cache = new LRUCache<>(3);
        cache.put("A", "1");
        cache.put("B", "2");
        cache.put("C", "3");
        System.out.println(cache); // {A=1, B=2, C=3}
        
        cache.get("A"); // 访问 A
        cache.put("D", "4"); // 插入 D，B 被淘汰
        System.out.println(cache); // {C=3, A=1, D=4}
    }
}

---

五、面试回答技巧总结

回答框架：总-分-总

示例：说说 HashMap 的底层原理？

总：HashMap 底层采用数组 + 链表 + 红黑树的数据结构，通过哈希函数实现 O(1) 的查询效率。

分：

1. 哈希计算：对 key 的 hashCode 进行扰动处理 (h = key.hashCode()) ^ (h >>> 16)，减少冲突
2. 索引定位：通过 (n - 1) & hash 计算数组下标，这里要求数组长度是 2 的幂次方
3. 冲突处理：相同索引的元素以链表形式存储，JDK 1.8 后链表长度超过 8 且数组长度超过 64 时转为红黑树
4. 扩容机制：当元素数量超过阈值（capacity * 0.75）时触发扩容，容量翻倍，数据重新哈希

总：理解这些原理对于写出高效代码和排查性能问题都很重要。

常见追问及准备

追问方向	准备要点
为什么用红黑树不用 AVL 树？	红黑树旋转次数更少，增删效率更高
为什么是 0.75 不是其他值？	时间和空间成本的权衡，统计学泊松分布
扩容为什么是 2 倍？	保持 2 的幂次方，位运算高效，迁移优化
HashMap 为什么非线程安全？	同时 put 可能导致数据丢失、死循环（JDK 1.7）

---

六、总结

HashMap 看似简单，实则蕴含了丰富的设计思想：

1. 空间换时间：用数组实现 O(1) 查找
2. 平衡艺术：链表与红黑树的转换，时间与空间的权衡
3. 延迟加载：扩容的触发时机设计
4. 哈希优化：扰动函数减少冲突

掌握这些原理，不仅能轻松应对面试，更能指导日常开发中的性能优化。

---

参考源码版本：JDK 1.8.0_361