深入剖析 Java HashMap：从数组、链表到红黑树，探秘高效数据结构背后的设计理念
Java HashMap 作为一种常用的数据结构，以其高效的键值对存储和检索能力著称。其内部设计精妙，巧妙地融合了数组、链表和红黑树三种数据结构，并在性能和空间成本之间取得了良好的平衡。本文将深入 HashMap 的内部机制，为您详细解读其设计理念，并分析其在不同场景下的性能表现。
一、数组：构建 HashMap 的基石
HashMap 使用数组作为其底层数据结构，所有键值对都存储在这个数组中。为了方便后续的讨论，我们将数组中的每个位置称为一个“桶”(bucket)。
1. 初始容量与扩容机制：
- 初始容量: HashMap 的默认初始容量为 16，这意味着它在创建之初会分配一个大小为 16 的数组。
- 加载因子: 除了初始容量，HashMap 还有一个重要的参数叫做“加载因子”(load factor)，默认值为 0.75。加载因子表示 HashMap 的数组中元素数量达到容量的百分之多少时进行扩容。
- 扩容过程: 当 HashMap 中的元素数量超过“加载因子 * 当前容量”时，就会触发扩容机制。扩容过程包括以下步骤：
- 创建一个新的数组，其容量是原数组的 2 倍。
- 将原数组中的所有元素重新计算哈希值，并根据新的哈希值将它们迁移到新数组中。这个过程称为“rehashing”。
为什么要将数组长度设计为 2 的幂？
这是为了优化 HashMap 中的关键操作：确定键值对在数组中的存储位置。当数组长度是 2 的幂时，可以通过高效的位运算来实现取模运算，从而快速定位键值对所在的桶。
具体来说，假设数组长度为 length (2 的幂)，hash 是键的哈希值，那么键值对在数组中的索引可以通过以下公式计算：
index = hash & (length - 1)
由于 length 是 2 的幂，(length - 1) 的二进制表示中，从最低位到长度位都是 1。因此，hash & (length - 1)