doc/面经/问答/集合.md

hashmap

put方法

​ 该方法首先会判断hashmap的数组是否被初始化，如果没有初始化，则首先进行初始化操作。其次判断该key是不是null，如果为null则在数组下标为0的地方进行插入操作，如果不为null，则进行下一步判断。 ​ 如果数组该位置为null，则新建一个node，进行插入，如果不为null，则采用头插法插入元素，如果链表长度大于8，并且数组长度大于64，则将链表转换为红黑树。如果小于64则直接扩容

为什么hashmap长度为16

• 减少hash冲突
• 每次扩容只用移动一半的元素

这是因为hashmap缓存了key的hash值，每次移动元素只需要新的高位与1相与就行。

get方法

判断该元素时候为空，如果为空直接返回，如果不为空则返回value

为什么选择红黑树

红黑树相比avl树，在检索的时候效率其实差不多，都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡，他允许局部很少的不完全平衡，这样对于效率影响不大，但省去了很多没有必要的调平衡操作，avl树调平衡有时候代价较大，所以效率不如红黑树。

Java 中的 HashMap 底层原理使用数组和链表/红黑树实现，而不使用 B 树，原因有以下几点：

1. 红黑树的查找、插入、删除操作复杂度相对稳定，不会像 B 树 那样随着树高逐渐变差，平均时间复杂度为 O(log n)。B 树虽然有更快的查找速度，但在 Java 中，HashMap 的数据量一般都在1K以下，单机内存完全可以满足红黑树的需求。
2. 空间利用率方面，B 树中非叶子节点需要存储下一级节点的指针，因此每个节点占用的空间相对较大，而红黑树只需要保存左右子节点和父节点的指针，所以相对来说更加节省空间。
3. 红黑树相对于 B 树 更容易实现。
4. 在实际应用中，虽然B树比红黑树有更优异的性能表现，但其实现比较复杂，在使用时需要结合具体场景来考虑。相比之下，红黑树实现简单，维护成本低，且平均情况下的性能也能够满足HashMap的需求，因此选择红黑树作为HashMap的底层数据结构更为合适。

综上所述，HashMap 选择红黑树而不是 B 树 作为其底层数据结构，主要是出于对效率和实现的考虑。

红黑树特征：

1. 每个节点或者是黑色，或者是红色。
2. 根节点是黑色。
3. 每个叶子节点（NIL）是黑色。
4. 如果一个节点是红色的，则它的子节点必须是黑色的。
5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。