面试连环炮系列(七):说说HashMap的put操作
-
HashMap的put操作做了什么?
HashMap的是由数组和链表构成的,JDK7之后加入了红黑树处理哈希冲突。put操作的步骤是这样的:- 根据key值计算出哈希值作为数组下标。如果数组的这个位置是空的,把k放进去,put操作就完成了。
- 如果数组位置不为空,这个元素必然是个链表。遍历链表逐一比对value,如果value在链表中不存在,就把新建节点,将value放进去,put操作完成。
- 如果链表中value存在,则替换原节点的value,put操作完成。
- 如果链表节点数已经达到8个,首先判断当前hashMap的长度,如果不足64,只进行resize,扩容table,如果达到64就将冲突的链表为红黑树。
-
元素在数组中的位置怎么计算出来的
采用数组长度与value的哈希值取与操作计算的,表达式:
,n是数组长度,hash是hash(value)。(n - 1) & hash
-
红黑树有什么优势,为什么要将链表转成红黑树
红黑树的平均查找长度是log(n),长度为8的时候,平均查找长度为3,如果使用链表,平均查找长度为8/2=4。链表长度如果是小于等于6,平均查找长度6/2=3,虽然速度也很快,但是转化为树结构和生成树的时间也会耗时。 -
什么情况下数组会扩容
当元素个数超过
,重新计算每个元素在数组中的位置,这是一个非常消耗性能的操作。数组长度 * loadFactor
`时,就会进行数组扩容,loadFactor的默认值为0.75。默认情况下,数组大小为16,元素个数超过
`16 * 0.75=12
`的时候,就把数组的大小扩展一倍,即
`2 * 16 = 32
参考(部分摘抄的文字版权属于原作者):
https://www.jianshu.com/p/2c7a4a4e1f53
https://www.cnblogs.com/liwei2222/p/8013367.html
https://www.cnblogs.com/williamjie/p/9358291.html
https://www.cnblogs.com/xc-chejj/p/10825676.html
本文链接:https://www.codingbrick.com/archives/169.html
特别声明:除特别标注,本站文章均为原创,转载请注明作者和出处倾城架构,请勿用于任何商业用途。