HashMap 分析，基于JDK7

一、HashMap 原理分析

HashMap 是一个用来存数据的容器，存储格式为 key-value 。

HashMap 的底层以 数组+链表 的格式进行存储。

往HashMap 中存键值对的原理图如下

image.png

如图，HashMap存值大致步骤如下：

image.png

1.1、存储原理

HashMap 采用链地址（同时也是Hash冲突的解决原理）法进行存储。

链地址法逻辑图如下：
image.png

hash 冲突的解决：当 hash 算法得出相同数组的下标索引时，以链表的形式进行存储。

1.3、构造函数

以无参构造为入口

相关代码如下：
image.png
通过构造函数得出以下结论：

  • HashMap 默认初始化容量大小为 16（在put方法时才进行初始化，这里只是设置）
  • HashMap 容器最大上限为 1 << 30

    1.4、插入数据（put方法）-小知识

    1.4.1、加载因子的使用（设置容器扩容阈值）

    1.4.1.1、加载因子设置
    image.png
    第一次进行设置操作的时候，会进行加载因子的设置，默认值为：16 * 0.75 = 12 。

小贴士：roundUpToPowerOf2() 方法解析 先来看一下 roundUpToPowerOf2() 方法内容 image.png 方法的关键是 Integer.highestOneBit

关于 Integer.highestOneBit 测试案例如下： image.png 结论：按照 2^n 得出结果，如果值不是2的n次幂，例如：15 ，就往小的取值，最近的 2的n次幂，小于15的最近的 2的n次幂是 8（2^3）。
>
HashMap > Integer.highestOneBit( (number-1) << 1 ) **> 中把 number -1 然后扩大两倍，使得取值在 number 右边最大的 n次幂，往大了取

1.4.1.2、加载因子使用

image.png
如上述代码所示，加载因子是用来判定是否需要扩容的判定标准之一。

通过上述代码能够知道

  • 扩容条件
    1、当前容器键值对数量 >= threshold
    &&
    2、当前新的键值对插入的位置不为空
    （如果新增加元素 hash 获取到的数组索引值所在的位置没有值，直接赋值就完了，毕竟扩容需要有相关的内存损耗和性能损耗，如果要出入的值所对应的索引值有值，那就直接进行扩容，防止生成链表的操作）
  • 扩容大小：当前数组容量的两倍

    1.4.1.3、为什么加载因子为 0.75

    假设容器的长度为 16，加载因子为 0.75 ，而进行扩容出发的条件之一就是 容器元素个数 >= 16 * 0.75 = 12

为什么加载因子为 0.75 也就是说为什么不等容器中的数组存满的在进行扩容？

因为容器中 Entry[] 数组的存储是根据 key 获取 hash值，然后计算得到索引值的，也就是说可能存在某种情况，hash值的落点无法覆盖所有的数组位置。
比如：
image.png
索引的落点总是无法落到红色框定的数组位置，会存在数组没有存满的情况，但是相同索引位置的链表却一致增长，所以需要在数组没有满之前进行扩容，减少链表的长度，具体需要在什么时候进行扩容，通过大数据的测试，计算出当容器元素数量 >= 容器长度 * 0.75 的时候进行扩容，效率最高。所以该因子就设定为了 0.75。

1.4.2、索引计算

image.png

索引计算分两个步骤

  • 步骤一、求 hash 值
    为了获取足够分散的散列值
  • 步骤二、 hash 值 & (容器大小-1)
    让散列值在计算后，范围落在容器大小之内
    如：散列值 于 16 -1 & 运算后
    010101010001010101001
    000000000000000001111
    ————————————————-
    000000000000000001001

    1.4.3、扩容操作

    扩容在 put 方法执行 addEntry 时触发

image.png
执行逻辑

  • 新建数组，数组长度为原数组长度的2倍
  • 遍历原数组，重新计算 hash值，并计算索引值，进行插入操作
  • 重新计算 threshold (扩容阈值)，计算公式：新数组长度 * 0.75

    1.5、获取值（get）

    以 get(Object key) 为例

相关代码如下：
image.png
值的获取如下

  • 1、根据key计算 hash值，然后获取索引值

  • 2、索引值位置有值，或者存在链表，通过对比
    对比条件： 1、hash值相同，2、key 的地址相同 || key equals e.key

    1.6、常见的常量值

  • DEFAULT_INITIAL_CAPACITY 默认容量常量：16

  • MAXIMUM_CAPACITY 支持最大容量：2^30
  • DEFAULT_LOAD_FACTOR 默认加载因子：0.75f
  • Entry[] table = (Entry[]) EMPTY_TABLE; 存储元素的数组，数组长度总为 2^n
  • int size; HashMap 中存储的键值对数量
  • modCount：HashMap 扩容和结构改变次数
  • threshold ：扩容的临界值 = 容量 * 0.75
  • loadFactory ：加载因子

【公众号】花好夜猿
wxlogo.jpg