HashMap的实现原理详解(看这篇就够了)

一线资深java工程师明确了需求通晓调集容器，尤其是今日我谈到的HashMap。

HashMap在Java调集的重要性不亚于Volatile在并发编程的重要性(可见性与有序性)。

我会要点解说以下9点：

1.HashMap的数据结构

2.HashMap核心成员

3.HashMapd的Node数组

4.HashMap的数据存储

5.HashMap的哈希函数

6.哈希冲突：链式哈希表

7.HashMap的get办法：哈希函数

8.HashMap的put办法

9.为什么槽位数有必要运用2^n？

HashMap的数据结构

首要我们从数据结构的视点来看：HashMap是:数组+链表+红黑树（JDK1.8增加了红黑树部分）的数据结构，如下所示:

HashMap的实现原理详解(看这篇就够了)

这儿需求搞明白两个问题：

  • 数据底层详细存储的是什么？
  • 这样的存储办法有什么优点呢？

1.核心成员

默许初始容量(数组默许巨细):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<K,V>[] table;
实践存储的元素个数
transient int size;
当map里面的数据大于这个threshold就会进行扩容
int threshold   阈值 = table.length * loadFactor

2.Node数组

从源码可知，HashMap类中有一个十分重要的字段，便是 Node[] table，即哈希桶数组，显着它是一个Node的数组。

 static class Node<K,V> implements Map.Entry<K,V> {
 final int hash;//用来定位数组索引位置
 final K key;
    V value;
 Node<K,V> next;//链表的下一个Node节点
 Node(int hash, K key, V value, Node<K,V> next) {
 this.hash = hash;
 this.key = key;
 this.value = 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 = 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）,如下图所示：

HashMap的实现原理详解(看这篇就够了)

哈希表中哈希函数的设计是适当重要的，这也是建哈希表过程中的关键问题之一。

3.核心问题

建立一个哈希表之前需求处理两个首要问题：

1)构造一个适宜的哈希函数,均匀性 H（key）的值均匀分布在哈希表中

2)冲突的处理

冲突：在哈希表中，不同的关键字值对应到同一个存储位置的现象。

4.哈希冲突：链式哈希表

哈希表为处理冲突，能够选用地址法和链地址法等来处理问题，Java中HashMap选用了链地址法。

链地址法，简单来说，便是数组加链表的结合,如下图所示：

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)。

HashMap的实现原理详解(看这篇就够了)

这样做的优点是，能够将hashcode高位和低位的值进行混合做异或运算，而且混合后，低位的信息中加入了高位的信息，这样高位的信息被变相的保留了下来。

等于说核算下标时把hash的高16位也参与进来了，掺杂的元素多了，那么生成的hash值的随机性会增大，削减了hash磕碰。

补白：

  • **^异或：**不同为1，相同为0
  • **>>> ：**无符号右移：右边补0
  • **&运算：**两位一起为“1”，成果才为“1，不然为0

h & (table.length -1)来得到该目标的保存位，而HashMap底层数组的长度总是2的n次方。

为什么槽位数有必要运用2^n？

1.为了让哈希后的成果更加均匀

HashMap的实现原理详解(看这篇就够了)

假设槽位数不是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<K,V>[] tab; Node<K,V> 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<K,V> e; K k;
 //节点key存在，直接掩盖value
 if (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<K,V>)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 1st
                        treeifyBin(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 key
            V oldValue = e.value;
 // onlyIfAbsent是办法的调用参数，表明是否替换已存在的值，
 // 在默许的put办法中这个值是false，所以这儿会用新值替换旧值
 if (!onlyIfAbsent || oldValue == null)
                e.value = value;
 // Callbacks to allow LinkedHashMap post-actions
            afterNodeAccess(e);
 return oldValue;
 }
 }
 // map改变性操作计数器
 // 比方map结构化的改变像内容增减或许rehash，这将直接导致外部map的并发
 // 迭代引起fail-fast问题，该值便是比较的根底
 ++modCount;
 // size即map中包含k-v数量的多少
 // 超越最大容量 就扩容
 if (++size > threshold)
        resize();
 // Callbacks to allow LinkedHashMap post-actions
    afterNodeInsertion(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的介绍，期望对你有所收成！