HashMap是如何工作的

一、认识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%数组长度,并且数组长度我们建议最好是质数。在这里为什么不用%操作呢?原因如下:
  1. 首先这么做肯定可以达到和取模一样的效果,并且位操作&的效率更高
  2. 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树为了维持平衡的开销要小得多。

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

  1. 红黑树的结点是红色的或黑色的
  2. 红黑树的根节点是黑色的
  3. 叶子节点(NULL结点)都是黑色的
  4. 每个红色节点的两个子节点都为黑色(红黑树不会出现相邻的红色节点)
  5. 从任意节点出发,到其每个叶子节点的路径中包含相同数量的黑色节点
  6. 新加入到红黑树的节点为红色节点

为什么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几个刁钻的面试题,第四个我就跪了

参考资料

留言区

还能输入500个字符