HashMap设计问题

HashMap知识点

1、散列表实现

动态数组+链表+红黑树

2、扰动函数

实现

为什么使用扰动函数?

1.7和1.8区别

JDK1.7用了9次扰动处理=4次位运算+5次异或，而JDK1.8只用了2次扰动处理=1次位运算+1次异或至于为什么JDK1.8进行了缩减，可能是因为做多了离散分布提升不明显，还是为了效率考虑，进行了缩减

3、初始化容量

实现（寻找2的倍数最小值）

如果实现找到最小值？

1、向右移位1、2、4、8、16，这主要是为了把二进制的各个位置都填上1

2、当二进制的各个位置都是1以后，就是一个标准的2的倍数减1了，最后把结果加1再返回即可，这样就可以得到一个靠近初始容量的2的倍数最小值

4、负载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

负载因子是做什么的？

负载因子决定了数据量多少了以后进行扩容1、负载因子小，意味着会更容易扩容，同时碰撞率也更小，空间换时间2、负载因子大，意味着更不容易扩容，碰撞率会上升

0.75是个合理的值，默认值0.75就是说当阀值容量占了3/4时赶紧扩容，减少Hash碰撞

5、插入数据

流程

1.8 引入了红黑树，链表超过8同时数据长度大于64，会转换成红黑树，插入、删除、查找的最坏时间复杂度都为 O(logn)

注意：数据插入由1.7的头插法改成了尾插法

头插法和尾插法区别

1、JDK1.7是用单链表进行的纵向延伸，当采用头插法扩容时会容易出现逆序且环形链表死循环问题

2、JDK1.8之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题

3、多个线程同时对HashMap做扩容操作可能会导致一个线程以另一个线程扩容完的逆序链表进行顺序操作，导致循环链表的产生，具体可找对应的文章查看

环形链表产生可看视频

6、扩容

扩容元素拆分

问题：需要把元素拆分到新的数组中

jdk.8优化:拆分元素的过程中，原jdk1.7中会需要重新计算哈希值，但是到jdk1.8中已经进行优化，不在需要重新计算，提升了拆分的性能

如果实现的？

1、扩容之后一定是2的多少次幂2、由上图可知，扩容之后数据的位置要不在原始位置，要不在原始位置+旧容量3、同时可发现是否在哪个位置，可由扩容之后n-1二进制高位对应hash位上是1或者0判断4、if ((e.hash & oldCap) == 0)，通过hash值与旧容量（oldCap 高位为1，其余为0即1 0000）进行与运算，便可知高位是1还是0

什么情况下会扩容

1、数组长度小于64，同时某个链表长度大于8，这时会调用resize扩容

2、元素数量大于数组长度*0.75

过程

1、扩容时计算出新的newCap、newThr，这是两个单词的缩写，一个是Capacity ，另一个是阀Threshold

2、newCap用于创新的数组桶 new Node[newCap];

3、遍历hash表，扩容元素拆分可看上述描述

4、如果只有头节点，直接映射到扩容之后位置

5、如果是红黑树，需要对红黑树进行拆分

7、删除

红黑树，树节点小于6时发生退化

为什么需要退化？

考虑到内存（树节点比普通节点内存大2倍，以及避免反复转化），所以，退化阀值最多为6。

8、遍历