HashMap 树化

HashMao默认参数

默认大小为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时退化为链表,中间数是为了过度使用,防止链表与红黑树之间频繁的转换,造成效率低下。


理解不深,多方参考,质疑就是你对!

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容