概述

  • java中的hash表。
  • 主要分析jdk1.8版本
  • 容量上限是int类型的上限值。

  • jdk1.7及之前版本的hashMap在并发场景下会有死循环问题。

    put方法

  • 插入或替换方法

  1. 判断存储数组是否初始化过
    1. 没初始化过则调用扩容方法进行初始化
  2. 找到对应hash表位置是否存在节点
    1. 不存在节点则直接新增，完成
    2. 存在节点则继续判断
  3. 该位置对应的节点是否就是要插入的节点
    1. 完全匹配了，则更新值，完成。
    2. 如果不能匹配，那这个节点的值可能是树节点或链表，继续向后判断。
  4. 判断这个位置的节点是否是树节点。
    1. 如果是树节点，则调用树节点的插入方法，完成。
  5. 以上都不是，那这个位置的节点只能是链表节点了。
    1. 在链表中匹配要插入的节点，匹配不到则插到链表最后，完成。
  • 以上的完成一般都还有其余的收尾操作，比如判断是否需要为null值试才插入、比如扩容、比如记录操作次数。

    get()方法

  1. 判断数组是否存在，不存在返回null
  2. 判断数组长度是否大于0，否则返回null
  3. 判断对应hash位置是否存在节点，不存在返回null
  4. 比对这个节点上的值是否是目标值，匹配成功直接返回。
  5. 节点上的值不是，则判断这个节点是否是链表节点或树节点（是否有next），都不是返回null。
  6. 判断是不是树节点，调用树节点的get方法，直接返回。
  7. 到最后一定是链表节点了，循环比对链表上的值，直接返回。

    resize()方法

  • 存储数组初始化或长度扩容
  • 数组的长度一定是2的指数倍（1，2，4，8，16，32，64……）
  • 准备工作，拿到原数组引用、原数组长度、原数组阈值。

    先计算要扩容的长度

  1. 判断扩容前数组容量是否大于0
    1. 大于0表示正经扩容的，（就是原本数组有一定长度，这里不够了需要扩容）
      1. 正经扩容时先判断是否已超过某个极限值，如果超过了，则直接设置长度为int类型的最大值。
      2. 没超极限值则容量翻倍
      3. 如果长度在极限值以下，默认值以上则指定阈值。否则留给下一阶段指定。
    2. 数组长度不大于0说明还没初始化
  2. 判断原数组阈值是否大于0.
    1. 就是如果HashMap创建时指定了初始化长度，则使用指定的长度进行初始化。

  3. 原数组没初始化，也没制定初始化大小，则使用默认值

    1. 默认初始化长度 16
    2. 默认初始化阈值 12

      判断新数组阈值是否指定了

  4. 因为创建HashMap时如果指定好了数组大小，则这里需要计算下阈值大小。

  5. 另外如果原长度为2，扩容长度到4，那就不能简单的把阈值乘2。

    转移数据

  • 只有原本有数据的才需要转移，如果是初始化原本没有数据，就不用这一步了
  • 循环已有的数组：
  1. 节点不能为空。（为空的是还没插入过数据的）
  2. 判断节点的next是否为null
    1. 为null表示不是树节点也不是链表节点，直接转移到新数组即可。
    2. 如果存在nuxt则继续判断
  3. 节点是否是树节点。
    1. 是树节点则调用树节点的转移方法。
  4. 上面两个都不是则一定是链表节点。
    1. 链表节点转移只可能会落到新数组的两个位置，（由hash方法决定的）
    2. 直接计算高低位，处理成两个链表，直接赋值到新数组对应位置。

compute()方法

  • 传入key和一个lambda表达式，
    • 表达式传入的值是原节点的key和value，
    • 如果原节点不存在或value没有会传null。
    • 返回值是新的value值，如果为null会做删除操作。