目录
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的性能和效率，而链表转红黑树的操作则是为了在特定情况下提供更好的查找、插入和删除元素的性能。
HashMap的长度为什么是 2的 N 次方
为了能让 HashMap 存数据和取数据的效率高，尽可能地减少 hash 值的碰撞，也就是说尽量把数
据能均匀的分配，每个链表或者红黑树长度尽量相等。我们首先可能会想到 % 取模的操作来实现。
下面是回答的重点哟：
取余（%）操作中如果除数是 2 的幂次，则等价于与其除数减一的与（&）操作（也就是说hash % length == hash &(length - 1) 的前提是 length 是 2 的 n 次方）。并且，采用二进制位操作 & ，相对于 % 能够提高运算效率。
这就是为什么 HashMap 的长度需要 2 的 N 次方了
最简回答：HashMap的长度选择为2的N次方是为了提高散列算法的效率和分布均匀性，通过使用2的幂次方作为长度，可以确保哈希码的高位和低位可以均匀参与到散列计算中，减少哈希冲突的发生，并提高散列算法的效率和性能。
)
