HashMap知识点

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。

对其任意元素的查找速度始终为常数级，即O(1)

取关键字或关键字的某个线性函数值为哈希地址

直接定址法

取关键字平方后的中间几位为哈希地址

平方取中法

将关键字值分割成位数相同的几个部分，然后取这几部分的叠加和（舍去进位）作为哈希地址

折叠法

数字分析法

✅ 除留取余法

哈希函数

将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。

✅ 拉链法

又叫再散列法

di=1，2，3，…，m-1

线性探测再散列

di=1，-1，2，-2，…，k，-k    ( k<=m/2)

二次探测再散列

di=伪随机数序列

伪随机探测再散列

开放地址法

同时构造多个不同的哈希函数：Hi=RH1(key），i=1，2，3，…k当哈希地址Hi=RH1(key)发生冲突时，再计算Hi=RH2（key）…，直到冲突不再产生。这种方法不易产生聚焦，但增加了计算时间

再哈希法

散列法

若关键字所对应的哈希地址已被占用，则保存到公共溢出区中。一般在开辟地址的时候会产生哈希地址和公共溢出区两块

建立一个公共溢出区

哈希碰撞

装填因子 a = 总键值对数 /  哈希表总长度

负载因子

1、数据结构-散列表

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

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

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

如果实现找到最小值？

3、初始化容量

static final float DEFAULT_LOAD_FACTOR = 0.75f;

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

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

负载因子是做什么的？

4、负载因子

流程

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

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

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

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

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

环形链表产生可看视频

头插法和尾插法区别

5、插入数据

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

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、如果是红黑树，需要对红黑树进行拆分

过程

6、扩容

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

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

为什么需要退化？

7、删除

8、遍历

源码

使用了hashSeed

做了9次扰动处理 = 4次位运算 + 5次异或运算

JDK1.7

未在此处使用了hashSeed

简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算

JDK1.8

生成hash

单独一个indexFor方法

JDK1.8 内容一样 未封装方法

计算坐标

inflateTable

初始化

先判断是否key相同，相同则覆盖并返回旧值

单层循环，不仅遍历了数组同时遍历了链表

先判断是否需要扩容(size >= threshold) && (null != table[bucketIndex])

如果扩容，则需要重新计算index。如需要也可配置jdk.map.althashing.threshold(默认为int最大值)来重新计算hash

头插法

新增键值对(createEntry)

key不同则新增(addEntry)

resize

下标位置无元素则新增

变量替换，后面覆盖

key相同

putTreeVal

判断是否是树节点

先形成双向链表

do树化(hd.treeify)

树化(treeifyBin)

否则就是链表，尾插法

冲突处理

赋值

判断扩容

put流程

先扩容，再添加值

indexFor方法，要重新计算index （h & (length-1)）

transfer方法在多线程情况下会产生循环链表https://www.processon.com/diagraming/635cc7a2e0b34d77dbbe8d01

在addEntry方法中

先添加值，再扩容

resize方法，同时也是初始化方法

判断高低位(e.hash & oldCap) == 0

尾插法

利用Head、Tail高低位设计，对链表或者树进行拆分转移

扩容机制

单独方法inflateTable

同扩容方法resize放在一起

版本区别

HashMap知识点