jdk8重新认识hashmap

原创
2019/04/07 10:18
阅读数 63

重新认识hashmap

Hashmap🌩类中有个很重要的字段(Node[]table)这个就是我们常说的hash桶,本质上这是一个数组,Node是hashmap的内部类,实现了entry接口。。hashmap底层是数组+链表的组合形式。

Hashmap的put方法。

首先根据key值计算hash值,得到要插入的数组索引i,此时判断table[i]是否为空或者null,如果是空或null,就直接插入。插入以后再判断当前的键值对数量是否超过了最大容量,hashmap的最大容量是16,加载因子是0.75,正常情况下12就会扩容。

然后,若是发现tale[i]不为null,那么此时会先比较当前的tale[i]的首个key值和即将插入的key是否相同(此处的相同是指其中的hashcode和equals是否相同)若是相同,则直接覆盖。

若是不相同,则开始遍历table[i],此时在jdk8中引入了红黑树的特性,就是说会判断当前链表是否超过8,若是超过了8,则会将链表转化为红黑树,遍历过程中,若是发现有相同key值时,则覆盖,否则在红黑树或链表中执行插入操作。

 

Hashmap的时间复杂度理想状态下是O(1),但是考虑到存在hash碰撞,会导致某个数组table[i]下的链表出现过长的情况,那么此时很有可能会是O(N)。。为了避免这种情况出现,尽量是采用比较好的算法来减少hash碰撞,目前用的最常见的应该是高位运算和取模运算。

 

 

Hashmap的链表插入变化

Hashmap在1.7以前采用的是头插入法,这样会出现一个问题是会在扩容时改变链表元素原先的排列顺序,如果此时出现了高并发情况会导致链表成环(链表成环会导致陷入死循环),所以在1.8中改为采用尾插入法,这样就不会改变原有的链表元素位置。

 

 

红黑树的时间复杂度是

跟二叉查找树的时间复杂度是一样的,执行查找、插入、删除等操作的时间复杂度为O(logn)

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部