HashMap是如何工作的_LoveIT的博客

一、认识HashMap

HashMap最早在jdk 1.2就出现了，直到jdk1.7都没有太大的改动：

jdk1.7及以前采用的存储结构是采用了数组+链表，jdk1.8的存储结构是数组+链表+红黑树

HashMap的底层其实就是一个哈希表，通过哈希表可以实现O（1）的查询效率，HashMap允许存储一个key-value都为null的元素（这一点Hashtable不可以），HashMap在多线程环境下没法保证对元素的操作是线程安全的。下面我们就来一步步分析，并针对特定问题给出对应的解决方法。

二、深入分析HashMap

1、底层数据结构

在jdk1.7以前HashMap的底层数据结构是数组+链表的存储结构：

在jdk1.8以后采用了数组+链表+红黑树的存储结构：

在HashMap的数组里存储着Key-Value这样的实例，在jdk1.7以前叫Entry，jdk1.8以后叫的Node，名字变了，但是本质一样。每一个节点都会保存自身的hash、key、value、以及下个节点，我看看Node的源码。

2、HashMap的属性和构造方法

重要的属性

//默认的Map大小 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 
//Map的最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;   
//链表树化阈值 8，链表长度大于等于8才会转化为红黑表
static final int TREEIFY_THRESHOLD = 8;
//树转链表的阈值 6，小于等于6才会转化为链表
static final int UNTREEIFY_THRESHOLD = 6;
//Hash表的基本数组，Node数组
transient Node<K,V>[] table;  
//key-value对的数量
transient int size; 
//table当前的阈值
int threshold;
//table当前的加载因子
final float loadFactor;

构造方法

/**
* 构造一个加载因子是0.75并且初始容量是16的HashMap
*/
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted  
}  
/**
* 构造一个加载因子是0.75并且初始容量是initialCapacity的最近2的幂大小的HashMap
*/
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
* 构造一个加载因子是指定加载因子并且初始容量是initialCapacity的最近2的幂大小的HashMap
*/
public HashMap(int initialCapacity, float loadFactor) {                  
    if (initialCapacity < 0)                                             
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);             
    if (initialCapacity > MAXIMUM_CAPACITY)                              
        initialCapacity = MAXIMUM_CAPACITY;                              
    if (loadFactor <= 0 || Float.isNaN(loadFactor))                      
        throw new IllegalArgumentException("Illegal load factor: " +     
                                           loadFactor);                  
    this.loadFactor = loadFactor; 
    //tableSizeFor()方法将我们传入的大小值转换为据这个数最小的2的幂，但是有没有觉得这里把初始容量赋给阈值是不是有点奇怪呢？答案在resize()方法中
    this.threshold = tableSizeFor(initialCapacity);                      
}   

/**
* 根据已有的Map构造一个新Map
*/
public HashMap(Map<? extends K, ? extends V> m) { 
    this.loadFactor = DEFAULT_LOAD_FACTOR;        
    putMapEntries(m, false);                      
}

这里有几个点需要关注：

阿里Java编程规范中为什么要求指定HashMap的容量？

HashMap扩容是非常非常消耗性能的，Java7中每次扩容先创建2倍当前容量的新数组，然后再将老数组中的所有元素再次通过hash&(length-1)的方式重新散列到新的数组中； Java8中HashMap虽然不需要重新根据hash值散列后的新数组下标，但是由于需要遍历每个Node数组的链表或红黑树中的每个元素，根据元素key的hash值与原来老数组的容量的关系来决定放到新Node数组哪一半(2倍扩容)，还是需要时间的；具体的扩容原理可以参考下面resize()的解析。

总之就是一句话：随着数据量的快速增加，HashMap会发生多次扩容，而HashMap中的扩容机制决定了每次扩容都需要重建hash表，是非常影响性能的。

HashMap指定容量初始化后，底层Hash数组已经被分配内存了吗？

通过上面的HashMap的构造方法的源码可以知道，HashMap在指定容量之后并没有直接给底层的Node数组分配空间。在jdk1.8中真正分配空间是在第一次put元素的时候由resize()方法执行的，下面会详细说到。

HashMap是如何保证用户输入任意初始容量最终HashMap的容量始终是2的整数幂的？

既然都说道这了，我们不妨来看看tablSizeFor()方法的实现吧！

这个方法的作用就是返回一个给定数字的最小的2的幂。下面我们来分析一下这个方法：

为什么要对给定的容量cap-1呢？

这是为了防止原本给定的容量就是2的幂了，那么进过下面5次右移就会把容量扩大为原来的2倍。举个例子，比如传了一个容量值为10：

最后判断一下，发现n不小于0并且n不大于最大容量就把n+1 即：（0000 1111）+1 ===> (0001 0000) ，也就是2^4=16。

3、存储元素的put()方法

通常我们会使用HashMap的put方法网HashMap中存数据，那么在我们调用了put()之后发生了那些事情呢？我们打开源码看看：

可以看到，put()方法只是对putVal()方法进行了一次包装，putVal()有几个形参，从左向右依次是：key的hash值、key、value、是否仅允许key不存在再存放。

HashMap中计算key的hash值的方法

jdk1.8中hash()算法的实现：

//jdk1.8中hash算法
static final int hash(Object key) {
    int h;
	//如果key==null 那么将会被存储在Hash数组的第一个槽位table[0]
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

对比jdk1.7中的计算key的hash算法的方法

//对比jdk1.7中的hash算法
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
         return sun.misc.Hashing.stringHash32((String) k);
    }
　　// 先取key的hashCode再和hashSeed进行异或运算
    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

在这两个jdk版本中的hash()算法的实现是不同的，但基本逻辑没有变：都是先获取了key的hashCode，然后对这个hashCode进行了移位和异或运算。

HashMap的hash值是如何计算的？为什么要这么计算？

JDK 1.8 中，hash值是通过对key的hashCode() 的高 16 位异或低 16 位实现的：(h = k.hashCode()) ^ (h >>> 16)。主要是从速度，功效和质量来考虑的，减少系统的开销，也不会造成因为高位没有参与下标的计算，从而引起的碰撞。

对比发现jdk1.7中的hash()算法的移位操作比jdk1.8中的复杂，这样设计是为什么呢？

因为在jdk1.8中引入了红黑树后对于hash()算法就不需要有那么高的要求了，就算是不够散列也有红黑树来兜底，但是jdk1.7没有红黑树，为了保证元素的散列性，hash()算法应该尽可能的将key的hashCode的每一位都让他参与到计算中，即只要key的hashCode中任何一位发生变化就会对最终的结果产生影响。

拿到hash值之后，就到了putVal()中真正的处理元素了。下面是putVal()的源码：

putVal()方法的逻辑：

第一个if处判断当前的table数组是否为空，如果为空就进入resize()方法初始化一个table数组。在jdk1.8中resize()方法不仅可以扩容，还可以初始化table数组。
第二个if是判断在table[i]位置是否有元素，如果没有就直接new一个Node放进去即可。这里需要注意的是在计算i这个值的时候采用的算法：(n-1)&hash，为什么要这么做呢？通常我们实现的Hash表都是采用hash%数组长度，并且数组长度我们建议最好是质数。在这里为什么不用%操作呢？原因如下：

首先这么做肯定可以达到和取模一样的效果，并且位操作&的效率更高

n表示table当前的容量，但是我们知道table的容量是2的幂，把这个数-1就得到了一个低位连续是1的一个数（二进制表示），此时再做按位与，数组的索引值就完全取决于hash值了。

进入了第三个条件就是说明当前table存在但是table[i]的位置发生了hash碰撞。接下来就是解决hash碰撞的以及当链表长度操作8之后转化为红黑树的逻辑了：

在第三个条件中又存在三个条件：

第一个条件判断插入的新值是否在HashMap中已经存在，如果是的，就会把这个值先取出来，然后在最后的一个if判断中进行修改

第二个条件就说明插入的新值在HashMap中不存在，此时判断当前链表是否已经树化了，如果被树化就调用putTreeVal()把新值修改到红黑树中

第三个条件是插入的新值在HashMap中不存在并且链表还没有树化，可以看到，jdk1.8中采用了尾插法把新的结点插入的（这里一定要注意，jdk1.7采用的是头插法）。 并且在插入的过程中还在不断的监控链表的长度，如果链表的长度一旦>=8了就立即调用treeifyBin()方法将链表转换为红黑树

最后在插入成功之后会进行比较++size>threshlid是否成立，如果成立说明需要扩容了。

总结一下put()方法的流程：

（1）通过put()方法传入key-vlaue，并调用hash函数计算出key的hash值，jdk1.8中的hash函数是如果key是null，那么hash=0,即key为null的元素将存储在Hash表的第一个位置；否则hash=(h=key.hashCode())^(h>>>16)

（2）调用到putVal(...)方法中，首先判断当前Hash表是否初始化了，如果没有初始化则会调用resize()方法执行初始化，否则进入下一步；

（3）根据hash值计算出key-value键值对的槽位（i=(n-1)&hash），如果槽位table[i]还没有元素，那就直接新添加的key-value键值对实例化成Node添加到哈希表中；如果槽位table[i]已经有元素了，那就进入下一步；

（4）如果发生了hash冲突，那就要还要判断此时处理冲突的情况是什么

如果哈希表中的key和待插入的新元素的key相等并且它们的equals()方法相等，那么就会执行元素值替换操作；

否则如果此时槽位已近变成了红黑树了，那就调用**putTreeValur()**把值插入到红黑树中
若此时的数据结构是链表，从链表头遍历每个结点，如果key相等并且equals()方法相等那就执行值替换操作，否则执行尾插，在链表尾部插入新元素，插入之后判断链表的长度是否大于等于树化阈值8，如果达到了树化阈值将会调用treeifyBin()执行树化逻辑，最后能不能树化，还需要看当前哈希数组的长度是否大于最小树化容量64，如果达不到那就不会执行树化逻辑而是执行扩容逻辑；

（5）最后当map实际数大小等于threshold容量的阈值时，会进行两倍扩容

最后结合流程图再来理解一下put()方法的流程：

了解了HashMap的put流程，我们来看一下常见的额面试问题是咋问题的（~~刁难的~~）？

HashMap为什么只有当链表长度大于8并且哈希数组的容量大于64时才转红黑树？

红黑树的插入、删除和遍历的最坏时间复杂度都是O(lgn)，因此，意外的情况或者恶意使用下导致hashcode()方法的返回值很差时，只要Key具有可比性，性能的下降将会是"优雅"的。但由于TreeNodes的空间占用是常规Nodes的两倍，所以只有桶中包含足够多的元素以供使用时，我们才应该使用树。那么为什么这个数字会是8呢？看HashMap源码中的一段注释：

理想情况下，在随机哈希代码下，桶中的节点多少的频率遵循泊松分布，上图展示了桶长度k的频率表。由频率表可以看出，同一个Hash桶位冲突达到8的概率非常非常小（千万分之六）。所以作者应该是根据概率统计而选择了8作为阀值，由此可见，这个选择是非常严谨和科学的。

红黑树简单介绍

红黑树（Red Black Tree）是一个自平衡的二叉查找树，但是每个节点上增加一个存储位表示节点的颜色（红色或黑色），红黑树的查找、删除、插入操作最坏的时间复杂度都可以达到O(lgn)。红黑树是牺牲了严格的高度平衡的优越条件为代价，红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。

红黑树的查询性能略微逊色于AVL(平衡二叉查找树)树，因为他比AVL树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较；

但是，红黑树在插入和删除上完胜AVL树，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小得多。

总的来说，红黑树除了符合二叉查找树的基本特性外，还具有以下几个特性：

红黑树的结点是红色的或黑色的；
红黑树的根节点是黑色的；
叶子节点（NULL结点）都是黑色的；
每个红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）；
从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点；
新加入到红黑树的节点为红色节点。

为什么HashMap初始容量是1<<4?

（1）首先用位运算而不直接写个16，这样是为了位运算的方便（比如后面扩容时的写法就是newCap = oldCap << 1），位运算比算数计算的效率高了很多。
（2）再者使用16这种类型的数是为了摆脱在计算某个key的桶位的时候的使用取模运算带来的性能消耗，HashMap采用2的幂整数与Length-1按位与，既可以达到取模运算的效果，也可以简化运算提高效率；
（3）因为在使用哈希表容量是2的幂的数字的时候，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。

4、Hash表的扩容resize()原理

HashMap中有两种情况会触发扩容：

Map的实际大小等于扩容阈值（threshold=加载因子*初始容量）的时,会执行2倍扩容；

当hash表中某个桶的链表长度大于树化阈值(TREEIFY_THRESHOLD=8)，但是hash数组的容量小于最小树化容量(MIN_TREEIFY_CAPACITY=64)时会执行2倍扩容；

除了上面两种情况之外，还有一种情况也会调用resize()方法，但不是扩容逻辑——hash表的初始化

是不是一看到这么长的源码就没有读下去的欲望了？不要怕，接下来我们分解一步步来：

（1）确定新容量和新阈值或者初始化Hash表

首先获取当前当前哈希表的长度，如果哈希表还未初始化那长度就是0；
获取当前阈值threshold,并初始化新的容量newCap和新阈值newThr为0；
接下来分三种情况计算出新容量和新阈值：

1）如果当前哈表容量oldCap>0，并且当前哈希表的容量大于等于最大允许容量（MAXIMUM_CAPACITY=2^30），那就把阈值设为最大的整数，然后返回不允许再扩容了；否者将新的容量设置为当前容量的2倍，如果设置后新的容量<最大允许容量并且当前容量>=默认容量（16）就会把新的阈值也设置为当前阈值的2倍

2）第二个成立表示哈希表还没初始化大事阈值初始化了（oldThr>0），此事会将新的容量设置为当前阈值。为什么呢？因为在构造方法中将算出来的容量设置给了阈值。

3）最后一种情况就是哈希表和阈值都没有初始化，那就把新的容量设置为默认容量16，新的阈值设置为默认加载因子0.75*默认容量16=12

随后判断一下新的阈值是否为0，如果为0那就根据容量和加载因子计算出一个新阈值后将阈值更新;
最后更新阈值，并实例化一个newCap大小的Node数组，完成哈希表容量的扩大；

（2）把当前哈希表中的数据复制到新哈希表中

到这一步扩容动作已经完成了，现在Node数组已经是之前的2倍了，现在需要干的事情就是从老哈希表中将数据重新hash并散列到新表中。主要逻辑如下：

核心思路：遍历老的哈希表，没有元素的槽位不管，只处理有元素的槽位；处理有元素的槽位的逻辑分为三大部分：

1）如果这个槽位没有后继结点了（没有形成链表），就重新计算元素移动到新的哈希表中位置并直接移动过去，重新计算桶位的算法还是：e.hash&(newCap-1)

2）如果槽位有后继结点并且已近树化了（已经是红黑树了），那就将红黑树拆分后，在新的哈希表中重新hash并散列到新的Node数组中

3）如果槽位有后继结点但是没有树化（已经是链表了），那就还是用尾插法把元素移动到新的哈希表中，需要注意的是：

A：扩容后，若e.hash&oldCap=0，那么元素在扩容后的位置=原始位置(newTab[j] = loHead)

B：扩容后，若hash&oldCap!=0，那么元素在扩容后的位置=原始位置+旧数组大小( newTab[j + oldCap] = hiHead)。

到这里HashMap的扩容机制原理大致清楚了后，我们来看一下常见的面试题如何提问的（~~刁难的~~）？

HashMap的扩容分几个步骤？

HashMap的扩容可以分为两个步骤： * 根据老哈希表的大小计算出新哈希表的新容量以及新阈值，并创建一个新的Node空数组，长度是原数组的2倍 * 遍历原Entry数组，把所有的Entry重新Hash到新数组

为什么要重新Hash呢，直接复制过去不香么？

因为HashMap的元素槽位是通过（n-1）&hash计算出来的，其中n是HashMap的容量，扩容之后Map的容量发生了变化，因此需要重新计算元素的槽位

为啥之前用头插法，java8之后改成尾插了呢？

在jdk1.7中，当多线程同时扩容时, 执行resize扩容时会调用transfer方法重新散列table散列元素为从头插入, 这里容易形成环形链表,调用get方法或put方法遍历这个Hash数组的位置的链表，如果元素key不存在，就在这个循环链表中无限循环遍历了，因为停止循环的条件就是：尾结点的指针为null

使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

总的来说就是： Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系，从而容易导致形成循环链表。

Java8在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。

那是不是意味着Java8就可以把HashMap用在多线程中呢？

我认为即使不会出现死循环，但是通过源码看到put/get方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证。

5、Hash表获取元素get()原理

调用get方法时传入key，首先还是调用hash函数计算出key的hash值（hash=(h=key.hashCode())^(h>>>16)）：

计算出key的hash值之后调用getNode(...)到Map中获取结点元素

首先判断当前哈希表是否为空，如果为空直接返回null；
如果哈希表不空，就会计算key的桶位table[(n-1)&hash]，如果桶位为空还是会返回null；
如果哈希表不为空并且key在HashMap中存在，那就首先检查一下hash表中的这个元素是不是要找的值（判定的标准是equals方法返回true），如果是就直接返回vlaue,如果不是还会在判断一下是否存在后继结点，如果不存在直接返回null
如果存在后继结点，那么首先判断一下是红黑树还是链表，如果是红黑树那就到红黑树中取值，如果是链表那就从头开始遍历链表找到值后返回。

最后关于HashMap我总结了一些常见的面试题，大家可以通过题目检测一下自己的学习成果。链接：关于HashMap几个刁钻的面试题，第四个我就跪了