HashMap源码实现剖析

一、前言

HashMap 顾名思义，就是用hash表的原理实现的Map接口容器对象，那什么又是hash表呢。

咱们对数组都很相熟，数组是一个占用间断内存的数据结构，学过C的敌人对这一点影响必定更为粗浅。既然是一段间断的内存，数组的特点就不言而喻了，一旦你晓得要查第几个数据，工夫复杂度就是O(1),然而对于插入操作就很艰难；还有一种数据结构你也肯定很相熟，那就是链表，链表由一组指向（单向或者双向）的节点连贯的数据结构，它的特点是内存不间断，查找艰难，然而插入删除都很容易。

那有没有一种查找容易，插入删除查找都容易的数据结构呢，没错，它就是hash表。

本篇，咱们就来探讨：

HashMap的数据结构实现形式
HashMap是怎么做到为get、put操作提供稳固的工夫复杂度的
HashMap什么时候从单节点转成链表又是什么时候从链表转成红黑树
HashMap初始化时为什么要给自定义的初始容量。
HashMap如何保障容量始终是2的幂
HashMap为何要保障容量始终是2的幂
HashMap的hash值如何计算
HashMap为什么是线程不平安的

要理解HashMap 最好的形式就是看源码，本篇内容基于Jdk1.8HashMap源码。

二、HashMap的基本要素

磨刀不误砍柴功，想理解HashMap的原理，必然绕不过HashMap源码中的以下几个变量：

DEFAULT_INITIAL_CAPACITY：初始容量 1<<4也就是16
MAXIMUM_CAPACITY：最大容量 1<<30。
DEFAULT_LOAD_FACTOR：负载因子，默认是0.75。什么意思呢，比如说你定义了一个初始容量为16的HashMap，当你一直向外面增加元素后，最多到初始容量的0.75，HashMap就会触发扩容操作。
threshold：下一个触发扩容操作的阈值，threshold = CAPACITY * LOAD_FACTOR。
TREEIFY_THRESHOLD：链表转红黑树阈值，默认为8，超过8就会执行链表转红黑树办法，然而留神转红黑树办法中会判断以后size是否大于64，只有大于64才转红黑树，否则执行resize()操作。
UNTREEIFY_THRESHOLD：红黑树转链表阈值，默认为6，顾名思义，红黑树节点小于6就会转成链表。
Node<K, V> implements Map.Entry<K, V> HashMap存放数据的根本单位，外面存有hash值、key、value、next。
Node<K, V>[] table：寄存Node节点的数组，HashMap最底层数组，数组元素能够为单节点Node、多节点链表、多节点红黑树。

以上内容，有个印象就好，不用每个都记得。但这些概念对了解HashMap至关重要。

三、注释

3.1 HashMap 数据结构

HashMap的数据结构很简略，它是一个Node类型的数组，每个元素能够为单节点、多节点链表、多节点红黑树。要害的问题是，这么简略的构造怎么实现的put、get都很快？什么时候从单节点转成链表又是什么时候从链表转成红黑树？

3.1.1 HashMap如何实现put、get操作工夫复杂度为O(1)~O(n)?

咱们晓得，查找一个数组的元素，当咱们不晓得index的时候，复杂度是很高的，然而当咱们晓得index的时候，这个复杂度就是O(1)级别的。HashMap应用的就是这个原理。
对于get操作，首先依据key计算出hash值，而这个hash值执行操作(n - 1) & hash后就是它所在的index，在最好的状况下，该index恰好只有一个节点且hash值和key的hash值雷同，那么工夫复杂度就是O(1)，当该节点为链表或者红黑树时，工夫复杂度会回升，然而因为HashMap的优化（链表长度、红黑树长度绝对于HashMap容量不会过长，过长会触发resize操作），所以最坏的状况也就是O(n),可能还会小于这个值。

对于put操作，咱们晓得，数组插入元素的老本是昂扬的，HashMap奇妙的应用链表和红黑树代替了数组插入元素须要挪动后续元素的耗费。这样在最好的状况下，插入一个元素，该index地位恰好没有元素的话，工夫复杂度就是O(1),当该地位有元素且为链表或者红黑树的状况下，工夫复杂度会回升，然而最坏的状况下也就是O(n)。

3.1.2 HashMap什么时候从单节点转成链表又是什么时候从链表转成红黑树？

单节点转链表很简略，当依据新退出的值计算出来的index处有元素时，若元素为单节点，则从节点转为链表。
链表转红黑树有两个条件：

链表长度大于TREEIFY_THRESHOLD，默认阈值是8
HashMap长度大于64

当同时满足这两个条件，那么就会触发链表转红黑树的操作。

3.2 HashMap初始化时为什么要给自定义的初始容量？

为啥前辈们都要求定义一个HashMap的时候肯定要应用构造函数HashMap(int initialCapacity)指定初始容量呢？

在阿里的《Java开发手册》中是这样阐明的：

【举荐】汇合初始化时，指定汇合初始值大小。
阐明：HashMap 应用 HashMap(int initialCapacity) 初始化，
正例：initialCapacity = (须要存储的元素个数 / 负载因子) + 1。留神负载因子（即 loader
factor）默认为 0.75，如果临时无奈确定初始值大小，请设置为 16（即默认值）。
反例：HashMap 须要搁置 1024 个元素，因为没有设置容量初始大小，随着元素一直减少，容
量 7 次被迫扩充，resize 须要重建 hash 表，重大影响性能。

这个问题在HashMap源码中是不言而喻的，每次put函数中都会查看以后size是否大于threshold，如果大于就会进行扩容，新容量是原来容量的二倍。那么问题就来了，当你要存大量数据到HashMap中而又不指定初始容量的话，扩容会被一次接一次的触发，十分耗费性能。

而初始容量和负载因子给多少好呢，日常开发中如无必要不倡议动负载因子，而是依据要应用的HashMap大小确定初始容量，这也不是说为了防止扩容初始容量给的越大越好，越大申请的内存就越大，如果你没有这么多数据去存，又会造成hash值过于离散。

3.3 HashMap如何保障容量始终是2的幂

HashMap应用办法tableSizeFor()来保障无论你给值是什么，返回的肯定是2的幂：

  static final int tableSizeFor(int cap)    {        int n = cap - 1; // 作用：保障当cap为2的幂时，返回原值而不是二倍，如8 返回8 而不是16        n |= n >>> 1;        n |= n >>> 2;        n |= n >>> 4;        n |= n >>> 8;        n |= n >>> 16;        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;    }

首先咱们来看操作：

           n |= n >>> 1;        n |= n >>> 2;        n |= n >>> 4;        n |= n >>> 8;        n |= n >>> 16

假如 n=01000000, n |= n >>> 1后 n=01100000，n |= n >>> 2后n=01111000,n |= n >>> 4;后n=01111111,咱们能够发现，上述5步操作能够将一个32位数第一位为1的前面所有位全变为1。这样再执行n + 1操作后，该数就必为2的幂次方了。如01111111+1 = 10000000。
那又为什么要保障肯定是2的幂次方呢？不是不行吗？

3.3.1 HashMap为何要保障容量始终是2的幂

说到这个问题不得不说执行put()办法时，是如何依据hash值在table中定位。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)    {        ......        if ((p = tab[i = (n - 1) & hash]) == null)            tab[i] = newNode(hash, key, value, null);        ......

能够看到，它应用了一个 (n - 1) & hash的操作，n为以后hashmap的容量，而容量肯定为2的幂次方，n-1的二进制低位都为1，举例：16=0000000000010000，15=0000000000001111，这样的解决益处在于，当执行(n - 1) & hash的操作时，元素的地位仅取决于低位而与高位无关（这种无关性随着HashMap容量的增大而减小），这个逻辑长处是，无论你的hash值有多大，我都锁定了你的取值范畴小于以后容量，这样做防止了hash值过于离散的状况，而当HashMap扩容时又能够同时增大hash值的取值范畴，毛病是减少了hash碰撞的可能性，为了解决这个问题HashMap批改了hash值的计算方法来减少低位的hash复杂度。

3.3.2 HashMap计算hash值

不废话，间接上源码：

    static final int hash(Object key)    {        int h;        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);    }

hash办法用 key的hash值异或上key的hash值的高16位，为什么要这样做呢？
首先，h>>>16 的值高16位都为0，这样h^(h>>>16)时，高16位的值不会有任何变动，然而低16位的值混淆了key的高16位的值，从而减少了hash值的复杂度，进一步缩小了hash值一样的概率。

3.4 HashMap为什么是线程不平安的

在Jdk1.7中，造成HashMap线程不平安的起因之一是transfer函数，该函数应用头查法在多线程的状况下很容易呈现闭环链表从而导致死循环，同时还有数据失落的问题，Jdk1.8中没有transfer函数而是在resize函数中实现了HashMap扩容或者初始化操作，resize采纳尾插法很好的解决了闭环链表的问题，然而仍旧防止不了数据笼罩的问题。
在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;        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;        ......

在执行完 if ((tab = table) == null || (n = tab.length) == 0)判断且为true的状况下，会间接进行赋值，然而在多线程的环境下，当两个线程同时实现判断，线程1刚赋值完，线程2再进行赋值，就造成了数据笼罩的问题。
这只是最简略的景象，咱们要想线程平安，首先要有多线程平安的解决逻辑，很显著HashMap是没有这样的逻辑的，那么很多为单线程设计的逻辑就很大可能出问题，所以HashMap为什么是线程不平安的？它自身设计就不反对多线程下的操作，所以不该有此问。
如果想要线程平安的应用基于hash表的map，能够应用ConcurrentHashMap，该实现get操作是无锁的，put操作也是分段锁，性能很好。
所以说术业有专攻，每个容器的实现都有它对应的优缺点。咱们须要学会的是剖析面对的每一种状况，正当的应用不同的容器去解决问题。

HashMap根本的原理和对应实现就说到这里了，更深刻的话题如：红黑树插入节点、均衡红黑树、遍历红黑树，能够间接看红黑树对应的原理和实现。

须要源码正文的请戳这里源码解析

最初，最近很多小伙伴找我要Linux学习路线图，于是我依据本人的教训，利用业余时间熬夜肝了一个月，整顿了一份电子书。无论你是面试还是自我晋升，置信都会对你有帮忙！

收费送给大家，只求大家金指给我点个赞！

电子书 | Linux开发学习路线图

也心愿有小伙伴能退出我，把这份电子书做得更完满！

有播种？心愿老铁们来个三连击，给更多的人看到这篇文章

举荐浏览：

干货 | 程序员进阶架构师必备资源免费送
神器 | 反对搜寻的资源网站