HashMap

put

  • 判断是否有tab[],没有证明还没有初始化,先初始化(容量,threadHold)
  • 对key hash后和length-1与寻找bucket,如果bucket为空放入,如果不为空但是key相同换掉,如果是treeNode证明已经树化,调用putTreeVal,否则是链化的,向下寻找找到key相同的或者链的tail插入(尾插),并判断是链的容量是否到了树化的临界点,到了把tab树化最后判断是否需要扩容,最后把oldVal返回
  • 问题: 如何树化,树化之后的putTreeVal如何操作,如何扩容

get

  • 1.获得key的hash,和length-1求与得到bucket的firstNode,如果key相同返回value不同判断是不是treeNode,是的话调用getTreeNode,不是的话顺着链向下找直到key相同返回相应的value或者是null
  • 问题: treeNode如何get

如何树化

  • 当链表超过8个,就会树化,如果链表的size比较小,还会扩容(为什么扩容) 第一次树化只是由node变成treenode,维护了pre和next指针,但是并没有真正树化真的树化,应该是第一次putTreeVal的时候树化之后入会putTreeVal找到树的root,通过hash值寻找root大的dir+,小的dir-如果key相同返回p,如果key不同,但是hash相同,看下key有没有实现compator类如果没有实现或者实现了,但是compator之后也相同,就search当前的节点直到找到应该插入的地方,如果找不到(key不同compator相同)只能调用system的hash方法然后调整树至平衡

treeNode如何get

  • 找到root,根据hash值find

扩容

  • map有最大size,如果超过了直接返回老的map,不会再扩了否则就是init下初始的容量threadHold值,或者不是第一次init的话就扩容为原来的二倍,从头到尾遍历,
  • 不是树化的bucket: 如果目标bucket上只有一个节点,直接放到原来2的index上 多个节点 节点的hash和oldCap求于,为0的穿成一串 不为0的穿成一串,同时保留第一个的头结点 最后把0的头结点放到原地,不为0的头结点放到2的index上
  • 树化的bucket: 同样也是hash和oldCap求于,然后分成两串,串的size大于8的树化,小于6的链化

remove

  • 根据key获得bucket的index,然后寻找需要被remove的node同理寻找的过程也分为链化和树化的节点
  • 链化的:不断next判断key是否相同,找到之后直接通过指针把找到的noderemove了
  • 树化的:和get中寻找treeNode相同,先找到目标节点

注: remove有的会去匹配value的值,如果key的value和传入的value不同
不可以删除当前节点

发表评论

邮箱地址不会被公开。 必填项已用*标注