标准件网站开发百度在线识别图片

一、HashMap 核心原理

HashMap 是 Java 中最常用的哈希表实现，基于 数组 + 链表/红黑树 的复合结构，核心特性如下：

1. 哈希函数

   • 键的哈希值通过 hashCode() 计算，并通过扰动函数优化分布：

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

2. 索引计算

   • 索引位置：(n - 1) & hash（n 是数组长度，必须是 2 的幂），相当于取模运算。

3. 冲突解决

   • 链表法：哈希冲突时，元素以链表形式存储。
   • 红黑树优化：链表长度超过 TREEIFY_THRESHOLD=8 时转为红黑树（数组长度需 ≥64）；小于 UNTREEIFY_THRESHOLD=6 时退化为链表。

---

二、源码级关键实现细节

1. 数据结构

// 数组（哈希桶）
transient Node<K,V>[] table;// 链表节点定义
static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;
}// 红黑树节点定义
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;
}

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. 键已存在，直接覆盖值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);else {// 5. 遍历链表，插入到尾部或替换现有节点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;
}

3. 扩容机制（resize）

• 触发条件：元素数量 > 容量 × 负载因子（默认 0.75）。
• 扩容步骤：
  1. 新容量为旧容量的 2 倍（保持 2 的幂次）。
  2. 遍历旧数组，重新分配元素：
     • 链表节点：拆分为高位链和低位链（利用 (e.hash & oldCap) == 0 判断）。
     • 红黑树节点：调用 split() 方法拆分或退化为链表。

---

三、HashMap 的线程安全问题

1. 非线程安全表现

• 数据覆盖：并发插入时，若两个线程同时计算到同一桶位置，可能导致数据覆盖。
• 扩容死循环：JDK 1.7 中链表头插法在并发扩容时可能形成环形链表，导致 get() 死循环（JDK 1.8 改为尾插法修复）。
• 脏读：一个线程扩容过程中，另一线程可能读取到不完整的数据。

2. 线程安全实现方案

• 使用 ConcurrentHashMap：
  • JDK 1.7：分段锁（Segment），锁粒度较粗。
  • JDK 1.8+：CAS + synchronized 锁单个桶头节点，锁粒度更细。

    final V putVal(K key, V value, boolean onlyIfAbsent) {if (key == null || value == null) throw new NullPointerException();int hash = spread(key.hashCode());int binCount = 0;for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh;if (tab == null || (n = tab.length) == 0)tab = initTable();// 使用 CAS 尝试无锁插入else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))break;}// 若桶为 ForwardingNode，协助扩容else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f);else {V oldVal = null;// 锁住桶头节点synchronized (f) {if (tabAt(tab, i) == f) {// 插入链表或红黑树}}if (binCount != 0) {if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);break;}}}addCount(1L, binCount);return null;
    }
    

• 使用 Collections.synchronizedMap：通过包装类对所有操作加互斥锁，性能较差。

---

四、总结

• 高效性：哈希函数优化、红黑树、尾插法扩容等设计提升性能。
• 线程安全：优先选择 ConcurrentHashMap，其通过细粒度锁和 CAS 实现高并发。
• 适用场景：单线程高频读写、多线程读多写少（需额外同步）。

通过源码级分析，可以深入理解 HashMap 的设计哲学与工程实现细节，为高性能编程奠定基础。