HashMap 原理解析

type

status

date

slug

summary

常见 Java 数据结构：

ArrayList：数组

LinkedList：链表

HashMap:

jdk ≤ 1.7 数组+链表
jdk ≥ 1.8 数组+链表（+红黑树）

HashMap1.7 的数据结构是怎样的？

HashMap1.7 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。

HashMap1.7 是在链表头部还是尾部添加数据？

JDK1.7 用的是头插法

HashMap 是怎么预防和解决 Hash 冲突的？

其实，Java 中的 HashMap 采用的 Hash 冲突解决方案就是单独链表法，也就是在 Hash 表节点使用链表存储 Hash 值相同的值

不过需要知道的是 JDK8 之后，如果链表长度超过 8 将会将链表转化为红黑树以便提高在 Hash 冲突严重情况下的查询效率，也能够避免一定的 Hash 碰撞攻击。

HashMap1.7 默认容量是多少？为什么？

JDK1.7 的时候初始容量确实是 16（默认大小为 16，负载因子 0.75，阈值 12）但是 JDK1.8 的时候初始化 HashMap 的时候并没有指定容量大小，而是在第一次执行 put 数据，才初始化容量。

HashMap1.7 数组是什么时候创建的？

JDK1.7 中，第一次put时才创建数组 tables

HashMap1.7 的扩容条件是什么？

存放新值的时候当前已有元素的个数必须大于等于阈值

存放新值的时候当前存放数据发生 Hash 碰撞（当前 key 计算的 Hash 值换算出来的数组下标位置已经存在值）

需要同时满足上面两个条件才行。

因为上面这两个条件，所以存在下面这些情况

（1）、就是 Hashmap 在存值的时候（默认大小为 16，负载因子 0.75，阈值 12），可能达到最后存满 16 个值的时候，再存入第 17 个值才会发生扩容现象，因为前 16 个值，每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。

（2）、当然也有可能存储更多值（超多 16 个值，最多可以存 27 个值）都还没有扩容。原理：前11个值全部 Hash 碰撞，存到数组的同一个位置（虽然 Hash 冲突，但是这时元素个数小于阈值 12，并没有同时满足扩容的两个条件。所以不会扩容），（在存入第 12 个元素的时候，还是存入前面 11 个元素所在的下标位置，因为存入之前此时比较当前元素个数 11<12(16x0.75)，所以在存入第 12 个元素的时候不会发生扩容，那么还有 15 个数据下标的位置是空的，后面所有存入的 15 个值全部分散到数组剩下的 15 个位置（这时元素个数大于等于阈值，但是每次存入的元素并没有发生 Hash 碰撞，也没有同时满足扩容的两个条件，所以叶不会扩容），所以在存入第 28 个值的时候才同时满足上面两个条件，这时候才会发生扩容现象。

JDK1.7 中先进行扩容后进行插入，而在 JDK1.8 中是先进行插入后进行扩容。为什么1.8要这么做？

JDK1.7 中：先扩容后插入

当你发现你插入的桶是不是为空，如果不为空说明存在值就发生了 Hash 冲突，那么就必须得扩容，但是如果不发生 Hash 冲突的话，说明当前桶是空的（后面并没有挂有链表），那就等到下一次发生 Hash 冲突的时候在进行扩容，但是当如果以后都没有发生 Hash 冲突产生，那么就不会进行扩容了，减少了一次无用扩容，也减少了内存的使用

JDK1.8 中：先插入后扩容

主要是因为对链表转为红黑树进行的优化，因为你插入这个节点的时候有可能是普通链表节点，也有可能是红黑树节点

如果是链表节点，是否达到了链表转化为红黑树的阈值是 8，如果没有那么就还可以继续插入。

如果是红黑树节点，需要看插入红黑树节点是否还能满足当前是红黑树的特性，如果还能继续满足即还没有达到扩容的临界条件。