问题

HashMap的实现原理是什么？

---

标准答案

HashMap是基于哈希表（Hash Table）实现的，核心思想是数组 + 链表（JDK 1.7）或数组 + 链表 + 红黑树（JDK 1.8）的组合结构。它通过哈希函数计算键的索引位置，并使用拉链法（链表或红黑树）处理哈希冲突。HashMap的关键机制包括哈希计算、冲突处理、扩容机制、遍历方式等。JDK 1.8 对 HashMap 进行了优化：当某个桶的链表长度超过**阈值（8）**时，会转换为红黑树，以提高查找效率。

---

答案解析

1. 数据结构

HashMap的底层数据结构在不同版本中有所演进：

• JDK 1.7 及之前： 数组 + 链表
• JDK 1.8 及之后： 数组 + 链表 + 红黑树（链表长度超出阈值时转换）

核心结构：
HashMap 由一个数组（table） 组成，每个数组的元素是一个 Node<K, V>（链表/红黑树的头结点），每个节点存储键值对（Entry）。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;  // 哈希值（用于加速查找）
    final K key;     // 键
    V value;         // 值
    Node<K,V> next;  // 指向下一个节点（形成链表）
}

在 JDK 1.8 及之后，当链表长度超过 8 时，链表会转换为红黑树：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent, left, right;
    boolean red;
}

---

2. HashMap 的核心原理

(1) 计算键的存储索引（哈希函数）

• 插入键值对时，HashMap 通过 hashCode() 计算键的哈希值 h，然后通过 按位运算 计算存储位置：

  static final int hash(Object key) {
      int h;
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
  

  解释：

  • key.hashCode() 计算对象的原始哈希值
  • h ^ (h >>> 16) 进一步扰动哈希值，使高位参与计算，提高随机性
  • 索引 = hash & (table.length - 1)
    • 由于 table.length 总是 2 的幂，& (length - 1) 作用相当于取模运算 % length，但更高效

(2) 处理哈希冲突

哈希冲突（多个键计算出的索引相同）有两种处理方式：

• JDK 1.7：链地址法（单向链表）
• JDK 1.8：链表 + 红黑树

JDK 1.8 的改进

• 链表过长（> 8）时，转化为红黑树（提高查询性能 O(n) -> O(log n)）
• **红黑树退化：**当扩容或元素减少后，红黑树节点少于 6，则重新转换为链表

(3) 负载因子与扩容

HashMap 的扩容机制：

• **负载因子（load factor）：**决定何时扩容，默认值 0.75
• 阈值（threshold）： capacity * loadFactor
• 扩容规则： 当 size > threshold，触发扩容（rehash），数组长度翻倍 (capacity * 2)

扩容的代价：
由于需要重新计算所有元素的索引并迁移到新的数组，rehash 是一个昂贵的操作，会影响性能。

void resize() {
    Node<K,V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    int newCapacity = oldCapacity * 2;  // 扩容两倍
    Node<K,V>[] newTable = new Node[newCapacity];
    
    for (Node<K,V> e : oldTable) {  
        while (e != null) { 
            Node<K,V> next = e.next;
            int newIndex = e.hash & (newCapacity - 1); // 计算新索引
            e.next = newTable[newIndex];
            newTable[newIndex] = e;
            e = next;
        }
    }
    table = newTable;
}

优化建议：

• 如果事先知道数据量，建议初始化容量，避免扩容影响性能：

  Map<String, Integer> map = new HashMap<>(1024);
  

---

3. JDK 1.7 vs JDK 1.8 的主要区别

版本	结构	哈希冲突处理	扩容顺序	线程安全问题
JDK 1.7	数组 + 链表	头插法（容易引发死链）	先扩容再迁移数据	存在死循环风险
JDK 1.8	数组 + 链表 + 红黑树	尾插法（防止死循环）	先迁移再扩容	改进了并发安全性

JDK 1.7 存在的问题：
由于采用头插法，在并发情况下可能导致 环形链表（死循环），使 get() 方法陷入死循环。

4. HashMap 的常见问题

❌ 常见误区

1. 误认为 HashMap 是线程安全的

   • 错误示例：多个线程同时 put() 可能导致数据丢失、死循环
   • **正确方案：**使用 ConcurrentHashMap

2. 错误实现 hashCode() 导致哈希碰撞严重

   • 错误示例：

     @Override
     public int hashCode() {
         return 1; // 全部 key 产生相同哈希值，退化为链表
     }
     

   • **正确方案：**合理分布 hashCode()

3. 忽视扩容开销

   • **优化方案：**事先指定 initialCapacity，避免频繁扩容

深入追问

🔹 HashMap 何时触发扩容？扩容会带来什么性能问题？如何优化？
🔹 多线程环境下，HashMap 会导致哪些并发问题？如何解决？
🔹 为什么 HashMap 采用 & (table.length - 1) 而不是 % length？

相关面试题

• ConcurrentHashMap 和 HashMap 有什么区别？
• 如何优化 HashMap 的性能？
• HashMap 扩容时是否可能造成数据丢失？
• 为什么 HashMap 的容量必须是 2 的幂？
• HashMap 为什么要用红黑树，而不是 AVL 树或 B+ 树？

---

总结

• 底层结构： 数组 + 链表 + 红黑树
• 哈希冲突处理： 先用链表，链表过长时转为红黑树
• 扩容机制： 负载因子 0.75，超阈值时容量翻倍
• JDK 1.8 改进： 采用尾插法、红黑树优化查询
• 线程安全问题： 非线程安全，需用 ConcurrentHashMap

这就是 HashMap 的完整实现原理！ 🚀