HashMap是在面试中经常会问的一点,很多时候我们仅仅只是知道HashMap他是允许键值对都是Null,并且是非线程安全的,如果在多线程的环境下使用,是很容易出现问题的。 这是我们通常在面试中会说的,但是有时候问到底层的源码分析的时候,为什么允许为Null,为什么不安全,这些问题的时候,如果没有分析过源码的话,好像很难回答, 这样的话我们来研究一下这个源码。看看原因把。
HashMap最早出现在JDK1.2中,它的底层是基于的散列算法。允许键值对都是Null,并且是非线程安全的,我们先看看这个1.8版本的JDK中HashMap的数据结构把。
HashMap图解如下
我们都知道HashMap是数组+链表组成的,bucket数组是HashMap的主体,而链表是为了解决哈希冲突而存在的,但是很多人不知道其实HashMap是包含树结构的,但是得有一点 注意事项,什么时候会出现红黑树这种红树结构的呢?我们就得看源码了,源码解释说默认链表长度大于8的时候会转换为树。我们看看源码说的
结构
1 |
|
接下来就是树结构了
TreeNode 是红黑树的数据结构。
1 |
|
我们在看一下类的定义
1 |
|
继承了抽象的map,实现了Map接口,并且进行了序列化。
在类里还有基础的变量
变量
1 |
|
我们再看看构造方法
构造方法
1 |
|
在这源码中,loadFactor负载因子是一个非常重要的参数,因为他能够反映HashMap桶数组的使用情况, 这样的话,HashMap的时间复杂度就会出现不同的改变。
当这个负载因子属于低负载因子的时候,HashMap所能够容纳的键值对数量就是偏少的,扩容后,重新将键值对 存储在桶数组中,键与键之间产生的碰撞会下降,链表的长度也会随之变短。
但是如果增加负载因子当这个负载因子大于1的时候,HashMap所能够容纳的键值对就会变多,这样碰撞就会增加, 这样的话链表的长度也会增加,
一般情况下负载因子我们都不会去修改。都是默认的0.75。
扩容机制
resize()这个方法就是重新计算容量的一个方法,我们看看源码:
1 |
|
所以说在经过resize这个方法之后,元素的位置要么就是在原来的位置,要么就是在原来的位置移动2次幂的位置上。 源码上的注释也是可以翻译出来的
1 |
|
所以说他的扩容其实很有意思,就有了三种不同的扩容方式了,
-
在HashMap刚初始化的时候,使用默认的构造初始化,会返回一个空的table,并且 thershold为0,因此第一次扩容的时候默认值就会是16. 同时再去计算thershold = DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY = 16*0.75 = 12.
-
如果说指定初始容量的初始HashMap的时候,那么这时候计算这个threshold的时候就变成了 threshold = DEFAULT_LOAD_FACTOR * threshold(当前的容量)
-
如果HashMap不是第一次扩容,已经扩容过了,那么每次table的容量和threshold也会变成原来的2倍。
之前看1.7的源码的时候,是没有这个红黑树的,而是在1.8 之后做了相应的优化。 使用的是2次幂的扩展(指长度扩为原来2倍)。 而且在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,这样子他就剩下了计算hash的时间了。
看完这个源码,翻译了一节节的英文,算是大致明白了一点源码内容了,有什么讨论的问题咱们可以一起讨论一下,感谢观看。