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

hashmap

put方法

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

为什么hashmap长度为16

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

get方法

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

为什么选择红黑树

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

红黑树特征：

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