HashMap
发布日期:2022-02-17 07:12:02
浏览次数:1
分类:技术文章
本文共 856 字,大约阅读时间需要 2 分钟。
-
链表和树之间的转换
长度为8,链表转树,长度退变为6,树转链表。。中间有个差值,还可以防止链表和树频繁转换。假设8以上转为树,8以下转为链表,那么一个hashmap如果不停的插入删除,链表长度在8左右徘徊,就会不停的树转链表,链表转树,效率很低。
-
负载因子为什么是0.75
我们在考虑HashMap的时候,首先要想到的是HashMap只是一个数据结构,既然是数据结构最主要的就是节省时间和空间。负载因子的作用肯定也是节省时间和空间。为什么节省呢?我们考虑两种极端情况。 1、负载因子是1.0 我们的数据一开始是保存在数组里面的,当发生了Hash碰撞的时候,就是在这个数据节点上,生出一个链表,当链表长度达到一定长度的时候,就会把链表转化为红黑树。当负载因子是1.0的时候,也就意味着,只有当数组的8个值(这个图表示了8个)全部填充了,才会发生扩容。这就带来了很大的问题,因为Hash冲突时避免不了的。当负载因子是1.0的时候,意味着会出现大量的Hash的冲突,底层的红黑树变得异常复杂。对于查询效率极其不利。这种情况就是牺牲了时间来保证空间的利用率。
因此一句话总结就是负载因子过大,虽然空间利用率上去了,但是时间效率降低了。
2、负载因子是0.5
负载因子是0.5的时候,这也就意味着,当数组中的元素达到了一半就开始扩容,既然填充的元素少了,Hash冲突也会减少,那么底层的链表长度或者是红黑树的高度就会降低。查询效率就会增加。但是,兄弟们,这时候空间利用率就会大大的降低,原本存储1M的数据,现在就意味着需要2M的空间。
一句话总结就是负载因子太小,虽然时间效率提升了,但是空间利用率降低了。
3、负载因子0.75
经过前面的分析,基本上为什么是0.75的答案也就出来了,这是时间和空间的权衡。当然这个答案不是我自己想出来的。答案就在源码上,我们可以看看: 大致意思就是说负载因子是0.75的时候,空间利用率比较高,而且避免了相当多的Hash冲突,使得底层的链表或者是红黑树的高度比较低,提升了空间效率。
转载地址:https://blog.csdn.net/qq_42559485/article/details/115074999 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月04日 06时36分12秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Vue学习笔记之路由导航守卫
2019-04-30
Vue学习笔记之路由元信息
2019-04-30
Vue学习笔记之路由过渡动效
2019-04-30
Vue学习笔记之路由数据获取
2019-04-30
Vue学习笔记之路由滚动行为
2019-04-30
Vue学习笔记之路由懒加载
2019-04-30
Vue学习笔记之混入 (mixin)
2019-04-30
Vue学习笔记之自定义指令
2019-04-30
Vue学习笔记之Vuex学习---Vuex 是什么?
2019-04-30
Vue学习笔记之Vuex的核心概念State
2019-04-30
Vue学习笔记之Vuex的核心概念Getter
2019-04-30
Vue学习笔记之Vuex的核心概念Mutation
2019-04-30
Vue学习笔记之Vuex核心概念Action
2019-04-30
Vue学习笔记之Vuex的核心概念Module
2019-04-30
JavaScript数据结构与算法学习笔记之数组
2019-04-30
JavaScript数据结构与算法学习笔记之单链表
2019-04-30
JavaScript数据结构与算法学习笔记之双向链表(2)
2019-04-30
JavaScript数据结构与算法学习笔记之双向链表(1)
2019-04-30
JavaScript数据结构与算法学习笔记之双向链表(3)
2019-04-30
JavaScript数据结构与算法学习笔记之循环链表
2019-04-30