当前位置：首页 > article >正文

Java高频面试之集合-09

article 2025/3/13 17:11:46

hello啊，各位观众姥爷们！！！本baby今天来报道了！哈哈哈哈哈嗝🐶

面试官：详细说说HashMap

HashMap 数据结构详解

HashMap 是 Java 中最常用的键值对存储结构，基于 哈希表 实现，核心设计目标是 高效查找与插入。以下是其底层实现原理与关键优化：

一、核心数据结构

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

数组（桶数组）
- 初始容量为 16（可自定义），存储链表的头节点或红黑树的根节点。
- 数组索引通过 哈希值 & (数组长度 - 1) 计算（等价于取模，但性能更高）。
链表
- 哈希冲突时，键值对以链表形式存储在同一桶中（拉链法）。
- 链表节点为 Node<K,V>，包含 key、value、hash 和 next 指针。
红黑树
- 当链表长度 ≥8 且数组长度 ≥64 时，链表转换为红黑树（TreeNode），将查询复杂度从 O(n) 优化为 O(log n)。
- 树节点退化为链表的条件：节点数 ≤6（避免频繁转换）。

二、哈希计算与冲突解决

哈希值计算

static final int hash(Object key) {
    int h;
    // 高16位异或低16位，增强散列性
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

哈希冲突处理
- 拉链法：冲突的键值对存入同一桶的链表或树。
- 再哈希法：通过扩容重新分布键值对。

三、动态扩容机制

触发条件
当元素数量 > 容量 × 负载因子（默认0.75） 时触发扩容。
扩容流程
- 创建新数组（容量翻倍，保持 2^n 特性）。
- 遍历旧数组，重新计算节点位置（利用高位区分新旧索引）。
- 链表节点按 (e.hash & oldCap) == 0 拆分为低位链表和高位链表。
扩容优化（JDK 1.8）
- 单链表拆分：避免多线程下环形链表问题。
- 红黑树拆分：树节点按哈希值拆分后，若节点数 ≤6，退化为链表。

四、关键操作源码解析

put(K key, V value)

public V put(K key, V value) {
    // 计算哈希值
    int hash = hash(key);
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 初始化或扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 计算桶索引
    i = (n - 1) & hash;
    p = tab[i];
    
    // 桶为空，直接插入新节点
    if (p == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 桶首节点匹配
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 树节点处理
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 链表遍历
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 链表转树
                    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;
            }
        }
        // 更新值并返回旧值
        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;
}

get(Object key)

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;
    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))))
            return first;
        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;
}

五、性能与优化

时间复杂度

操作平均最差
put/get O(1) O(log n)（树化后）
调优参数
- 初始容量：预估元素数量，避免频繁扩容（建议设为 (预期元素数 / 负载因子) + 1）。
- 负载因子：默认 0.75，权衡空间利用与哈希冲突。
线程安全替代方案
- ConcurrentHashMap：分段锁或 CAS 实现高并发读写。
- Collections.synchronizedMap：包装类，方法级同步。

操作	平均	最差
`put`/`get`	`O(1)`	`O(log n)`（树化后）

六、JDK 1.7 vs 1.8 对比

特性	JDK 1.7	JDK 1.8
数据结构	数组 + 链表	数组 + 链表 + 红黑树
哈希计算	多次扰动（4次位运算+5次异或）	1次位运算 + 1次异或
扩容策略	头插法（可能产生环形链表）	尾插法（避免环形链表）
节点拆分	全链表重新哈希	高低位链表拆分