HashMap源码分析一JDK源码分析系列

正文开始 注:JDK 版本为 1.8

HashMap1.8 和 1.8 之前的源码差别很大

• 目录

  • 简介

    • 数据结构
  • 类结构
  • 属性
  • 构造方法
  • 增加
  • 删除
  • 修改
  • 总结

1.HashMap 简介

HashMap 基于哈希表的 Map 接口实现，是以 key-value 存储形式存在。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。)

HashMap 的实现不是同步的，这意味着它不是线程安全的。它的 key、value 都可以为 null。此外，HashMap 中的映射不是有序的。在 JDK1.8 中，HashMap 是由 数组 + 链表 + 红黑树构成，新增了红黑树作为底层数据结构，结构变得复杂了，但是效率也变的更高效。

1.2 HashMap 数据结构

在 JDK1.8 中，HashMap 是由 数组 + 链表 + 红黑树构成，新增了红黑树作为底层数据结构，结构变得复杂了，但是效率也变的更高效。当一个值中要存储到 Map 的时候会根据 Key 的值来计算出他的

hash，通过哈希来确认到数组的位置，如果发生哈希碰撞就以链表的形式存储 在 Object 源码分析中解释过，但是这样如果链表过长来的话，HashMap 会把这个链表转换成红黑树来存储。

来看依一下 HashMap 的存储结构

但是这样的话问题来了，HashMap 为什么要使用红黑树呢，这样结构的话不是更麻烦了吗？？

这个问题我也没有想过，其实很多在看的时候只会在乎红黑树的实现而忽略到了为什么要使用的这个问题，我也是在写本文的时候突发疑惑。参考了网上的例子，同时也解释了为什么阀值为 8：

因为 Map 中桶的元素初始化是链表保存的，其查找性能是 O(n)，而树结构能将查找性能提升到 O(log(n))。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。至于为什么阈值是 8，我想，去源码中找寻答案应该是最可靠的途径。

参考地址：https://dwz.cn/nPFXmXwJ

2. 类结构

我们来看一下类结构

在阅读源码的时候一直有个问题很困惑就是 HashMap 已经继承了 AbstractMap 而 AbstractMap 类实现了 Map 接口，那为什么 HashMap 还要在实现 Map 接口呢？同样在 ArrayList 中 LinkedList 中都是这种结构。

据 java 集合框架的创始人 Josh Bloch 描述，这样的写法是一个失误。在 java 集合框架中，类似这样的写法很多，最开始写 java 集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK 的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。

• Cloneable 空接口，表示可以克隆
• Serializable 序列化
• AbstractMap 提供 Map 实现接口

3. 属性

初始化容量 ( 必须是二的 n 次幂)

集合最大容量 ( 必须是二的幂)

负载因子，默认的 0.75

当链表的值超过 8 则会转红黑树(1.8 新增)

当链表的值小于 6 则会从红黑树转回链表

当 Map 里面的数量超过这个值时，表中的桶才能进行树形化，否则桶内元素太多时会扩容，而不是树形化 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD

table 用来初始化 ( 必须是二的 n 次幂)

用来存放缓存

HashMap 中存储的数量

用来记录 HashMap 的修改次数

用来调整大小下一个容量的值计算方式为(容量 * 负载因子)

哈希表的加载因子

重点属性

• table 在 JDK1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构其中 table 就是 HashMap 中的数组
• Size 为 HashMap 中 K - V 的实时数量
• loadFactor 加载因子，是用来衡量 HashMap 满的程度，计算 HashMap 的实时加载因子的方法为：size/capacity，而不是占用桶的数量去除以 capacity。capacity 是桶的数量，也就是 table 的长度 length。
• threshold 计算公式：capacity * loadFactor。这个值是当前已占用数组长度的最大值。过这个数目就重新 resize(扩容)，扩容后的 HashMap 容量是之前容量的两倍

4. 构造方法

开始看构造方法。

4.1 HashMap()

构造一个空的 HashMap，默认初始容量（16）和默认负载因子（0.75）。

4.2 HashMap(int initialCapacity)

构造一个空的 HashMap具有指定的初始容量和默认负载因子（0.75）。

4.3 HashMap(int initialCapacity, float loadFactor)

构造一个空的 HashMap具有指定的初始容量和负载因子。我们来分析一下。

最后调用了 tableSizeFor，来看一下方法实现：

5. 增加

现在我们开始分析 put()方法

我们可以看到 put 调用的是 putVal 来进行数据插入，但是要注意到 key 在这里执行了一下 hash()方法, 来看一下 Hash 方法是如何实现的。

从上面可以得知 HashMap 是支持 Key 为空的，而 HashTable 是直接用过 Key 来获取 HashCode 所以 key 为空会抛异常其实上面就已经解释了为什么 HashMap 的长度 为什么要是 2 的幂 因为 HashMap 使用的方法很巧妙，它通过 hash & (table.length -1)来得到该对象的保存位，前面说过 HashMap 底层数组的长度总是 2 的 n 次方，这是 HashMap 在速度上的优化。当 length 总是 2 的 n 次方时，hash & (length-1)运算等价于对 length 取模，也就是 hash%length，但是 & 比 % 具有更高的效率。比如 n % 32 = n & (32 -1)。

现在看 putVal()方法，看看它到底做了什么。

主要参数：

• hash key 的 hash 值
• key 原始 Key
• value 要存放的值
• onlyIfAbsent 如果 true 代表不更改现有的值
• evict 如果为 false 表示 table 为创建状态

完整源码分析，放图片的话会太长了，所以就截取了一下分为两部。

暂时分析到添加，首发乱敲代码公众号