HashMap的实现原理(看这篇就够了） HashMap的实现原理(看这篇就够了

文章图片

HashMap 是一线资深 java工程师必须要精通的集合容器，它的重要性几乎等同于Volatile在并发编程的重要性（可见性与有序性）。
本篇通过图文源码详解，深度剖析 HashMap 的重要内核知识，易看易学易懂。建议收藏，多学一点总是好的，万一面试被问到了呢。
我是Mike，10余年BAT一线大厂架构技术倾囊相授。本篇重点：

HashMap的数据结构
HashMap核心成员
HashMapd的Node数组
HashMap的数据存储
HashMap的哈希函数
哈希冲突：链式哈希表
HashMap的get方法：哈希函数
HashMap的put方法
为什么槽位数必须使用2^n？

HashMap的数据结构 【HashMap的实现原理(看这篇就够了）】首先，我们从数据结构的角度来看：HashMap是:数组+链表+红黑树（JDK1.8增加了红黑树部分）的数据结构，如下所示:

文章图片

这里需要搞明白两个问题：
*数据底层具体存储的是什么？
这样的存储方式有什么优点呢？*

默认初始容量(数组默认大小):16，2的整数次方static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 最大容量static final int MAXIMUM_CAPACITY = 1 << 30; 默认负载因子static final float DEFAULT_LOAD_FACTOR = 0.75f; 装载因子用来衡量HashMap满的程度，表示当map集合中存储的数据达到当前数组大小的75%则需要进行扩容链表转红黑树边界static final int TREEIFY_THRESHOLD = 8; 红黑树转离链表边界static final int UNTREEIFY_THRESHOLD = 6; 哈希桶数组transient Node[] table; 实际存储的元素个数transient int size; 当map里面的数据大于这个threshold就会进行扩容int threshold阈值 = table.length * loadFactor

2.Node数组
从源码可知，HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个Node的数组。

static class Node implements Map.Entry {final int hash; //用来定位数组索引位置final K key; V value; Node next; //链表的下一个Node节点 Node(int hash, K key, V value, Node next) {this.hash = hash; this.key = key; this.value = https://www.it610.com/article/value; this.next = next; } public final K getKey(){ return key; }public final V getValue(){ return value; }public final String toString() { return key +"=" + value; } public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value); }public final V setValue(V newValue) {V oldValue = https://www.it610.com/article/value; value = newValue; return oldValue; }public final boolean equals(Object o) {if (o == this)return true; if (o instanceof Map.Entry) {Map.Entry e = (Map.Entry)o; if (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))return true; }return false; }}

Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。
HashMap的数据存储 1.哈希表来存储
HashMap采用哈希表来存储数据。
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构，只要输入待查找的值即key，即可查找到其对应的值。
哈希表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
2.哈希函数
哈希表中元素是由哈希函数确定的,将数据元素的关键字Key作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。
表示为：Addr = H（key）,如下图所示：

文章图片

哈希表中哈希函数的设计是相当重要的，这也是建哈希表过程中的关键问题之一。
3.核心问题
建立一个哈希表之前，需要解决两个主要问题：
1) 构造一个合适的哈希函数,均匀性 H（key）的值均匀分布在哈希表中
2) 冲突的处理
冲突：在哈希表中，不同的关键字值对应到同一个存储位置的现象。
4.哈希冲突：链式哈希表
哈希表为解决冲突，可以采用地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。
链地址法，简单来说，就是数组加链表的结合,如下图所示：

文章图片

HashMap的哈希函数

/*** 重新计算哈希值*/static final int hash(Object key) {int h; // h = key.hashCode() 为第一步取hashCode值// h ^ (h >>> 16) 为第二步高位参与运算return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

//计算数组槽位

(n - 1) & hash

对key进行了 hashCode 运算，得到一个32位的 int 值 h, 然后用 h 异或 h>>>16位。在 JDK1.8 的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：
(h = k.hashCode()) ^ (h >>> 16)。

文章图片

这样做的好处是：
可以将hashcode高位和低位的值进行混合做异或运算，而且混合后，低位的信息中加入了高位的信息，这样高位的信息被变相的保留了下来。
等于说计算下标时把hash的高16位也参与进来了，掺杂的元素多了，那么生成的hash值的随机性会增大，减少了hash碰撞。
备注：

- ^异或：不同为1，相同为0 ->>> ：无符号右移：右边补0 - &运算：两位同时为“1”，结果才为“1，否则为0

h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方。
为什么槽位数必须使用2^n 1. 为了让哈希后的结果更加均匀

文章图片

假如槽位数不是16，而是17，则槽位计算公式变成：(17 – 1) & hash
从上文可以看出，计算结果将会大大趋同，hashcode参加&运算后被更多位的0屏蔽，计算结果只剩下两种0和16，这对于hashmap来说是一种灾难。2.等价于length取模
当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
位运算的运算效率高于算术运算，原因是算术运算还是会被转化为位运算。
最终目的，还是为了让哈希后的结果更均匀的分部，减少哈希碰撞，提升hashmap的运行效率。
分析HashMap的put方法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node[] tab; Node p; int n, i; // 当前对象的数组是null 或者数组长度时0时，则需要初始化数组if ((tab = table) == null || (n = tab.length) == 0) {n = (tab = resize()).length; }// 使用hash与数组长度减一的值进行异或得到分散的数组下标，预示着按照计算现在的// key会存放到这个位置上，如果这个位置上没有值，那么直接新建k-v节点存放// 其中长度n是一个2的幂次数if ((p = tab[i = (n - 1) & hash]) == null) {tab[i] = newNode(hash, key, value, null); }// 如果走到else这一步，说明key索引到的数组位置上已经存在内容，即出现了碰撞// 这个时候需要更为复杂处理碰撞的方式来处理，如链表和树else {Node e; K k; //节点key存在，直接覆盖valueif (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) {e = p; }// 判断该链为红黑树else if (p instanceof TreeNode) {// 其中this表示当前HashMap, tab为map中的数组e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); }else {// 判断该链为链表for (int binCount = 0; ; ++binCount) {// 如果当前碰撞到的节点没有后续节点，则直接新建节点并追加if ((e = p.next) == null) {p.next = newNode(hash, key, value, null); // TREEIFY_THRESHOLD = 8// 从0开始的，如果到了7则说明满8了，这个时候就需要转// 重新确定是否是扩容还是转用红黑树了if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash); break; }// 找到了碰撞节点中，key完全相等的节点，则用新节点替换老节点if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break; p = e; }}// 此时的e是保存的被碰撞的那个节点，即老节点if (e != null) { // existing mapping for keyV oldValue = https://www.it610.com/article/e.value; // onlyIfAbsent是方法的调用参数，表示是否替换已存在的值，// 在默认的put方法中这个值是false，所以这里会用新值替换旧值if (!onlyIfAbsent || oldValue == null)e.value = value; // Callbacks to allow LinkedHashMap post-actionsafterNodeAccess(e); return oldValue; }}// map变更性操作计数器// 比如map结构化的变更像内容增减或者rehash，这将直接导致外部map的并发// 迭代引起fail-fast问题，该值就是比较的基础++modCount; // size即map中包括k-v数量的多少// 超过最大容量就扩容if (++size> threshold)resize(); // Callbacks to allow LinkedHashMap post-actionsafterNodeInsertion(evict); return null; }

HashMap的put方法执行过程整体如下：
① 判断键值对数组 table[i] 是否为空或为null，否则执行 resize() 进行扩容；
② 根据键值 key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加；
③ 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value；
④ 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对；
⑤ 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥ 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
HashMap总结 HashMap底层结构？基于Map接口的实现，数组+链表的结构，JDK 1.8后加入了红黑树，链表长度>8变红黑树,<6变链表
两个对象的hashcode相同会发生什么? Hash冲突，HashMap通过链表来解决hash冲突
HashMap 中 equals() 和 hashCode() 有什么作用？HashMap 的添加、获取时需要通过 key 的 hashCode() 进行 hash()，然后计算下标 ( n-1 & hash)，从而获得要找的同的位置。当发生冲突（碰撞）时，利用 key.equals() 方法去链表或树中去查找对应的节点
HashMap 何时扩容？put的元素达到容量乘负载因子的时候，默认16*0.75
hash 的实现吗？h = key.hashCode()) ^ (h >>> 16)， hashCode 进行无符号右移 16 位，然后进行按位异或，得到这个键的哈希值，由于哈希表的容量都是 2 的 N 次方，在当前，元素的 hashCode() 在很多时候下低位是相同的，这将导致冲突（碰撞），因此 1.8 以后做了个移位操作：将元素的 hashCode() 和自己右移 16 位后的结果求异或
HashMap线程安全吗？HashMap读写效率较高，但是因为其是非同步的，即读写等操作都是没有锁保护的，所以在多线程场景下是不安全的，容易出现数据不一致的问题，在单线程场景下非常推荐使用。
以上就是HashMap的介绍，本篇的视频版详解，留言可获取。
---END--
关于作者：mikechen，十余年BAT架构经验，资深技术专家，曾任职阿里、淘宝、百度。
欢迎关注个人公众号：mikechen的互联网架构，十余年BAT架构经验倾囊相授！
在公众号菜单栏对话框回复【架构】关键词，即可查看我原创的300期+BAT架构技术系列文章与1000+大厂面试题答案合集。