面试题：Java基础类之集合框架核心原理

Question

分析HashMap在Java 8中的实现原理，包括数据结构、哈希算法、扩容机制以及如何解决哈希冲突。

Answer 1

1. 数据结构

在Java 8中，HashMap的数据结构是数组 + 链表 + 红黑树。

• 数组：HashMap底层使用一个Node类型的数组table来存储数据。数组的每个元素是一个链表或红黑树的头节点。
• 链表：当发生哈希冲突时，新的元素会以链表的形式存储在数组对应位置。链表采用单向链表结构。
• 红黑树：当链表长度大于等于8且数组长度大于等于64时，链表会转化为红黑树，以提高查找效率。当红黑树节点数量小于6时，又会退化为链表。

2. 哈希算法

HashMap的哈希算法主要通过hashCode()方法和indexFor()方法（Java 8中为(n - 1) & hash）来确定元素在数组中的位置。

• 首先调用对象的hashCode()方法获取哈希码。
• 然后对哈希码进行扰动处理，HashMap的hash方法通过对哈希码进行位运算，使哈希值更均匀地分布，减少哈希冲突。例如：

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

• 最后通过(n - 1) & hash（n为数组长度）计算出元素在数组中的索引位置。这种计算方式利用了位运算的高效性，且能保证索引值在数组范围内。

3. 扩容机制

• 触发条件：当HashMap中的元素个数（size）超过阈值（threshold）时，就会触发扩容。阈值threshold = capacity * loadFactor，其中capacity是当前数组的容量，loadFactor是负载因子，默认值为0.75。
• 扩容过程：扩容时，新的容量是原来容量的2倍。然后重新计算每个元素在新数组中的位置，并将原数组中的元素重新分配到新数组中。这是一个比较耗时的操作，因为需要重新计算哈希值和索引位置。例如：

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;
            if (e.next == null)
                newTab[e.hash & (newCap - 1)] = e;
            else if (e instanceof TreeNode)
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
            else { // 链表优化重定位
                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 & oldCap) == 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 (loTail != null) {
                    loTail.next = null;
                    newTab[j] = loHead;
                }
                if (hiTail != null) {
                    hiTail.next = null;
                    newTab[j + oldCap] = hiHead;
                }
            }
        }
    }
}

4. 解决哈希冲突

• 链地址法：这是HashMap解决哈希冲突的主要方式。当不同的键计算出相同的哈希值时，这些键值对会以链表的形式存储在数组的同一个位置。新的元素会被添加到链表的头部（Java 7及之前）或尾部（Java 8）。
• 红黑树优化：当链表长度过长（大于等于8且数组长度大于等于64）时，链表会转化为红黑树。红黑树是一种自平衡的二叉搜索树，相比于链表，它的查找、插入和删除操作平均时间复杂度为O(log n)，在处理大量冲突时效率更高。当红黑树节点数量小于6时，又会退化为链表，因为链表在节点数量较少时性能更好。