Java基础之HashMap(一)

1. 导读

今天分享的是不管是日常使用还是面试频率都很高的HashMap, 下面我就下面三个方面来分享个人对HashMap的理解:
.1 常用的hash算法以及解决冲突的方式;
.2 HashMap的数据结构是什么? 是怎么解决冲突的?
.3 HashMap::hash做了什么, 为什么这么做?

2. 常用的hash算法以及解决冲突的方式

2.1 hash: 意为散列, 但大多直接音译叫做哈希; 对于任意长度的输入, 经过hash算法的计算后, 返回一个固定的值, 该值就是hash值;

2.2 常见的hash算法:

2.2.1 直接定址法：直接以关键字k或者k加上某个常数（k+c）作为哈希地址;
2.2.2 数字分析法：提取关键字中取值比较均匀的数字作为哈希地址;
2.2.3 除留余数法：用关键字k除以某个不大于哈希表长度m的数p，将所得余数作为哈希表地址;
2.2.4 分段叠加法：按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址;
2.2.5 平方取中法：如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址;
2.2.6 伪随机数法：采用一个伪随机数当作哈希函数;

2.3 hash碰撞及解决办法:
hash碰撞是因为, 当不同值的输入, hash算法返回的值是相同的;

2.3.1 开放定址法: 开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入;
2.3.2 链地址法: 将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部;
2.3.3 再哈希法: 当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止;
2.3.4 建立公共溢出区: 将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中;

3. HashMap的数据结构是什么

HashMap的数据结构是分为两部分的:
.1 第一部分是上图左边的hash槽, 是以数组来来存放哈希码的;
.2 第二部部分是真正存放数据的数据节点, JAVA8以前是用链表来存储的, 但是JAVA8以后引入了红黑树;

看了上面的HashMap的数据结构图以后, 我们可以发现HashMap解决hash冲突的方法方法了:
.1 不同哈希码会分布在不同的hash槽, 这是第一步;
.2 如果同一个hash槽上有冲突, 那么就通过链表的方式来存储数据;

JAVA8以后, 当链表长度大于8时, 会转化为红黑树, 这种设计是因为当数据量变大时, 黑红树的树查找效率比链表高;一切向效率看齐;

4. HashMap::hash

HashMap::hash的作用是获取当前待插入节点位于哪个hash槽的方法;HashMap::hash做了三件事:
.1 判空; HashMap允许待插入节点的key为空, key为空则返回0;
.2 调用key自身的hashCode方法, 获取key自身的hashCode;
.3 将获取的hashCode右移16位, 再与原值进行异或, 返回结果;
HashMap::hash的核心是第三步, 我们来看看为什么这么做;
key.hashCode返回就是key的hash码, 他的值是int的取值范围是[-2^32, 2^32], 那么这么大的取值范围已经够用了, 为什么还要进行异或操作?
我们回到上面HashMap的结构图, 可以看到hash槽的长度是固定, 他的初始大小是16; 至于为什么初始值是16我们放到后面解答; 既然HashMap::hash的返回值过大, HashMap又做了一步计算来确定hash槽的地址:

这是JAVA7中真正确定hash槽的方法(JAVA8中移除了这个方法, 直接在put | get方法内计算了), 这个方法只做了一件事, 将HashMap::hash的返回值与当前hash槽的长度进行异或(因为JAVA中的数组是从0开始的, 所以这里的length减了1), 这种hash算法也是最常用的取余法, 可是上面明明进行了位与操作, 怎么会是取余呢? 其实取余操作在某些情况下能转换为位与操作的;我们用初始长度16, 待插入节点的hash值为21举例:

可以看到这时候的位与结果与取余结果是一样的, 但是位与操作的效率远比除法效率高, 故而HashMap::indexFor(1.7)采用了位与操作;
回到上个问题, 因为HashMap的hash槽初始值比较小, 那么当HashMap::hash返回值很大的时候会发生什么呢?
我们还是以初始值16举例:

可以发现虽然两次HashMap::hash的结果差距很大, 但是HashMap::indexFor的结果都是0, 我们数据离散的目的就不能实现了, 而究其原因就是高位没有参与运算;
所以为了解决这个问题, 我们只要让高位也参与运算好了, 因为int的长度是32位, 我们只要让高位的16位也参数运算就好了(这种方式我们前面在讲Long::hashCode时也说过, 证明底层思想有时候是互通的);

可以看到高位参与运算以后, h1.indexFor()的结果是 15, h2.indexFor() 的结果是 0, 我们数据离散的目的也就达到了;

这期先对HashMap做了一个初步的解析, 下期会再分享HashMap扩容机制以及其他问题的个人理解;如果内容有不足, 烦请指正;
如果本期对你有帮助, 烦请点赞并转发, 谢谢;