转载

HASHMAP(JDK1.7)最详细原理分析(一)

公众号:大猪蹄子程序员

在JDK1.7中,HASHMAP是由数组+链表实现的,原理图如下:

HASHMAP(JDK1.7)最详细原理分析(一)
HashMap map = new HashMap(); // 伪初始化
map.put("键","值"); // 真初始化
复制代码

HashMap的构造方法在执行时会初始化一个数组table,大小为0。

HashMap的PUT方法在执行时首先会判断table的大小是否为0,如果为0则会进行真初始化,也叫做延迟初始化。

当进行真初始化时,数组的默认大小为16,当然也可以调用HASHMAP的有参构造方法由你来指定一个数组的初始化容量,但是注意,并不是你真正说了算,比如你现在想让数组的初始化容量为6,那么HASHMAP会生成一个大小为8的数组,如果你想数组的初始化容量为20,那么HASHMAP会生成一个大小为32的数组,也就是你想初始化一个大小为n的数组,但是HASHMAP会初始化一个大小 大于等于n的二次方数 的一个数组。至于为什么要这样,我们等会再说。

对于PUT方法,当无需对table进行初始化或已经初始化完了之后,它接下来的主要任务是将key和value存到数组或链表中。 那么怎么将一个keyvalue给存到数组中去呢?

我们知道,如果我们想往数组中存入数据,我们首先得有一个数组下标,而我们在进行PUT的时候并不需要再传一个参数来作为数组的下标,那么HASHMAP中下标是怎么获取来的呢?答案为哈希算法,这也是为什么叫HASHMAP而不叫其他MAP。

对于哈希算法,了解过的人应该都知道它需要一个哈希函数,这个函数接收一个参数返回一个HashCode,哈希函数的特点是对于相同的参数那么返回的HashCode肯定是相同的,对于不相同的参数,函数会尽可能的去返回不相同的HashCode,所以换一个角度理解,对于哈希函数,给不相同的参数可能会返回相同的HashCode,这个就叫哈希冲突或哈希碰撞。

那么我们能直接把这个HashCode来作为数组下标吗,另外一个很重要的问题是 我们到底应该对 key 做哈希运算还是对 value 做哈希运算,还是对 keyvalue 同时做哈希运算?

那么这个时候我们就要考虑到GET方法了,因为GET只需要传入一个key作为参数,而实际上GET方法的逻辑就是通过把key进行哈希运算快速的得到数组下标,从而快速的找到key所对应的value。 所以对于PUT方法虽然传入了两个参数,但是只能对key进行哈希运算得到数组下标,这样才能方便GET方法快速查找。

但是还有一个问题就是,HashCode它能直接作为数组下标吗?

HashCode它通常是一个比较大的数字,比如:

System.out.println("键".hashCode()); // 38190
// 为什么是这个结果,大家自行去看String类中的hashCode方法
复制代码

所以我们不可能把这么大的一个数字作为数组下标,那怎么办?

大家可能通常会想到取模运算,但是HashMap没有用取模,而是:

static int indexFor(int h, int length) {
	// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
	return h & (length-1);
}
复制代码

这个方法就是JDK1.7HashMap中PUT和GET方法中获取数组下标的方法(PUT和GET两个方法都要去获取下标?是的,如果你看到这里看不懂了,那么你再去想想上面的讲的提高GET方法效率的逻辑吧),这个方法中h代表hashcode,length代表数组长度。我们发现它是用的 逻辑与 操作,那么问题就来了,逻辑与操作能准确的算出来一个数组下标?我们来算算,假设hashcode是01010101(二进制表示),length为00010000(16的二进制表示),那么h & (length-1)则为:

h:  0101 0101
15: 0000 1111
  &
    0000 0101
复制代码

对于上面这个运行结果的取值方法我们来讨论一下:因为15的高四位都是0,低四位都是1,而与操作的逻辑是两个运算位都为1结果才为1,所以对于上面这个运算结果的高四位肯定都是0,而低四位和h的低四位是一样的,所以结果的取值范围就是h的低四位的一个取值范围:0000-1111,也就是0至15,所以这个结果是符合数组下标的取值范围的。

那么假设length为17呢?那么h & (length-1)则为:

h:  0101 0101
16: 0001 0000
  &
    0001 0000
复制代码

当length为17时,上面的运算的结果取值范围只有两个值,要么是0000 0000,要么是0001 000,这是不太好的。

所以我们发现,如果我们想把HashCode转换为覆盖数组下标取值范围的下标,跟我们的length是非常相关的,length如果是16,那么减一之后就是15(0000 1111),正是这种高位都为0,低位都为1的二级制数才保证了可以对任意一个hashcode经过逻辑与操作后得到的结果是我们想要的数组下标。 这就是为什么在真初始化HashMap的时候,对于数组的长度一定要是二次方数,二次方数和算数组下标是息息相关的,而这种位运算是要比取模更快的。

所以到此我们可以理一下:在调用PUT方法时,会对传入的key进行哈希运算得到一个hashcode,然后再通过逻辑与操作得到一个数组下标,最后将keyvalue存在这个数组下标处。

确定了keyvalue该存的位置之后,上文说过,对于不同的参数可能会得到相同的HashCode,也就是会发生哈希冲突,反应到HashMap中就是,当PUT两个不同的key时可能会得到相同的HashCode从而得到相同的数组下标,其实在HashMap中就算key所对应的HashCode不一样,那么也有可能在经过逻辑与操作之后得到相同的数组下标,那么这时HashMap是如何处理的呢?对,是链表,具体是怎么实现的呢?下篇文章继续吧。

相信大家不喜欢在小小的手机屏幕上还看到一大块的代码,阅读体验不好,所以我写作的风格会文字偏多一点。

原文  https://juejin.im/post/5cf3a11851882566477b7a02
正文到此结束
Loading...