几个关于HashMap超经典的面试题! 欢迎补充

HashMap 是 Java 中一个非常重要且常用的数据结构，因此在技术面试中经常会被问到。以下列出几个经典的关于 HashMap 的面试题，并给出详细的答案和解释。

1：HashMap 的工作原理是什么？

回答：
HashMap 是基于哈希表的一种数据结构，它存储键值对（key-value pair），并通过键的哈希码将值存储到一个数组中。

基本工作原理：

1. 哈希值计算：当一个键值对插入到 HashMap 中时，首先会计算键的哈希值（使用 hashCode 方法）。
2. 定位桶：根据哈希值确定该键值对在数组中的位置（桶/桶索引）。这个位置通常通过对数组长度取模（hash % n，这里 n 是数组长度）来确定。
3. 冲突解决：如果多个键的哈希值经过取模运算落在了相同的桶中，就会出现哈希冲突。HashMap 采用链地址法来解决冲突，即在桶中使用链表或者红黑树存储多个键值对。
4. 扩容：当插入的元素数量超过数组容量（负载因子）的某个阈值时，HashMap 会进行扩容（通常是两倍扩容）。扩容时，需要重新计算每个现有键值对的哈希值并移动到新的桶中。

JDK 1.8 以后的改进：

• JDK 1.8 采用红黑树优化链表。当链表长度超过 8 且数组长度超过 64 时，链表会转换为红黑树，以提高插入和查找的效率。

2：什么是 Hash 冲突？HashMap 如何处理 Hash 冲突？

回答：
Hash 冲突：当两个或多个键的哈希值在经过取模运算后映射到 HashMap 的同一个桶位置时，发生了哈希冲突。

HashMap 处理哈希冲突的方法：

1. 链地址法：将具有相同哈希值的键值对存储在一个链表中。链表的头部存储在桶中，链表节点存储相应的键值对。

   示例：

   // 简化的链地址法示例
   class Node {
       int key;
       int value;
       Node next;
       Node(int key, int value) { this.key = key; this.value = value; }
   }
   

2. 红黑树：在 JDK 1.8 之后，当链表长度超过 8 且 HashMap 数组长度大于 64 时，链表会转换为红黑树。红黑树具有平衡二叉树的性质，能够在 O(log n) 时间复杂度内进行插入和查找操作。

3：HashMap 的扩容过程是怎样的？

回答：
HashMap 的扩容是当当前容量超过阈值（capacity * loadFactor）时触发的。

扩容过程：

1. 创建新数组：扩容时创建一个容量是原来数组两倍的新数组。
2. 重新 hash：将原数组中的每个键值对重新计算哈希值，并根据新的数组长度确定新的桶位置。
3. 桶中的元素重新分配：将原链表或树中存储的元素重新分配到新数组的桶中。

示例代码：

// Simplified resize method from HashMap class
void resize() {
    Node<K,V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    int newCapacity = oldCapacity << 1;  // Double the capacity
    Node<K,V>[] newTable = new Node[newCapacity];
    
    for (int i = 0; i < oldCapacity; i++) {
        Node<K,V> e;
        if ((e = oldTable[i]) != null) {
            oldTable[i] = null;  // Help GC
            if (e.next == null) {
                newTable[e.hash & (newCapacity - 1)] = e;  // Single element in bucket, move it directly
            } else if (e instanceof TreeNode) {
                // Handle tree nodes…
            } else {
                // Rehash all elements in the same bucket
                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 & oldCapacity) == 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 (loHead != null) newTable[i] = loHead;
                if (hiHead != null) newTable[i + oldCapacity] = hiHead;
            }
        }
    }
    table = newTable;
}

4：HashMap 和 ConcurrentHashMap 的区别？

回答：
HashMap 和 ConcurrentHashMap 都是存储键值对的集合，但它们在并发环境下的表现不同。

1. 线程安全性：

   • HashMap：非线程安全的。多个线程同时对 HashMap 进行读写操作可能导致数据不一致。
   • ConcurrentHashMap：线程安全的。通过分段锁或 CAS 操作实现高效并发控制。

2. 锁机制：

   • HashMap：没有任何锁机制。
   • ConcurrentHashMap：JDK 1.7 采用分段锁（Segment）。JDK 1.8 取消分段锁，采用 CAS 和 synchronized 锁优化并发控制。

3. 性能：

   • HashMap：在没有并发需求的情况下，性能较好。
   • ConcurrentHashMap：在并发较高的场景下，性能优越。

4. 迭代器：

   • HashMap：迭代器是快速失败的（fail-fast）。如果在迭代过程中检测到集合被修改，会抛出 ConcurrentModificationException。
   • ConcurrentHashMap：迭代器是弱一致性的，不抛异常，只能保证在创建迭代器时的元素一致性，后续元素变动不影响当前迭代结果。

5：为什么 HashMap 的 initialCapacity 应该是 2 的幂？

回答：
HashMap 的 initialCapacity 应该是 2 的幂次主要是为了优化哈希分布，减少哈希冲突。具体原因如下：

1. 提高哈希分布均匀性：使用 hash % n 来确定元素存放的桶位置。n 为 2 的幂时，n-1 的二进制表示形式只有低位是 1，高位全是 0，这样进行 hash & (n-1) 操作时，高位信息不会被丢失，提高了哈希分布的均匀性。

   示例：

   int hash = key.hashCode();
   int index = hash & (n - 1); // n is a power of 2
   

2. 提高计算效率：使用 &（按位与）操作比 %（取模）操作更快，因为 & 是位操作，直接在二进制层面进行。

3. 避免resize过程中的浪费：当容量是 2 的幂时，resize 过程中的元素会重新分布到新的桶位置上，不会产生严重的哈希冲突，有助于保持均匀分布。

综上所述，选择 2 的幂次作为 HashMap 的初始容量有助于提高哈希分布的均匀性和插入、查询的性能。