欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

面试连环炮系列(七):HashMap的put操作做了什么

程序员文章站 2022-05-29 10:33:31
1. HashMap的put操作做了什么? HashMap的是由数组和链表构成的,JDK7之后加入了红黑树处理哈希冲突。put操作的步骤是这样的: 1. 根据key值计算出哈希值作为数组下标。如果数组的这个位置是空的,把k放进去,put操作就完成了。 2. 如果数组位置不为空,这个元素必然是个链表。 ......
  1. hashmap的put操作做了什么?
    hashmap的是由数组和链表构成的,jdk7之后加入了红黑树处理哈希冲突。put操作的步骤是这样的:
    1. 根据key值计算出哈希值作为数组下标。如果数组的这个位置是空的,把k放进去,put操作就完成了。
    2. 如果数组位置不为空,这个元素必然是个链表。遍历链表逐一比对value,如果value在链表中不存在,就把新建节点,将value放进去,put操作完成。
    3. 如果链表中value存在,则替换原节点的value,put操作完成。
    4. 如果链表节点数已经达到8个,首先判断当前hashmap的长度,如果不足64,只进行resize,扩容table,如果达到64就将冲突的链表为红黑树。
  2. 元素在数组中的位置怎么计算出来的
    采用数组长度与value的哈希值取与操作计算的,表达式:(n - 1) & hash,n是数组长度,hash是hash(value)。

  3. 红黑树有什么优势,为什么要将链表转成红黑树
    红黑树的平均查找长度是log(n),长度为8的时候,平均查找长度为3,如果使用链表,平均查找长度为8/2=4。链表长度如果是小于等于6,平均查找长度6/2=3,虽然速度也很快,但是转化为树结构和生成树的时间也会耗时。

  4. 什么情况下数组会扩容
    当元素个数超过数组长度 * loadfactor时,就会进行数组扩容,loadfactor的默认值为0.75。默认情况下,数组大小为16,元素个数超过16 * 0.75=12的时候,就把数组的大小扩展一倍,即2 * 16 = 32,重新计算每个元素在数组中的位置,这是一个非常消耗性能的操作。

参考(部分摘抄的文字版权属于原作者):




鸡汤:你全心全意的付出,还不如别人的随便搞搞。