Java HashMap 原理详解

一、基本概念

HashMap 是 Java 中最常用的键值对集合，基于哈希表实现，提供了快速的存取操作。

Map<String, Integer> map = new HashMap<>();
map.put("key1", 100);
map.get("key1");  // 返回 100

二、核心数据结构

1. JDK 1.8 之前：数组 + 链表

数组索引:  [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]
           ↓     ↓     ↓     ↓     ↓     ↓     ↓     ↓
         null  Node  Node  null  Node  null  null  Node
                     ↓           ↓
                   Node        Node

2. JDK 1.8 之后：数组 + 链表 + 红黑树

数组索引:  [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]
           ↓     ↓     ↓     ↓     ↓     ↓     ↓     ↓
         null  Node  Node  null  Tree  null  null  Node
                     ↓           ↓
                   Node        TreeNode
                               /    \
                           TreeNode TreeNode

红黑树转换条件：

  • 链表长度 ≥ 8
  • 数组长度 ≥ 64
  • 同时满足这两个条件时，链表转换为红黑树

三、核心源码分析

1. 基本属性

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    // 默认初始容量 16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    // 默认负载因子 0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    // 链表转红黑树的阈值
    static final int TREEIFY_THRESHOLD = 8;
    
    // 红黑树转链表的阈值
    static final int UNTREEIFY_THRESHOLD = 6;
    
    // 哈希桶数组
    transient Node<K,V>[] table;
    
    // 键值对数量
    transient int size;
    
    // 扩容阈值
    int threshold;
    
    // 负载因子
    final float loadFactor;
}

2. Node 节点结构

// 链表节点
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;      // 哈希值
    final K key;         // 键
    V value;             // 值
    Node<K,V> next;      // 下一个节点
    
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    
    public final K getKey() { return key; }
    public final V getValue() { return value; }
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
}

3. TreeNode 节点结构

// 红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // 父节点
    TreeNode<K,V> left;    // 左子节点
    TreeNode<K,V> right;   // 右子节点
    TreeNode<K,V> prev;    // 前驱节点（用于删除）
    boolean red;           // 颜色标记
    
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

四、核心操作原理

1. 哈希计算

// 计算哈希值
static final int hash(Object key) {
    int h;
    // key 为 null 时，hash 值为 0
    // 否则：key 的 hashCode() 高 16 位异或低 16 位
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 计算数组索引
final int index = (n - 1) & hash;  // n 为数组长度

为什么要异或高 16 位？

  • 减少哈希冲突
  • 充分利用 hashCode 的高位信息
  • 计算速度快

2. put 操作流程

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. 如果数组为空，初始化数组
    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;
                }
                // 找到相同的 key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 6. 如果 key 已存在，覆盖旧值
        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;
}

3. get 操作流程

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    
    // 1. 数组不为空且计算的位置有数据
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        
        // 2. 检查第一个节点
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        
        // 3. 检查后续节点
        if ((e = first.next) != null) {
            // 红黑树查找
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            
            // 链表查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

4. resize 扩容机制

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    // 1. 计算新容量
    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 < MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    // 2. 创建新数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    // 3. 数据迁移
    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;
}

五、关键特性

1. 负载因子 0.75 的原因

// 时间和空间的平衡
// 0.75：时间和空间成本的最佳平衡点
// 太小：空间浪费，但冲突少
// 太大：空间利用率高，但冲突多
static final float DEFAULT_LOAD_FACTOR = 0.75f;

2. 容量总是 2 的幂次方

// 原因：
// 1. (n - 1) & hash 等价于 hash % n，但位运算更快
// 2. 保证索引分布均匀
// 3. 扩容时可以高效地重新计算位置

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

3. 线程安全问题

HashMap 是非线程安全的，多线程环境下会出现问题：

// 并发 put 可能导致：
// 1. 数据丢失
// 2. 死循环（JDK 1.7）
// 3. 数据不一致

// 线程安全的替代方案：
Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();
Map<String, Integer> synchronizedMap = Collections.synchronizedMap(new HashMap<>());

六、性能分析

时间复杂度

操作 平均情况 最坏情况
put O(1) O(n)
get O(1) O(n)
remove O(1) O(n)

说明：

  • 平均 O(1)：哈希函数分布均匀时
  • 最坏 O(n)：所有 key 哈希到同一个位置（链表）

空间复杂度

  • O(n)：n 为键值对数量
  • 额外空间：数组 + 链表/红黑树节点

七、常见面试题

1. HashMap 的扩容机制？

// 触发条件：size > threshold（capacity * loadFactor）
// 扩容大小：原容量的 2 倍
// 数据迁移：重新计算每个元素的位置

2. 为什么 HashMap 线程不安全？

// 1. JDK 1.7：扩容时可能导致死循环
// 2. JDK 1.8：不会死循环，但可能数据覆盖
// 3. 多线程 put 可能导致数据丢失

3. HashMap 和 Hashtable 的区别？

特性 HashMap Hashtable
线程安全 否 是
允许 null 键/值 是 否
性能 高 低
继承 AbstractMap Dictionary
迭代器 Fail-Fast Fail-Safe

4. HashMap 和 ConcurrentHashMap 的区别？

// HashMap：非线程安全
// ConcurrentHashMap：线程安全
// ConcurrentHashMap 使用分段锁（JDK 1.7）或 CAS + synchronized（JDK 1.8）

八、最佳实践

// 1. 指定初始容量，避免频繁扩容
Map<String, String> map = new HashMap<>(100);

// 2. 使用合适的对象作为 key
// - 实现 hashCode() 和 equals()
// - 最好是不可变对象
// - String 是很好的 key 选择

// 3. 避免使用可变对象作为 key
class BadKey {
    private int value;
    // 如果 value 变化，hashCode 也会变化，导致找不到元素
}

// 4. 注意内存泄漏
// 及时 remove 不再使用的键值对

总结

HashMap 是 Java 中最重要的集合类之一，理解其原理对于编写高效代码和解决性能问题非常重要。核心要点：

  1. 数据结构：数组 + 链表 + 红黑树（JDK 1.8+）
  2. 哈希计算：扰动函数优化，减少冲突
  3. 扩容机制：容量翻倍，负载因子 0.75
  4. 性能：平均 O(1)，最坏 O(n)
  5. 线程安全：非线程安全，多线程用 ConcurrentHashMap
# java # 哈希算法 # 开发语言
Logo
https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

四天蒸发近2000亿，宇树科技股价近乎“腰斩”；苹果举办库克告别派对：9月1日正式卸任CEO；Anthropic两款新Claude模型曝光 | 极客头条

avatar AI编程社区
cover

Claude Code反超GitHub Copilot登顶第一、90%程序员已用上Agent，最新AI编码调查报告来了

avatar AI编程社区
cover

如何用好 Claude Code 写后端代码

avatar AI编程社区