HashMap

本篇讲解HashMap的相关知识

JDK 1.7

put过程:

  • 判断当前数组是否需要初始化。
  • 如果 key 为空,则 put 一个空值进去。
  • 根据 key 计算出 hashcode。
  • 根据计算出的 hashcode 定位出所在桶。
  • 如果桶是一个链表则需要遍历判断里面的 hashcode、key 是否和传入 key 相等,如果相等则进行覆盖,并返回原来的值。
  • 如果桶是空的,说明当前位置没有数据存入;新增一个 Entry 对象写入当前位置。

get过程:

  • 首先也是根据 key 计算出 hashcode,然后定位到具体的桶中。
  • 判断该位置是否为链表。
  • 不是链表就根据 key、key 的 hashcode 是否相等来返回值。
  • 为链表则需要遍历直到 key 及 hashcode 相等时候就返回值。
  • 啥都没取到就直接返回 null 。

JDK1.8

put过程:

  1. 判断当前桶是否为空,空的就需要初始化(resize 中会判断是否进行初始化)。
  2. 根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空,为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。
  3. 如果当前桶有值( Hash 冲突),那么就要比较当前桶中的 key、key 的 hashcode与写入的 key 是否相等,相等就赋值给 e,在第 8 步的时候会统一进行赋值及返回。
  4. 如果当前桶为红黑树,那就要按照红黑树的方式写入数据。
  5. 如果是个链表,就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面(形成链表)。
  6. 接着判断当前链表的大小是否大于预设的阈值,大于时就要转换为红黑树。
  7. 如果在遍历过程中找到 key 相同时直接退出遍历。
  8. 如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。
  9. 最后判断是否需要进行扩容。

get过程:

  1. 首先将 key hash 之后取得所定位的桶。
  2. 如果桶为空则直接返回 null 。
  3. 否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key,是就直接返回 value。
  4. 如果第一个不匹配,则判断它的下一个是红黑树还是链表。
  5. 红黑树就按照树的查找方式返回值。
  6. 不然就按照链表的方式遍历匹配返回值。
0%