默认大小为16,装填因子为0.75,即当表中元素(size)大于16*0.75时,需要进行扩容。
与树化相关的几个参数为,TREEIFY_THRESHOLD =8,UNTREEIFY_THRESHOLD =6,MIN_TREEIFY_CAPACITY =64
TREEIFY_THRESHOLD
首先,TREEIFY_THRESHOLD = 8,表示的是当链表元素个数大于8时,会考虑将链表转换为红黑树。
这个8,是怎么来的呢?
“因为树节点的大小是链表节点大小的两倍,所以只有在链表中包含足够的节点才用它”,显然尽管转为树使得查找的速度更快 O(logN)「链表为 O(N) 」,但是在节点数比较小的时候,此时对于红黑树来说内存上的劣势会超过查找等操作的优势,自然使用链表更加好,但是在节点数比较多的时候,综合考虑,红黑树比链表要好。
理想情况下,在随机哈希码下,哈希表中节点的频率遵循泊松分布,而根据统计,忽略方差,列表长度为K的期望出现的次数概率在为8的时候概率就已经很小了。
通常如果 hash算法正常的话,那么链表的长度也不会很长,那么红黑树也不会带来明显的查询时间上的优势,反而会增加空间负担。所以通常情况下,并没有必要转为红黑树,所以就选择了概率非常小,小于千万分之一概率,也就是长度为8 的概率,把长度 8 作为转化的默认阈值。
MIN_TREEIFY_CAPACITY
当好多元素被映射到同一个桶时,即使当前桶内的元素个数已经超过TREEIFY_THRESHOLD(8),如果capacity小于MIN_TREEIFY_CAPACITY(64),链表存储也不会转化成树形结构存储,此时会对HashMap进行扩容;如果capacity大于了MIN_TREEIFY_CAPACITY ,才会进行树化。
举个例子来说的话,
初始情况下,hashmap 的capacity为16,因子为0.75。
当hashmap桶内元素小于等于8,且size小于12时,不进行扩容和树化的操作。
当hashmap桶内元素为9,因为capacity为16,因此不进行树化,而选择扩容,将capacity扩容为32。
当hashmap桶内元素为10,因为capacity为32,因此不进行树化,而选择扩容,将capacity扩容为64。
当hashmap桶内元素大于10,由于capacity已经达到64,此时进行树化。
UNTREEIFY_THRESHOLD
当链表长度大于8时转换为红黑树,小于6时退化为链表,中间数是为了过度使用,防止链表与红黑树之间频繁的转换,造成效率低下。
理解不深,多方参考,质疑就是你对!