HashMap是如何工作的

声明:基于jdk1.8源码。

一、认识HashMap

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

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

HashMap允许存储一个键和值都为null的元素(这一点Hashtable不可以),HashMap在多线程环境下没法保证对元素的操作是线程安全的。下面我们就来一步步分析,并针对特定问题给出对应的解决方法。

二、深入分析HashMap

1、底层数据结构

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

jdk1.8采用了数组+链表+红黑树的存储结构:

jdk1.8的Node结点,实现基本和jdk1.7的Entry类似,只是名字变了。

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
static final int TREEIFY_THRESHOLD = 8;
//树转链表的阈值 6
static final int UNTREEIFY_THRESHOLD = 6;
//Hash表的基本数组,table数组
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);                      
}

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

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

首先为什么要对给定的容量cap-1呢?这是为了防止如果给定的容量就是2的幂了,那么进过下面4次右移就会把容量扩大为原来的2倍,且看我慢慢分析。举个例子,比如传了一个容量值为10:

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

3、存储元素put()方法原理

我们向HashMap存储元素的时候通常使用的就是put()方法,那么在我们调用了put()之后发生了那些事情呢?我们打开源码看看:

可以看到,put()方法只是对putVal()方法进行了一次包装,首先我们看一下在jdk1.8中hash()算法是如何实现的:

//jdk1.8中hash算法
static final int hash(Object key) {                              
    int h;                                                       
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}    

//对比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进行了移位并且异或运算。但是可以明显看到,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

(2)计算出key的hash值

(3)根据hash值判断vlaue存放的位置,再次之前他会先判断table是否已经初始化了,如果没有就会先初始化;如果初始化过了就会判断vlaue应该存放的位置是否已经有元素了,如果没有那就把value直接存放在数组中即可

(4)如果发生了hash冲突,那就要还要判断此时处理冲突使用的数据结构是什么

(5)如果此时使用的是红黑树,那就调用putTreeValur()把值插入到红黑树中

(6)若此时的数据结构是链表,遍历链表计算出插入之后链表长度是否大于等于8

(7)插入之后大于8了,就要先调整为红黑树,在插入

(8)插入之后不大于8,那么就直接插入到链表尾部即可

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

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

在插入新的结点后如果当前数组的元素个数大于阈值了就会进行扩容操作,或者刚开始哈希表的初始化都是在resize()方法中进行的,下面我们一起来分析一下他的源码:

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

(1)确定新容量和新阈值

  • 首先它判断当前hash表是否为空,如果为空就把当前容量设为0,否者拿到当前哈希表的容量oldCap;

  • 拿到当前阈值oldThr,并初始化新的容量newCap和阈值newThr为0

  • 接下来三种情况:

  • 1)如果当前哈表容量oldCap>0,并且当前哈希表的容量大于等于最大允许容量,那就把阈值设为最大的整数;否者将新的容量设置为当前容量的2倍,如果设置后新的容量<最大允许容量并且当前容量>=默认容量(16)就会把新的阈值也设置为当前阈值的2倍
  • 2)第二个成立表示哈希表还没初始化大事阈值初始化了(oldThr>0),此事会将新的容量设置为当前阈值。为什么呢?因为在构造方法中将算出来的容量设置给了阈值。
  • 3)最后一种情况就是哈希表和阈值都没有初始化,那就把新的容量设置为默认容量16,新的阈值设置为默认加载因子0.75*默认容量16=12
  • 最后判断一下新的阈值是否为0,如果为0没那就算出一个阈值字后将阈值更新

(2)申请新的哈希表

至此完成了对新哈希表的创建,这个哈希表的容量是老哈希表的2倍

(3)把当前哈希表中的数据复制到新哈希表中

  • 在真正扩容之前会判断一下当前的哈希表oldTab是否是空的,如果是空的表示这是来初始化哈希表的,这在前两步就完成了,在这里直接返回就可以了。

  • 如果oldTab!=null,那就需要把哈希表中的数据复制到新哈希表中

遍历老的哈希表,没有元素的槽位不管,只处理有元素的槽位

处理有元素的槽位的逻辑分为三大部分:

1)如果这个槽位没有后继结点了,就直接把元素移动到新的哈希表中,存放的位置是通过hash&(newCap-1)算出来的

2)如果槽位有后继结点并且已近树化了,那就红黑树拆分后,在新的哈希表中重新组装

3)如果槽位有后继结点但是没有树化,那就还是用尾插法把元素移动到新的哈希表总,需要注意的是:

  • A:扩容后,若hash&oldCap=0,那么元素在扩容后的位置=原始位

  • B:扩容后,若hash&oldCap!=0,那么元素在扩容后的位置=原始位置+旧数组大小。

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

首先还是计算出key的hash值,然后调用getNode()方法获取到值

  • 首先判断当前哈希表是否为空,如果为空直接返回null;
  • 如果hash表不空需要再判断key在HashMap中是否存在,如果不存在,还是直接返回null;
  • 如果哈希表不为空并且key在HashMap中存在,那就首先检查一下hash表中的这个元素是不是要找的值,如果是就直接返回vlaue,如果不是还会在判断一下是否存在后继结点,如果不存在直接返回null
  • 如果存在后继结点,那么首先判断一下是红黑树还是链表,如果是红黑树那就到红黑树中取值,如果是链表那就从头开始遍历链表找到值后返回。

三、安全失败机制(fail-safe)和快速失败机制(fail-fast)

1、快速失败机制 fail-fast

在使用迭代器遍历集合的时候,如果在遍历过程中集合的元素个数发生变化,就会抛出ConcurrentmodificationException

原理迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个modCount变量,当集合中元素个数发生了变化就会修改modCount的值,当调用hasNext()/next()方法是会判断modCount和exceptedModCount的值是否相等,如果相等就返回继续遍历,否则抛出ConcurrentModificationException,终止遍历。

应用场景:java.util包下的集合类使用了这种机制(Hashtable除外,它使用的是fail-safe),不能在多线程下发生并发修改(迭代过程中被修改)算是一种安全机制吧。

2、安全失败机制 fail-safe

采用安全失败机制的集合容器,在遍历的时候不会直接在原来的内容量上遍历,而是复制一份在复制的副本上遍历。由于遍历是在拷贝的副本上进行的,所以在遍历过程中对原集合所作的修改并不能被迭代器检测到,因此不会引发ConcurrentmodificationException

应用场景:J.U.C包下都是安全失败机制容器,可以在多线程环境下并发的修改和访问。

缺点:基于拷贝内容的优点是避免了Concurrent Modification Exception,但同样地,迭代器并不能访问到修改后的内容,即:迭代器遍历的是开始遍历那一刻拿到的集合拷贝,在遍历期间原集合发生的修改迭代器是不知道的。

四、HashMap刁钻面试题总结

1、HashMap的数据结构是什么?

答:在jdk1.7是采用了数组+链表,jdk1.8采用了数组+链表+红黑树

2、为什么要采用数组+链表作为存储结构?

首先要清楚一个基本的理论:数组查询效率高,只要给一个数组索引就可以立马找到对应的元素,但是插入、删除的效率低;链表插入、删除的效率高,但是查询的效率低。因此HashMap的table使用数组就可以通过一个索引值立即定位到确定到元素的槽位(solt)。但是可能有多个key的hashCode计算出来一样 即发生Hash碰撞,此时HashMap采用了拉链法,即以table数组这个槽位为链表头结点,把发生hash碰撞元素串在一根链表上。而且在jdk1.8进行了进一步优化,即如果链表的长度>8时将会转化为红黑树,当红黑树上的结点<6时又会转换为链表。这一点从源码中就可以看到:

TREEIFY_THRESHOLD是树化阈值为8,UNTREEIFY_THRESHOLD是非树化阈值为6

3、为什么在jdk1.8要使用红黑树,使用二叉搜索树或者平衡树不可以吗?
  • (1)二叉搜索树在给定的数据有序时会出现退化为链表的情况

二叉搜索树的思想是:左子树结点比父节点小,右子树结点比父节点大。当给的数据处于无序状态的时候二叉搜索树的性能非常好,只有O(logn),但是当给的数据有序的时对于二叉搜索树是灾难,基于二叉搜索树规则构建的树会退化为单链表。即如下图所示:

  • (2)平衡树的维护成本太高,不适合HashMap这样有频繁修改的的场景

平衡树(AVL)就是用来解决二叉搜索树会退化为链表对问题二提出的。它的原理如下:

a. 平衡树具有二叉搜索树的全部特性

b. 平衡树要求左子树和右子树的高度差不能超过1

通过平衡树,我们解决了二叉查找树的缺点。对于有 n 个节点的平衡树,最坏的查找时间复杂度也为 O(logn)。 但是由于平衡树要求每个节点的左子树和右子树的高度差至多等于1,这个 要求实在是太严了,导致每次进行插入/删除节点的时候,几乎都会破坏平衡树的第二个规则,进而我们都需要通过 左旋右旋 来进行调整,使之再次成为一颗符合要求的平衡树。

最后就会导致为了维护一个这个平衡树,带来了可能比只是用单链表还高的消耗,这时不可取得。因此为了解决这个问题,工程师们又想到了红黑树。红黑树的性质如下:

a. 具有二叉查找树数的所有特点

b.根节点是黑色的

c.每个叶子节点都是黑色的空节点,即叶子节点不存值

d.任意相邻的结点都不能是相同的颜色

e.任意结点到其任意叶子节点的路径上的黑色结点的数目相同

正是由于红黑树的这些特性,红黑树在插入、删除等操作,不会像平衡树那样,频繁着破坏红黑树的规则,所以不需要频繁调整。但是在效率方面,红黑树确实不及平衡树,可以说使用红黑树就是一种折中的方案。

3、为什么不直接上来就使用红黑树,而是达到阈值了才转化为红黑树?
  • 首先维护一个树的成本比维护一个链表的成本要高

  • 再者设置链表树化的阈值为8是因为链表的长度达到8的概率很低,看HashMap源码中的一段注释:

画红线的翻译过来就是说:在具有良好分布的用户hashCode的用法中,很少使用到红黑树。 理想情况下,在随机hashCodes下,bin中节点的 频率遵循泊松分布 ,默认调整大小阈值为0.75,平均参数约为0.5,尽管 由于存在较大差异调整粒度。 忽略差异,预期列表大小k的出现是(exp(-0.5)* pow(0.5,k)/阶乘(k))。

也就是说,想让一个链表的长度达到8的概率极低,几乎是不可能事件。

因此综合这两点,为啥一定要维护一个红黑树呢?没必要啊!!!

4、说一下HashMap的工作原理

HashMap的底层是数组+单向链表实现的,数组中的每个元素都是链表的头结点,这个链表的类型是HashMap的内部类Node(它实现了Map.Emtry接口),HashMap透过put(K,V)和get(K)方法来放入和取值:

put()方法存储值时

(1)key-value键值对通过put()方法传入,首先调用hash(key)计算出key的hash值

(2)拿到hash值之后,首先判断哈希表是否初始化了,如果没有初始化就调用resize()方法初始化

(3)如果初始化了,然后结合数组长度计算出key应该存放的下标

(4)如果在这个位置没有元素,那就直接把值放入即可,否则就是发生了hash碰撞

  • 如果key的hash值在HashMap中存在,且它们两者 equals 返回 true,则更新键值对;
  • 如果 key 的 hash 值在 HashMap 中存在,但是它们两者 equals 返回 false,则插入链表的尾部(尾插法)或者红黑树中(树的添加方式)。

获取对象时

(1)get()方法将键值对传入,首先还是计算key的hash值

(2)拿到hash值首先判断一下头结点是不是要找的元素,如果是直接返回value;如果不是就看看头结点是否有后继结点,如果没有就返回null

(3)如果头结点有后续结点那就判断如果头结点的类型如果是树就调用红黑树的获取值的方法getTreeNode(),否则还是当做链表处理,从头结点开始遍历,知道hash值相等并且equals返回true是就说明找到目标元素了。

hashCode 是定位的,存储位置;equals是定性的,比较两者是否相等。

5、你知道hash算法的实现吗?为什么要这么实现?

JDK1.8中HashMap中的hash算法的实现是通过:key的hashCode()高16位异或低16位实现的(h=(key.hashCode())^(h>>>16))。

现在的hashCode分布的已经很不错了,而且当发生较大碰撞时也用树形存储降低了冲突。仅仅异或一下,既减少了系统的开销,也不会造成的因为高位没有参与下标的计算(table长度比较小时),从而引起的碰撞。

6、hash中为什么要使用异或操作?

可以保证key的32位hashCode()中是要有一位发生变化,那么真个hash值也会跟着改变。目的是尽可能的减少hash冲突。

7、HashMap 的 table 的容量如何确定?loadFactor 是什么? 该容量如何变化?这种变化会带来什么问题?

(1)HashMap的table数组的容量是通过capaticy参数控制的,默认的数组大小是16,最大额数组大小是2^30。我们可以在HashMap的构造方法中传入指定的容量数值。

(2)loadFatory是装载因子,作用是判断当前哈希表是否可以扩容了。范围是0-1,默认是0.75.和他类似的一个参数是阈值threshold,在一切都是默认值的情况下,阈值是12

(3)扩容时,调用 resize() 方法,将 table 长度变为原来的两倍(注意是 table 长度,而不是 threshold)

这一问之后有可能会再问,加载因子默认为什么设置为0.75?

**选择0.75作为默认的加载因子,完全是时间和空间成本上寻求的一种折衷选择, **

加载因子过高,例如为1,虽然减少了空间开销,提高了空间利用率,但同时也增加了查询时间成本;

加载因子过低,例如0.5,虽然可以减少查询时间成本,但是空间利用率很低,同时提高了rehash操作的次数。

8、jdk1.7和jdk1.8中HashMap有哪些不同?

(1)在jdk1.8中当链表的长度大于等于8的时候会转换诶红黑树;

(2)jdk1.8中采用的是尾插法,而jdk1.7中采用的是头插法;

(3)jdk1.8简化了hash算法;

(4)jdk1.8修改了resize()的逻辑,使得jdk1.8在resize时不会出现循环链表的问题;

(5)jdk1.8中talbe数组的类型改为了Node,jdk1.7中的类型是Entry类型;

如果你说了jdk1.8中采用的是尾插法,而jdk1.7中采用的是头插法,人家就会问jdk1.8为啥使用尾插法?

  • 首先是为了解决在多先线程环境下由于头插法带来的形成环形链表的问题
  • 在jdk1.8中引入了红黑树,为了统计链表总的结点个数,以便判断是否需要树化,于是他就遍历了一遍链表并使用一个binCount的变量计数,当遍历完之指针就是在最后一个节点上指着呢,采用尾插顺理成章
9、HashMap,LinkedHashMap,TreeMap 有什么区别?

LinkedHashMap是HashMap的子类,他维护了一个双向链表,因此他可以保证元素的插入顺序和元素的遍历顺序是相同的;效率比HashMap低。

TreeMap就是一个红黑树的实现,实现 SortMap 接口,能够把它保存的记录根据键排序

10、HashMap和Hashtable的区别?

(1) HashMap的基类是AbstractMap, Hashtable的基类是Dictionary, 他们共同实现了Map接口
(2) HashMap的初始容量是16,Hashtable的初始容量都是11,负载因子都是0.75。但是扩容机制不同, HashMap是旧数组的2×旧表长度, 而Hashtable是2×旧表长度+1
(3) HashMap是非线程安全的,而Hashtable是线程安全的,因为所有的方法都使用了synchronized.
(4) HashMap使用迭代器迭代, Hashtable可以使用迭代器和枚举。
(6) HashMap中K和V都可以是null,但是Hashtable中都不能是null.
(7) HashMap中取消了contains方法,使用了containsKey和containsValue,但是Hashtable中三个方法都有
(9)对象的定位方法不同:
* Hashtable:使用K的hashCode直接作为hash值,和数组长度进行求余运算,得到键值对在数组中的位置,然后再使用equals方法形成链表。
* HashMap:使用K的hashCode进行高低16位异或运算作为hash值,和数组的长度减一进行&运算, 得到键值对在数组中的位置,然后再使用equals方法形成链表。说一下计算桶的位置为什么是这个样子,就是因为扩容的时候是2的n次方进行扩容, hash值在和2的n次方进行求余运算和&运算的结果一样, 但是&运算要快的多。同时正是因为扩容倍数的特殊性,导致扩容后不需要重新键值对在新数组的位置只需要判断K的hash值多出来的那一位是0还是1. 如果是0, 新表中键值对的位置和旧表-样。 如果是1,新表中键值对的位置等于旧表的位置+旧表的长度。
(9)Hashtable由于是线程安全的,因此采用了一种快速失败的机制。允许多个线程同时修改但不会抛出异常;HashMap采用了一种安全失败机制的机制,他不允许在遍历元素的时候,集合发生改,如果发生改变就会抛出异常。

11、Java 中的另一个线程安全的与 HashMap 极其类似的类是什么?同样是线程安全,它与 Hashtable 在线程同步上有什么不同?

ConcurrentHashMap是J.U.C下提供的一个并发容器,他是HashMap的线程安全版本,采用分段锁提高了效率,但是在Hashtable中是将整个hash表使用synchronized锁起来,并发性没有前者好。

留言区

还能输入500个字符