HashMap的底层数据结构是什么？

JDK 8 中 `HashMap` 的底层数据结构确实经过了优化，主要采用了“数组 + 链表 + 红黑树”相结合的形式，以应对哈希冲突，提升查询性能。详细说明如下： ### 1. **数组** - `HashMap` 的主体结构仍然是一个数组，数组的每个元素称为“桶”。 - 当我们插入键值对时，通过哈希函数计算出键的哈希值，进而确定应该插入到哪个桶中。 ### 2. **链表** - 在哈希冲突的情况下，如果多个键的哈希值相同（或映射到同一个桶中），这些键值对会通过链表的方式存储在同一个桶中。 - 链表的插入时间复杂度为 O(1)，但查找时间复杂度为 O(n)，当链表较长时，查找性能会明显下降。 ### 3. **红黑树** - 为了优化链表过长导致的性能下降，JDK 8 中引入了红黑树，当同一个桶中的链表长度超过 8 时，链表会自动转换为红黑树。红黑树的查找时间复杂度为 O(log n)，极大地提升了性能。 - 但这种转换有一个前提：如果此时 `HashMap` 的数组大小小于 64，则不会立即将链表转换为红黑树，而是优先进行数组扩容。这是因为扩容有可能将链表中的数据重新分布到不同的桶中，从而降低链表长度。 ### 关键代码分析： 1. **链表转红黑树的条件** - 当链表长度大于或等于 `TREEIFY_THRESHOLD`（其值为 8）时，触发链表向红黑树的转换： ```java if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); ``` 2. **数组扩容优先于红黑树转换** - 在 `treeifyBin` 方法中，当 `HashMap` 的数组大小小于 `MIN_TREEIFY_CAPACITY`（其值为 64）时，首先选择扩容： ```java final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); } ``` ### 总结：  - **JDK 7** 中，`HashMap` 的底层数据结构是“数组 + 链表”。 - **JDK 8** 引入了“数组 + 链表 + 红黑树”的结构，链表长度超过 8 且数组大小大于等于 64 时，链表会转换为红黑树，从而提升查找性能。