- 正确答案：HashMap 是 Java 中基于哈希表实现的键值对（Key-Value）集合，底层采用“数组 + 链表 + 红黑树”（JDK 1.8+）的混合结构。其核心原理是通过哈希函数将 key 映射到数组索引位置（即桶 bucket），发生哈希冲突时，先用链表解决；当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转为红黑树以优化查找性能；扩容时触发 rehash，新容量为原容量的 2 倍（初始容量 16，负载因子 0.75，默认阈值 12）。 - 解答思路： 1. 先明确 HashMap 的目标：支持 O(1) 平均时间复杂度的 put/get 操作； 2. 分析如何实现 O(1)：依赖数组随机访问能力 → 需将任意 key 映射为合法数组下标 → 引入哈希函数 + 取模/位运算； 3. 冲突不可避免 → 需冲突解决机制 → JDK 1.7 用头插法链表，JDK 1.8 改为尾插法 + 树化条件； 4. 扩容必要性：避免哈希冲突激增导致链表过长，退化为 O(n)；扩容需 rehash 所有已有元素 → 成本高，故需合理设置初始容量与负载因子； 5. 线程不安全本质：put 过程中涉及数组赋值、链表插入、树化、扩容等非原子操作，多线程并发可能导致死循环（JDK 1.7）、数据覆盖、丢失或树结构破坏（JDK 1.8）。 - 深度知识讲解：【1】哈希计算全过程（JDK 1.8）： - key.hashCode() 得到 int 哈希码（可能分布不均，尤其对 Integer、String 等）； - 执行扰动函数：h = key.hashCode() ^ (key.hashCode() >>> 16)，使高16位参与低位运算，降低哈希碰撞概率（尤其在数组容量较小时，下标由低几位决定）； - 计算索引：tab[(n - 1) & hash]，其中 n 是 table.length（必为 2 的幂）。该位运算等价于 hash % n，但效率更高，前提是 n 为 2 的幂 —— 这也是 HashMap 容量始终为 2 的幂的根本原因（由 resize 保证）。【2】Node 结构与存储模型： static class Node implements Map.Entry { final int hash; final K key; V value; Node next; // 链表指针 } 数组 table 是 Node[] 类型，每个元素是一个桶（bucket），指向该桶的首节点（链表头或红黑树根）。【3】链表转红黑树的双重阈值设计（treeifyBin）： - 条件一：链表长度 ≥ TREEIFY_THRESHOLD（=8）； - 条件二：table.length ≥ MIN_TREEIFY_CAPACITY（=64）；原因：若数组太小（如 length=16），即使链表长为8，扩容后（→32）可能自然分散；盲目树化反而增加维护开销。只有当数组已足够大仍冲突严重，才说明 key 哈希质量差或业务数据强聚集，此时树化收益大于成本。【4】红黑树节点结构（TreeNode）：继承自 Node，并扩展 parent、left、right、prev、red 等字段，形成可双向遍历的平衡二叉搜索树。树化时需遍历链表构造树，反向解树（untreeify）则还原为链表。树节点的查找、插入、删除均为 O(log k)，k 为该桶内元素数。【5】扩容机制（resize）： - 新容量 newCap = oldCap << 1（左移一位，即 ×2）； - 新阈值 newThr = oldThr << 1； - 遍历旧 table：对每个非空桶，若为单节点，直接 rehash 到新 table；若为链表，按 “e.hash & oldCap” 是否为 0 分成两个子链表（loHead/hiHead），分别插入新 table 的原索引位或原索引+oldCap 位（因新容量翻倍，高位多 1 bit）； - 若为红黑树，同样拆分为两棵子树（split 方法），若子树节点数 < UNTREEIFY_THRESHOLD（=6），则退化为链表。【6】关键常量与设计哲学： - DEFAULT_INITIAL_CAPACITY = 1 << 4 = 16； - DEFAULT_LOAD_FACTOR = 0.75f； - TREEIFY_THRESHOLD = 8； - UNTREEIFY_THRESHOLD = 6； - MIN_TREEIFY_CAPACITY = 64；负载因子 0.75 是时间与空间的折中：太小（如 0.5）→ 频繁扩容，内存浪费；太大（如 1.0）→ 冲突增多，链表/树变长，查询退化。实测和理论分析表明 0.75 在均匀哈希下能保持平均链表长度 ≈ 0.5，接近最优。【7】与 Hashtable、ConcurrentHashMap 对比： - Hashtable：全方法 synchronized，粗粒度锁，性能差；初始容量 11，扩容为 old×2+1，不保证 2 的幂，取模用 % 运算；不支持 null key/value； - ConcurrentHashMap（JDK 1.8）：取消分段锁（Segment），改用 CAS + synchronized（锁单个桶的首节点）；同样使用数组+链表+红黑树；引入 ForwardingNode 标记扩容中状态，支持并发读写；size 计数用 longAccumulator（类似分段计数器）避免全局锁。 - 伪代码（核心 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[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) // 无冲突，直接插入 tab[i] = newNode(hash, key, value, null); else { Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // key 存在，覆盖 else if (p instanceof TreeNode) e = ((TreeNode)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) // -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; } ```

中科卫星

全站热榜

创作者周榜