java8 hashmap 的几点细节

前言

哈希表是存储不连续主键的数据结构,如果主键是连续的,如[1,100],可以直接将主键作为下标用数组存放。但是很多情况主键不是连续的,或者值很大,如学号(2013201320),就要用哈希表存储。哈希表也是数组,只是存放时不是直接将主键作为下标,先通过散列函数计算应该放的位置,如:n=k%m,其中k是主键值,m是哈希表长度(数组长度),n为应该存放的位置。这样,n一定小于m,不会数组越界。但是可能发生冲突,即两个k计算的n一样,这样就需要有解决哈希冲突的策略。当需要查询时,先经过散列函数计算位置,如果主键值不是我们想要的,需要按照散列冲突去寻找主键。好的散列函数需要将主键在数组中分布的尽量均匀,一般数组长度取2的n次幂周围的素数

HashMap 是很常用的集合类,用于存储键值对(Node)。jdk1.7中hashmap用数组和链表实现,可是链表的查询效率低;在jdk1.8中hashmap使用数组+链表+红黑树的形式实现,当链表长度大于8时,会转成红黑树,提高了查询效率:O(n)到O(lgn),本文对jdk1.8中hashmap实现中的几个有意思的细节进行叙述

如何计算 key 的hash值

由于key任意类型,要先将key变成int型。作法为:key.hashcode()的高16位与低16位的异或运算值,这样利用了所有位上的数字,使分布更均匀

hash

图中>>>符号为无符号右移,>>为带符号右移

冲突时怎么办

有了key的hash值,就可以用散列函数计算下标,如果下标处没有存Node,直接存在数组中,如果已有Node,则以链表的形式向后遍历,如果遍历过程中没有遇到相同 key 的,在链表最后插入Node,如果插入Node时链表长度大于等于8,要将链表转红黑树;如果遇到相同的key,则将新的 value 替换旧的 value

为什么hashMap数组的初始长度为2的幂

位运算代替取模运算

在哈希表中,为了使 key 分布尽量均匀,一般取 2n 周围的素数,而 jdk 中 hashmap 的数组初始长度为1<<4=16,还强调数组长度必须是2的幂。我们知道取模运算的效率很低,对于每个 key 的hash值都要做取模运算,这个代价是很大的。如果将数组长度取2n ,可以将取模计算转化为位运算,使得效率大大提高

对于一个 int 型数字 x,用32位字节存储,如10010110...01010111,对于 y=2n (n=4) 的二进制是00000000...00010000,则 x%y 只与 x 的二进制的后4位有关,与前面的数字无关,如何取到x的二进制的 后四位呢,即用x&0000...00001111,而0000...00001111=0000...00010000-1,总结为如下公式:

扩容时的重定位

当hashmap的数组已用容量到达总容量的3/4时,需要扩容为当前容量的2倍: 2n+1,这样,所有存放的对象都要根据 key 重新定位,不然查询的时候就取不到了啊。在重新计算定位数组下标时,假设原来数组长度为16= 24 ,扩容后为32= 25 ,则现在要取二进制后五位,多的只是倒数第五位,如果倒数第五位为0,则扩容前后位置不变,如果倒数第五位为1,扩容后位置=扩容前位置+24

kuorong

您的支持鼓励我继续创作!