首页  思维导图  详情

HashMap知识点

2022-11-07 11:02:42   0  举报





AI智能生成

HashMap脑图、HashMap知识点、HashMap面试

HashMap脑图

HashMap知识点

HashMap面试

作者其他创作

大纲/内容

1、数据结构-散列表

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

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

哈希函数

直接定址法

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

平方取中法

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

折叠法

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

数字分析法

找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址

✅ 除留取余法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即 H(key) = key MOD p, p ≤ m 这是一种最简单，也最常用的构造哈希函数的方法。它不仅可以对关键字直接取模（MOD），也可以在折叠、平方取中等运算之后取模。

哈希碰撞

✅ 拉链法

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

散列法

开放地址法

又叫再散列法

有一个通用的再散列函数形式：Hi=(H(key)+di)%m i=1，2，…，n,
其中H（key）为哈希函数，m 为表长，di称为增量序列

线性探测再散列

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 = 总键值对数 / 哈希表总长度

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做扩容操作可能会导致一个线程以另一个线程扩容完的逆序链表进行顺序操作，导致循环链表的产生，具体可找对应的文章查看

环形链表产生可看视频

为什么在JDK1.8中进行对HashMap优化的时候，把链表转化为红黑树的阈值是8,而不是7或者不是20呢？

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

6、如果是链表，遍历链表，并将链表节点按原顺序进行分组（hash&oldcap == 0, 判断是在原位置，还是扩容之后位置）

7、删除

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