(1)底层数据存储结构是数组+链表+红黑树
(2)数组的默认长度为16
(3)负载因子为0.75,也就是说当使用容量达到总长度的四分之三时,触发扩容,新的数组长度为原数组长度的2倍。
(4)当key发生hash碰撞时,产生链表。当链表的长度大于8并且数组长度大于64时,产生红黑树。
(5)容量小于64,链表长度大于等于8也会触发一次扩容。
1,初始容量只是哈希表在创建时的容量。
2,加载因子其实是用来判断当前HashMap<K,V>中存放的数据量。
当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行扩容、rehash操作(即重建内部数据结构),扩容后的哈希表将具有两倍的原容量。hashmap初始化容量时候,对容量大小做的处理,保证初始化容量为最近的2的幂次方.
2的幂次方:hashmap在确定元素落在数组的位置的时候,计算方法是(n - 1) & hash,n为数组长度也就是初始容量 。hashmap结构是数组,每个数组里面的结构是node(链表或红黑树),正常情况下,如果你想放数据到不同的位置,肯定会想到取余数确定放在那个数组里,计算公式:hash % n,这个是十进制计算。在计算机中, (n - 1) & hash,当n为2次幂时,会满足一个公式:(n - 1) & hash = hash % n,**计算更加高效。(也是为了后面让元素均匀的分布在新数组中)**
奇数不行:在计算hash的时候,确定落在数组的位置的时候,计算方法是(n - 1) & hash,奇数n-1为偶数,偶数2进制的结尾都是0,经过hash值&运算后末尾都是0,那么0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大,**更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这样就会造成空间的浪费而且会增加hash冲突。**
如果加载因子比较大,扩容发生的频率比较低,浪费的空间比较小,发生hash冲突的几率比较大。比如,加载因子是1的时候,hashmap长度为128,实际存储元素的数量在64至128之间时间段比较多,这个时间段发生hash冲突比较多,造成数组中其中一条链表比较长,会影响性能。
如果加载因子比较小,扩容发生的频率比较高,浪费的空间比较多,发生hash冲突的几率比较小。比如,加载因子是0.5的时候,hashmap长度为128,当数量达到65的时候会触发扩容,扩容后为原理的256,256里面只存储了65个浪费了。
综合了一下,取了一个平均数0.75作为加载因子。当负载因子为0.75,时代入到泊松分布公式,计算出来长度为8时的概率=0.00000006,概率很小了,所以产生红黑树的概率也就很小。
以上两个例子证明了,*** 经过rehash之后,元素的位置要么是在原位置,要么是在原位置加原数组长度的位置。***
因为每次扩容会把原数组的长度*2,那么再二进制上的表现就是多出来一个1
比如原数组16-1二进制为0000 1111
那么扩容后的32-1的二进制就变成了0001 1111
再次扩容64-1就是0011 1111
既省去了重新计算hash值的时间,而且由于新增的1bit是0还是1,可以认为是随机的,*** 因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。 ***
什么时候发生Hash碰撞:
计算元素在数组的位置key的HashCode作为index.运算结果相同的两个对象就需要存储到同一个链表中
数组长度16:
默认容量太小了就有可能频繁发生扩容,影响效率。太大了又浪费空间,不划算
链表长度为8:
因为通常情况下,链表长度很难达到8,但是特殊情况下链表长度为8,哈希表容量又很大,造成链表性能很差的时候只能采用红黑树提高性能,这是一种应对策略