HashMap 源码分析

感谢 changfubai 对本文的改进做出的贡献！ HashMap 简介 HashMap 主要用来存放键值对，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个 JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。 JDK1.8 以后的 在解决哈希冲突时有了较大的变化，当链表长度大于等于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。并且， 总是使用 2 的幂作为哈希表的大小。 底层数据结构分析 JDK1.8 之前 JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列 。 HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。 所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法，换句话说使用扰动函数之后可以减少碰撞。 JDK 1.8 HashMap 的 hash 方法源码: JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。 对比一下 JDK1.7 的 HashMap 的 hash 方法源码. 相比于 JDK1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。 所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。 JDK1.8 之后 相比于之前的版本，JDK1.8 以后在解决哈希冲突时有了较大的变化。 当链表长度大于阈值（默认为 8）时，会首先调用 方法。这个方法会根据 HashMap 数组来决定是否转换为红黑树。只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是执行 方法对数组扩容。相关源码这里就不贴了，重点关注 方法即可！ 类的属性： loadFactor 负载因子 loadFactor 负载因子是控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0，数组中存放的数据(entry)也就越少，也就越稀疏。 loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值 。 给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量超过了 16 \ 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。 threshold threshold = capacity \ loadFactor ， 当 Size threshold 的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准 。 Node 节点类源码: 树节点类源码: HashMap 源码分析 构造方法 HashMap 中有四个构造方法，它们分别如下： 需要特别注意的是：传入的 并不是最终的数组容量。 会调用 将其 向上取整为大于或等于该值的最小 2 的幂次方 ，并暂时保存到 字段。真正的 数组会在第一次扩容（ ）时才初始化为这个大小。 例如： → → 长度最终为 16。 putMapEntries 方法： put 方法 HashMap 只提供了 put 用于添加元素，putVal 方法只是给 put 方法调用的一个方法，并没有提供给用户使用。 对 putVal 方法添加元素的分析如下： 1. 如果定位到的数组位置没有元素 就直接插入。 2. 如果定位到的数组位置有元素就和要插入的 key 比较，如果 key 相同就直接覆盖，如果 key 不相同，就判断 p 是否是一个树节点，如果是就调用 将元素添加进入。如果不是就遍历链表插入（插入的是链表尾部）。 我们再来对比一下 JDK1.7 put 方法的代码 对于 put 方法的分析如下： ① 如果定位到的数组位置没有元素 就直接插入。 ② 如果定位到的数组位置有元素，遍历以这个元素为头结点的链表，依次和插入的 key 比较，如果 key 相同就直接覆盖，不同就采用头插法插入元素。 get 方法 resize 方法 进行扩容，会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。resize 方法实际上是将 table 初始化和 table 扩容 进行了整合，底层的行为都是给 table 赋值一个新的数组。 HashMap 常用方法测试 写在最后 如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。 JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。 如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。