关于hashmap的一点笔记

https://www.bilibili.com/video/BV1nJ411J7AA

hashmap扩容

扩容之后的节点要么在原来的位置，要么就被分配到“原位置+旧容量”这个位置，原因是重新计算的位置=（n-1）&hash, 扩容之后（n-1）从二进制来看只是右边多了一个为1的bit位，如果hash对应的这个bit位是0那就是原位置，如果是1那就是原位置+旧容量。可以用一张图来说明。

hashmap链表转红黑树的条件

1. 数组长度大于64
2. 链表长度大于8

hashmap链表和红黑树互转的阈值

表转树的阈值是8，树转表的阈值是6

hashmap的resize()方法总结

resize()方法的作用是扩容，大致流程如下:

1. 计算出新的容量和扩容阈值
2. new一个新的数组
3. 遍历旧数组
4. 如果该元素没有next, 直接放到新的数组；如果是树节点，拆分树节点；剩下最后一种情况就是链表，那就遍历链表，按照之前的计算方法，形成新的两条链表。一条的索引位置是原数组的索引位置，另一条的索引位置是（原数组索引位置+旧数组容量）的位置。最后将这两条链表的头结点分别挂在数组中。

hashmap的get()方法总结

1. 通过hash值获取该key映射的桶
2. 如果桶上的key就是要查找的key, 则直接找到并返回
3. 如果桶上的key不是要找的key, 则查看后续的节点：
   a. 如果后续节点时红黑树节点，调用红黑树的方法根据key获取value
   b. 如果后续节点时链表节点，循环遍历链表根据key获取value
4. 红黑树查找，如果对比节点的hash值和要查找的hash值相等，就会判断key是否相等，相等就直接返回，不相等就从子树中递归查找
5. 树的查询复杂度是O(logn), 链表的查询复杂度是O(n)