HashMap底层原理

JDK1.8及以后底层结构为：数组+链表+红黑树

默认参数

扩容机制

数组

链表

红黑树

HashMap为什么用红黑树不用B树

HashMap什么时候扩容

HashMap的长度为什么是 2的 N 次方

HashMap底层原理

JDK1.8及以后底层结构为：数组+链表+红黑树

HashMap是Java集合框架中一种基于哈希表实现的Map接口，它存储键值对，键是唯一的，而值可以重复。它的底层结构是一个数组结构，在实际情况中，这个数组被分为多个“桶（bucket）”，每个桶内存储的是链表或红黑树（JDK1.8中引入），具体使用哪种取决于链表的长度和当前Map的大小

默认参数
- 默认负载因子（load factor）：0.75。负载因子是衡量HashMap满的程度的一个标准。当HashMap中的元素数量达到容量与负载因子的乘积时，就会进行扩容。
- 默认容量（capacity）：16，必须是2的幂。
扩容机制
- 当HashMap中的元素数量达到threshold时，即当前容量乘以负载因子，HashMap会进行扩容操作。
- 扩容操作会创建一个新的数组，其大小为原数组大小的两倍，并重新计算每个键的哈希值和在新数组中的位置。
- 这个过程涉及到重新计算每个键的哈希值，并将所有的键值对重新插入到新的数组中，因此扩容是一个比较耗费性能的操作。
数组
- 作用：数组是HashMap存储元素的主要结构，每个数组元素是一个桶（bucket），可以存储一个或多个键值对（Entry）。
- 默认大小：默认初始容量为16（必须是2的幂）。
- 扩容机制：当HashMap中的元素数量达到容量与负载因子乘积时，即size >= threshold（threshold = capacity * load factor），数组会进行扩容操作，扩容为原来的两倍大小。

对于默认的容量和负载因子，threshold 的默认值是：
threshold = 16 * 0.75 = 12
这意味着当 HashMap 中的元素数量达到 12 时，HashMap 会进行扩容操作。扩容后的新容量是原容量的两倍为36，同时 threshold 也会相应地更新为新的容量乘以负载因子。

链表
- 作用：当数组的同一个桶位置（即索引相同）发生哈希碰撞时，多个键值对会以链表的形式存储。JDK 1.8之前，HashMap就是使用链表处理冲突；JDK 1.8之后，当链表长度大于一定阈值时，链表会转换为红黑树。
- 默认阈值：链表转红黑树的阈值为8（当链表长度大于8时，会转换为红黑树）。
红黑树
- 作用：为了提高HashMap的性能，当链表长度过长时，链表会被转换成红黑树。这样可以减少搜索时间，从O(n)降低到O(log n)。
- 默认阈值：链表转回链表的阈值为6（当红黑树中的节点数量小于6时，会转换回链表）。

HashMap为什么用红黑树不用B树

HashMap 使用红黑树（Red-Black Tree）而不是 B 树的主要原因是效率和复杂度。

效率：红黑树相对于 B 树，在插入、删除和查找操作上具有更好的平均性能。红黑树的平衡性质可以保证树的高度相对较小，从而减少了搜索的路径长度，提高了操作的效率。
复杂度：B 树是一种多路搜索树，节点可以包含多个关键字和指针，适合用于磁盘存储等场景，可优化磁盘 IO 操作。然而，在内存中的数据结构中，红黑树的实现更为简单，代码的复杂度较低。同时，红黑树的性能在典型的 HashMap 使用场景中通常表现出良好的性能。

另外，HashMap 维护了一个哈希表和一个链表或红黑树的混合结构（JDK8 之后），当发生哈希冲突时，会使用链表或红黑树来处理冲突。链表适合处理冲突较少的情况，而红黑树则适合处理冲突较多的情况。红黑树相对于链表具有更高的查找效率，因此在冲突较多的情况下能够提供更好的性能。

总之，HashMap 使用红黑树而不是 B 树主要是出于对效率和复杂度的考虑。红黑树在内存中的实现更简单，对于典型的 HashMap 使用场景能够提供良好的性能，且适用于处理冲突较多的情况。

最简回答：HashMap使用红黑树而不是B树，是因为红黑树相对于B树在插入、删除和查找等操作上的平衡性能更好，且红黑树的节点比B树的节点更小，占用的内存更少，适合存储在内存中的数据结构。

HashMap什么时候扩容

在JDK1.7中，当HashMap中元素数量超过当前容量与负载因子（默认为0.75）的乘积时，会触发扩容操作，扩容后的容量为当前容量的两倍。例如，初始容量为16，当元素数量达到12时会触发扩容，扩容后的容量为32。
在JDK 1.8中，HashMap的扩容和红黑树转换是两个独立的操作，且顺序是先扩容，然后再进行红黑树的转换。当HashMap中的元素数量超过负载因子（默认为0.75）与数组容量的乘积时，会触发扩容操作。扩容会重新调整数组的大小，并将原来数组中的元素重新分配到新的数组位置上。扩容操作会导致原本哈希冲突较多的链表长度变长，因此当链表长度超过阈值（默认为8）时，会将链表转化为红黑树。综上所述，在JDK 1.8中，HashMap的操作顺序是先扩容，然后再进行红黑树的转换。扩容是为了减少哈希冲突，提高HashMap的性能和效率，而链表转红黑树的操作则是为了在特定情况下提供更好的查找、插入和删除元素的性能。