前言
在说HashMap之前,我们先说一说hash冲突。当数据通过hash算法求得hash值的时候,是不可避免的出现相同的hash值,这也叫做hash冲突。通常我们会采用4种方式去应对hash冲突的情况。
HashMap的简介
HashMap是基于映射(键值对)处理的数据数据结构。是程序员使用的频率最高的数据结构之一,在jdk1.8之后引入红黑树,优化底层数据结构。
传统的数据的数据结构是在内存中申请一段连续的内存空间,查询的时间复杂度为O(1),而插入和删除是O(n),这是因为伴随着数据的移动。
在Java7中数组+链表的形式,一旦链表过长那么会很影响put和get的效率,所以在Java8之后引入了红黑树+链表来代替链表。
为什么不一直使用链表?
我们是很清楚链表的弊端的,就是查询的效率很低,是O(n),当数据量很大的时候是不能接受这样的查询效率的。在JDK1.8之前它的结构大概是这样的
所以会一直花费心思在扰动函数上,让hash的更加分散。
为什么选择红黑树?
我们通过比较几种树的特性来说为什么选择了红黑树。
二叉查找树
我们最常见的就是二叉查找树,它的特点就是左节点永远都比它的父节点小,右节点一定比它的父节点大,比如下图
但是它有个很大的问题,就是容易瘸腿,比如下面
当瘸腿的时候,你会发现这和链表没啥区别了。然后就出现了下面这个树。
平衡二叉树
这个树的特性就是每一个节点的左子树和右子树的高度差至多等于1,如果大于1就需要进行左旋或者右旋,这样就保证了它的查询的时间复杂度始终保持在O(LogN)。如下图
虽然查询满足了我们的需求,但是它的问题是在插入和删除的时候维护树上面复杂很多,需要频繁的调整树结构来保证查询效率,所以就引申出了红黑树
红黑树
相对于平衡二叉树,它的特点如下
- 根节点是黑色的。
- 所有的叶子节点都是黑色的,并且不存数据。
- 任何相邻的节点不能同时为红色,红色节点是被黑色节点隔开的。
- 每个节点到达它可达的叶子节点的路径,都经过相同数目的黑色节点。
主要优点就是:它不追求绝对的平衡,插入最多两次旋转,删除最多三次旋转。
具体的实现我会单独的放到我数据结构专栏,太复杂了。。。
HashMap什么时机会从链表转为红黑树?什么时候再转回来呢?
在上面我说了,JDK1.8之后是链表+红黑树来替代的链表,组合的意思就是代表着这两种数据结构是需要切换的,这个时机就是链表长度到达8的时候进行切换,当然这个只是条件之一,还有一个条件是想转换为红黑树,table中,也就是hash表的横向容量必须达到64,否则就会优先resize
hash表。等讲完resize的方法的时候再总结一下HashMap中的存储数据的结构。所以就引出一些疑问。
为什么不在hash冲突的时候直接就使用红黑树呢?
因为红黑树的空间是链表的两倍,虽然能提升查询效率,但是插入的速度慢了很多,还涉及到平衡树的时候的各种旋转变色,所以链表其实是起到一个缓冲的作用。
为什么要到达8的时候转为红黑树呢?
原文注释上说,当hashCode遵循泊松分布的时候,因为hash冲突造成桶的的链表长度等于8的概率只有0.00000006。官方认为这个概率足够低,当需要红黑树介入的时候,你可以想象一下你的数据会是什么样的。
什么时候从红黑树转为链表呢?
当红黑树节点小于6的时候就会转回来,为什么是6呢,首先不能是8,因为如果是8的话,你会面临着频繁的链表与红黑树的切换,就让我想起了那句台词,我进来了,我出来了,我又进来了,我又出来了。。。。而选择6不选择7是因为,官方经过大量的验证,发现,当红黑树节点小于6的时候,它的优势就不那么明显了,不足以抵消维护红黑树的开销,之前听过一个大哥这么说的,经过工业严谨的实验证明,6在绝大多数的情况下表现良好。
所以我们可以看出,作者在链表转为红黑树这里考虑的非常多,就是要让两种结构达到一个均衡点,过于草率的进行结构转换的话,其实非常的影响效率。
从源码入手解析HashMap工作原理
接下来我会从源码开始一步一步引申出对HashMap的一些疑问。
我们先看一下HashMap中比较重要的一些属性,我的注释会解释相关含义
HashMap中的重要属性介绍,以及一些疑问
//默认的初始容量,1向左移动4位10000=16
static final int DEFAULT_INITIAL_CAPACITY = 1 > 16);
}
看三元表达式的后半部分就可以了。(h = key.hashCode()) ^ (h >>> 16)
。用key的hashCode去异或hashcode向右移16位。接着提出几点疑问
为什么要选择异或运算,而不是与运算和或运算?
与运算的方式是同为1则为1,否则为0。或运算是有1则为1,否则为0。异或是不同为1,相同为0。这样一对比其实就能发现与运算的结构更向0靠拢,或运算的结果更向1靠拢,而异或运算更加平均。公平起见,选异或。
为什么要让hashcode异或hashcode右移16位?
首先我们要知道的是hashcode是int类型,所以占4个字节32位,hash方法可以认为是对key本身的hashcode进行二次加工,这其实和HashMap计算key的位置的方式有关系的,确定位置在putVal
的方法中,为了不搞乱,我单独把它拿出来了,如下,看一下它计算位置的方式i = (n - 1) & hash
,n就是hash表的长度,用长度-1然后去&hash,看着挺难懂的,其实它就等于hash%n。当然这个前提是n得是2的幂次方。因为基于&的方式去计算,要快于十进制%的计算方式很多。所以这也解释了为什么容量要设置成2的幂次倍,就是采用取模的方式取址,还要提升计算速度!
再回来说为什么要右移16位。举个例子:你的hashcode是1111110001然后&1111,等于=0001,然后下一个hashcode和上一个只是发生了高位的变化,比如1100110001然后&1111,结果其实还是0001,那就会导致计算出来的地址都一样,类似这种情况那大家不都在一个桶里了吗,当长度较低的时候,只有hashcode的低16位参与运算了,所以没有选择用hash直接计算地址,向右移动16位相当于让高位下来了,然后再去异或hashcode,相当于高低位结合了,也就提升了hash值的散列程度。
为什么负载因子要设置成0.75?为什么不设置成1呢?
设置成1的话就代表着,只有table装满了的时候才会去扩容,这时候所有键的hash都需要重新计算,这比较损耗性能,同时,这也会导致冲突的hash比较多。所以既不能频繁的扩容,也不能太晚的扩容,所以0.75是一个很均衡的值,而且0.75也就是四分之三,用table的长度去乘这个负载因子得出来的数就是扩容的阈值,而0.75刚好使得这个阈值是一个整数,因为上面我们提到的,容量是2的幂次倍。
那么说完为什么容量要设置成2的幂次倍了,我们再说一下它是怎么保证的
其实就是和构造方法相关了,在这里我就直接写了,对后面看构造函数的源码也是有帮助的,它的构造方法中有个非常关键的方法就是tableSizeFor
,这个方法就是重新计算容量的,即便你重新传了初始容量,也要计算得出真实容量,我们看一下源码的实现
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
整个过程就是为了找到传入容量最近的大于它的一个2次幂的值,下面是我根据上面的算法写的几个例子
从例子中就可以很清楚的看出来为什么要传入的容量-1去计算。
接下来,我接着走源码,看看构造方法是怎么样的逻辑
HashMap的构造方法的工作流程解析
它的构造方法有四个,我这里只解析其中一个,如下
//参数位Map的构造函数,看过这个的解析,那么,其他三个一看就明白了
public HashMap(Map