HashMap

HsahMap是我们常用的数据结构,jdk1.8前由数组和链表组合构成的数据结构,jdk1.8后由数组和链表还有红黑树构成,数组里面每个地方都存了Key-Value结构的实例,在java7中将Entry,在java8中叫node。在进行put操作的时候会根据插入数据的Key的hash值进行index的确定,当进行put操作时有可能出现hash碰撞,所以这时的值就会和index上的值形成链表,hash进行存值时的每一个节点都会保存自身的hash、key、value、以及下个节点,我看看Node的源码。

新的Entry节点在插入链表的时候,是怎么插入的么?

jdk1.8前使用的是头插法,就是说新来的值会取代原有的值,然后原有的值会顺推到链表中,但是在jdk1.8后就采用了尾插法。因为数组的容量有限的,在达到一定的数量之后就会进行resize,就是进行扩容,进行扩容的时机与数组当前的长度和负载因子有关,一般默认的负载因子是0.75,就比如当前容量是100,当你存入第76个时就学要进行resize,进行扩容,但是HashMap进行扩容不是简单的扩大容量那么简单,

扩容的步骤:

第一步,扩容创建一个新的Entry空数组,长度是原数组的2倍。

第二部,进行ReHash,遍历原Entry数组,把每一个Entry重新Hash到新数组中,

为什么要重新Hash呢,直接复制过去不好么?

要进行ReHash的原因是因为数组的长度变了Hash的规则也随之改变,

hash的算法是 index = Key 的 hsahcode & (lenght-1)

为什么1.8改用尾插法:

因为resize的赋值方式,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置,在旧数组中同一条Entry链上的元素,通过重新计算索引位置后,有可能被放到了新数组的不同位置上。这就与可能会产生链表循环。

那我问你HashMap的默认初始化长度是多少?

我记得我在看源码的时候初始化大小是16,因为这样是为了位运算的方便,位与运算比算数计算的效率高了很多,之所以选择16,是为了服务将Key映射到index的算法

上一篇:nginx配置详解


下一篇:数据结构之哈希表