hashmap 原理

image.png

HashMap在面试中经常会被问到，一定会问到它的存储结构和实现原理，甚至可能还会问到一些源码

今天就来看一下HashMap

首先得看一下HashMap的存储结构和底层实现原理

image

如上图所示，HashMap底层是用数组+链表+红黑树实现的，其中红黑树是JDK1.8对HashMap优化之后加入的，当链表的长度大于8的时候会由链表结构转为红黑树，这些等下在看源码分析的时候都可以看到具体的实现。

那为什么用这几种数据结构来实现？

这种结构在数据结构上称为散列链表，其中的数组就相当于一个一个的桶(Bucket)，当有数据准备存进去的时候，它会通过一定的散列算法去计算，尽可能的让数据平均的命中到各个桶上面去，尽可能的避免哈希碰撞。如果发生哈希碰撞，就是不同的数据最后落到了同一个桶上的时候，就采用链表的方式来存储，但是链表长度比较长了的时候，去存储数据，读取数据都需要不停的去遍历循环，所以此时再采用链表结构的话效率会明显下降，所以JDK1.8之后做了优化，当链表的长度大于8的时候就由链表转为红黑树来存储。红黑树是平衡二叉树的其中一种实现，它比普通的二叉树表现更优异，因为普通的查询二叉树在一定条件下也可能会变成链表结构，而红黑树它是平衡二叉树的一种，它是通过左旋右旋变色等保持树的平衡。

简单的了解了HashMap的存储结构后，下面来讲下HashMap其中三个方法的源码

一、hash()方法

image.png

这个方法里看似简单，却暗藏玄机。

它是拿到了key本身的hashCode后，又做了一次运算，先将原来的hashCode无符号右位移16位，然后再将原来的hashCode异或(^)上这个位移后的值，最后得到一个值。

补充知识：

表示右移，如果该数为正，则高位补0，若为负数，则高位补1。

表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0。

^ 表示异或运算，每个位相同为0，不同为1

比如：

0 ^ 1 得 1
1 ^ 1 得 0
0 ^ 0 得 0
1 ^ 0 得 1

那为什么要无符号右移16位后做异或运算？key本身的hashCode直接拿来用不好吗？

我们做一个简单演练

image

将h无符号右移16为相当于将高区16位移动到了低区的16位，再与原hashcode做异或运算，可以将高低位二进制特征混合起来

从上文可知高区的16位与原hashcode相比没有发生变化，低区的16位发生了变化

我们可知通过上面(h = key.hashCode()) ^ (h >>> 16)进行运算可以把高区与低区的二进制特征混合到低区，那么为什么要这么做呢？

我们都知道重新计算出的新哈希值在后面将会参与hashmap中数组槽位的计算，计算公式：(n - 1) & hash，假如这时数组槽位有16个，则槽位计算如下：

image

仔细观察上文不难发现，高区的16位很有可能会被数组槽位数的二进制码锁屏蔽，如果我们不做刚才移位异或运算，那么在计算槽位时将丢失高区特征

也许你可能会说，即使丢失了高区特征不同hashcode也可以计算出不同的槽位来，但是细想当两个哈希码很接近时，那么这高区的一点点差异就可能导致一次哈希碰撞，所以这也是将性能做到极致的一种体现

使用异或运算的原因

异或运算能更好的保留各部分的特征，如果采用&运算计算出来的值会向1靠拢，采用|运算计算出来的值会向0靠拢

为什么槽位数必须使用2^n

1、为了让哈希后的结果更加均匀

这个原因我们继续用上面的例子来说明

假如槽位数不是16，而是17，则槽位计算公式变成：(17 - 1) & hash

image

从上文可以看出，计算结果将会大大趋同，hashcode参加&运算后被更多位的0屏蔽，计算结果只剩下两种0和16，这对于hashmap来说是一种灾难

2、可以通过位运算e.hash & (newCap - 1)来计算，a % (2^n) 等价于 a & (2^n - 1) ，位运算的运算效率高于算术运算，原因是算术运算还是会被转化为位运算

说了这么多点，上面提到的所有问题，最终目的还是为了让哈希后的结果更均匀的分部，减少哈希碰撞，提升hashmap的运行效率

作者：Java程序猿呀
链接：https://www.jianshu.com/p/53a8667da67b
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。