阅读 2030

那些年,我们又爱又恨的HashMap(一)

一、HashMap集合简介

特点:

  • HashMap是Map接口的一个重要实现类,基于哈希表,以key-value的形式存储数据,线程不安全;
  • null可以作为键,这样的键只能有一个,可以有一个或多个键对应的值为null;
  • 存取元素无序。

底层数据结构:

  • JDK1.8之前,由数组+链表构成,数组是存储数据的主体,链表是为了解决哈希冲突而存在的;
  • JDK1.8以后,由数组+链表+红黑树构成,当链表长度大于阈值(默认为8),并且数组长度大于64时,链表会转化为红黑树去解决哈希冲突。

注意: 链表转化为红黑树之前会进行判断,若果阈值大于8,但是数组长度小于64,这时链表不会转化为红黑树去存储数据,而是会对数组进行扩容。

这样做的原因: 如果数组比较小,应尽量避免红黑树结构。因为红黑树结构较为复杂,红黑树又称为平衡二叉树,需要进行左旋、右旋、变色这些操作才能保证平衡。在数组容量较小的情况下,操作数组要比操作红黑树更节省时间。综上所述:为了提高性能以及减少搜索时间,在阈值大于8并且数组长度大于64的情况下链表才会转化为红黑树而存在。具体参考treeifyBin方法。

HashMap存储数据结构图:

二、HashMap底层存储数据的过程

1.以下面代码所示进行分析:
package hashmap_demo;
import java.util.HashMap;
public class HashMapTest {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("柳岩", 18);
        map.put("杨幂", 28);
        map.put("刘德华", 40);
        map.put("柳岩", 20);
        System.out.println(map);
    }
}
//输出结果:{杨幂=28, 柳岩=20, 刘德华=40}
复制代码
2.HashMap存储过程图:

3.存储过程分析:

1.当执行HashMap<String, Integer> map = new HashMap<>();这行代码创建HashMap实例对象时;在JDK1.8之前,会在构造方法中创建一个长度为16 的Entry[] table数组用来存储键值对;JDK1.8之后,创建数组的时机发生了变化,不是在构造方法中创建数组了,而是在第一次调用put()方法时(即第一次向HashMap中添加元素)创建Node[] table数组。

注意: 创建HashMap实例对象在JDK1.8前后发生了变化,主要有两点:创建的时机发生了变化;数组类型发生了变化,由原来的Entry[]类型变为Node[]类型。

2.向哈希表中存储柳岩-18,会根据柳岩调用String类中重写后的hashCode()方法计算出柳岩对应的哈希值,然后结合数组长度采用某种算法计算出柳岩在Node[]数组中的索引值。如果该索引位置上无数据,则直接将柳岩-18插入到该索引位置。比如计算出柳岩对应的索引为3,如上图所示。

面试题:哈希表底层采用那种算法计算出索引值?还有哪些算法计算索引值?

答:采用key的hashCode()方法计算出哈希值,然后结合数组长度进行无符号右移(>>>)、按位异或(^)、按位与(&)计算出索引值;还可以采用平方取中法、取余数、伪随机数法。

取余数:10%8=2 11%8=3;位运算效率最高,其他方式效率较低。

3.向哈希表中存储杨幂-28,计算出该索引位置无数据,直接插入。

4.向哈希表中存储刘德华-40,假设刘德华计算出的索引也是3,那么此时该索引位置不为null,这时底层会比较柳岩刘德华的哈希值是否一致,如果不一致,则在此索引位置上划出一个节点来存储刘德华-40,这种方式称为拉链法。

补充:索引计算源码p = tab[i = (n - 1) & hash],即索引=哈希值&(数组长度-1),按位与运算等价于取余运算,因为51%16=3,19%16=3,所以会出现同一个数组,索引值相同,但哈希值不同的情况。

5.最后向哈希表中存储柳岩-20柳岩对应的索引值为3。因为该索引位置已有数据,所以此时会比较柳岩与该索引位置上的其他数据的哈希值是否相等,如果相等,则发生哈希碰撞。此时底层会调用柳岩所属String字符串类中的equals()方法比较两个对象的内容是否相同:

相同:则后添加数据的value值会覆盖之前的value值,即柳岩-20覆盖掉柳岩-18

不相同:继续和该索引位置的其他对象进行比较,如果都不相同,则向下划出一个节点存储(拉链法)。

注意点:如果一个索引位置向下拉链,即链表长度大于阈值8且数组长度大于64,则会将此链表转化为红黑树。因为链表的时间复杂度为O(N),红黑树的时间复杂度为O(logN),链表长度多大时O(N)>O(logN)。

三、HashMap的扩容机制

1.HashMap什么时候进行扩容?

首先看添加元素的put()方法流程:

说明:

  • 上图中的size表示HashMapK-V的实时数量,不等于数组的长度;
  • threshold(临界值)=capacity(数组容量)*loadFactory(加载因子),临界值表示当前已占用数组的最大值。size如果超过这个临界值进调用resize()方法进行扩容,扩容后的容量是原来的两倍;
  • 默认情况下,16*0.75=12,即HashMap中存储的元素超过12就会进行扩容。
2.HashMap扩容后的大小是多少?
是原来容量的2倍,即HashMap是以2n进行扩容的。
复制代码
3.HashMap的默认初始容量是多少?

HashMap的无参构造,默认初始值为16,源码如下:

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
复制代码

默认初始值源码:

/**
 * The default initial capacity - MUST be a power of two.
 * 默认初始容量必须是2的幂
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
复制代码

由源码可以看到,HashMap的默认初始容量为1左移4位,即1*2的4次方为16。如果使用HashMap的无参构造进行初始化,第一次put元素时,会触发resize()方法(扩容方法),扩容后的容量为16。这一点和ArrayList初始化过程很相似(使用ArrayList的无参构造初始化时,创建的是一个空数组,当第一次向空数组添加元素时会触发grow()扩容方法,扩容后的容量为10)。

4.指定初始容量为什么必须是2的幂?

HashMap的有参构造,即可以指定初始化容量大小,源码如下:

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
复制代码

即构造一个指定容量和默认加载因子(0.75)的空HashMap

由上面的内容我们知道,当向HashMap中添加元素时,首先会根据key的哈希值结合数组长度计算出索引位置。HashMap为了存取高效需要减少哈希碰撞,使数据分配均匀,采用按位与**hash&(length-1)**计算索引值。

HashMap采用取余的算法计算索引,即hash%length,但是取余运算不如位运算效率高,所以底层采用按位与**hash&(length-1)**进行运算。两种算法等价的前提就是length是2的n次幂。

5.为什么这样就能均匀分布?

我们需要知道两个结论:

  • 2的n次方就是1后面n个0;如2的4次方为16,二进制表示为10000;
  • 2的n次方-1就是n个1;比如2的4次方-1位15,二进制表示为1111。

举例说明为什么数组长度是2的n次幂可以均匀分布:

按位与运算:相同二进制位上都是1,结果为1,否则为0。
假设数组长度为23次幂8,哈希值为3,即3&(8-1)=3,索引为3;
假设数组长度为23次幂8,哈希值为2,即2&(8-1)=2,索引为2;
运算过程如下:
3&(8-10000 0011 -->3
0000 0111 -->7
----------------
0000 0011 -->3

2&(8-10000 0010 -->2
0000 0111 -->7
----------------
0000 0010 -->2

结论:索引值不同,不同索引位置都有数据分布,分布均匀。
复制代码

假设数组长度不是2的n次幂,比如长度为9,运算过程如下:

假设数组长度为9,哈希值为3,即3&(9-1)=3,索引为0;
假设数组长度为9,哈希值为2,即2&(9-1)=2,索引为2;
运算过程如下:
3&(9-10000 0011 -->3
0000 1000 -->8
----------------
0000 0000 -->0

2&(9-10000 0010 -->2
0000 1000 -->8
----------------
0000 0000 -->0

结论:索引值都为0,导致同一索引位置上有很多数据,而其他索引位置没有数据,致使链表或红黑树过长,效率降低。
复制代码

注意: hash%length等价于hash&(length-1)的前提条件是数组长度为2的n次幂。由于底层采用按位与运算计算索引值,所以需要保证数组长度必须为2的n次幂。

6.如果指定的初始容量不是2的n次幂会怎样?
这时HashMap会通过位运算和或运算得到一个2的幂次方数,并且这个数是离指定容量最小的2的幂次数。比如初始容量为10,经过运算最后会得到16。
复制代码

该过程涉及到的源码如下:

//创建HashMap集合对象,并指定容量为10,不是2的幂
HashMap<String, Integer> map = new HashMap<>(10);
//调用有参构造
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//this关键字继续调用
public HashMap(int initialCapacity, float loadFactor) {//initialCapacity=10
        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;
        this.threshold = tableSizeFor(initialCapacity);//initialCapacity=10
}
//调用tableSizeFor()方法
/**
* Returns a power of two size for the given target capacity.
* 返回指定目标容量的2的幂。
*/
static final int tableSizeFor(int cap) {
     int n = cap - 1;
     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;
}
复制代码

下面分析tableSizeFor()方法:

  • int n = cap - 1;为什么要减1操作呢?
这是为了防止`cpa`已经是2的幂了。如果`cpa`已经是2的幂,又没有执行减1的操作,则执行完下面的无符号右移后,返回的将为`cap`的2倍。
复制代码
  • n等与0时,返回1,这里不讨论你等于0的情况。
  • |表示按位或运算:运算规则为相同二进制位上都是0,结果为0,否则为1。

第1次运算:

int n = cap - 1;//cap=10,n=9
n |= n >>> 1;//无符号右移1位,然后再与n进行或运算
00000000 00000000 00000000 00001001  //n=9
00000000 00000000 00000000 00000100  //9无符号右移1位变为4
-----------------------------------------------
00000000 00000000 00000000 00001101  //按位或运算结果为13,即此时n=13
复制代码

第2次运算:

int n = 13
n |= n >>> 2;
00000000 00000000 00000000 00001101  //n=13
00000000 00000000 00000000 00000011  //13无符号右移2位变为3
------------------------------------------------
00000000 00000000 00000000 00001111  //按位或运算结果为15,即此时n=15
复制代码

第3次运算:

int n = 15
n |= n >>> 4;
00000000 00000000 00000000 00001111  //n=15
00000000 00000000 00000000 00000000  //15无符号右移4位变为0
------------------------------------------------
00000000 00000000 00000000 00001111  //按位或运算结果为15,即此时n=15
复制代码

接下来的运算结果都是n=15,由于最后有一个n + 1操作,最后结果为16。

总结: 由以上运算过程可以看出,如果指定的初始容量不是2的n次幂,经过运算后会得到离初始容量最小的2幂。

四、HashMap源码分析

1.成员变量
private static final long serialVersionUID = 362498820763181265L; //序列化版本号
复制代码
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //初始化容量,必须是2的n次幂
复制代码
static final int MAXIMUM_CAPACITY = 1 << 30; //集合最大容量:2的30次幂
复制代码
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认的加载因子
/**1.加载因子是用来衡量HashMap的疏密程度,计算HashMap的实时加载因子的方法为:size/capacity;
  *2.加载因子太大导致查找元素效率低,太小导致数组的利用率低,默认值为0.75f是官方给出的一个较好的临界值;
  *3.当HashMap里面容纳的元素已经达到HashMap数组长度的75%时,表示HashMap太挤了,需要扩容,而扩容这个过程涉及到rehash、复制数据等操作,非常消耗性能,所以开发中尽量减少扩容的次数,可以通过创建HashMap集合对象时指定初始容量来尽量避免扩容;
  *4.同时在HashMap的构造方法中可以指定加载因子大小。
  */
HashMap(int initialCapacity, float loadFactor) //构造一个带指定初始容量和加载因子的空HashMap
复制代码
static final int TREEIFY_THRESHOLD = 8; //链表转红黑树的第一个条件,链表长度大于阈值8
复制代码
static final int UNTREEIFY_THRESHOLD = 6; //删除红黑树节点时,当红黑树节点小于6,转化为链表
复制代码
static final int MIN_TREEIFY_CAPACITY = 64; //链表转红黑树的第二个条件,数组长度大于64
复制代码

五、常见面试题

1.发生哈希碰撞的条件是什么?
两个对象的索引相同,并且hashCode(即哈希值)相等时,会发生哈希碰撞。
复制代码
2.如何解决哈希冲突?
JDK1.8之前,采用链表解决;JDK1.8之后,采用链表+红黑树解决。
复制代码
3.如果两个key的hashCode相同,如何存储?
使用equals比较内容是否相同:

相同:后添加的value值会覆盖之前的value值;

不相同:划出一个节点存储(拉链法)。
复制代码
4.HashMap的底层数据结构?

JDK1.8:数组+链表+红黑树。其中数组是主体,链表和红黑树是为解决哈希冲突而存在的,具体如下图所示:

5.JDK1.8为什么引入了红黑树?红黑树结构不是更复杂吗?

JDK1.8以前HashMap的底层数据是数组+链表,我们知道,即使哈希函数做得再好,哈希表中的元素也很难达到百分之百均匀分布。当HashMap中有大量的元素都存在同一个桶(同一个索引位置),这个桶下就会产生一个很长的链表,这时HashMap就相当于是一个单链表的结构了,假如单链表上有n个元素,则遍历的时间复杂度就是O(n),遍历效率很低。针对这种情况,JDK1.8引入了红黑树,遍历红黑树的时间复杂度为O(logn),由于O(n)>O(logn);所以这一问题得到了优化。

6.为什么链表长度大于8才转化为红黑树?

我们知道8是从链表转成红黑树的阈值,在源码中有这样一段注释内容:

/** Because TreeNodes are about twice the size of regular nodes, we use them only when     * bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they         * become too small (due to removal or resizing) they are converted back to plain bins.   * In usages with well-distributed user hashCodes, tree bins are rarely used.  Ideally,   * under random hashCodes, the frequency of nodes in bins follows a Poisson distribution
  * (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on   * average for the default resizing threshold of 0.75, although with a large variance     * because of resizing granularity. Ignoring variance, the expected occurrences of list   * size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:
  *
  * 0:    0.60653066
  * 1:    0.30326533
  * 2:    0.07581633
  * 3:    0.01263606
  * 4:    0.00157952
  * 5:    0.00015795
  * 6:    0.00001316
  * 7:    0.00000094
  * 8:    0.00000006
  * more: less than 1 in ten million
  */
复制代码

翻译过来的的值意思就是说:

红黑树节点所占空间是普通链表节点的两倍,并且链表中存储数据的频率符合泊松分布,我们可以看到,在链表为8的节点上存储数据的概率是0.00000006,这也就表明超过8以后的节点存储数据的概率就非常小了。

由上述分析可以得出:

  • 如果小于阈值8就是用红黑树,会使得结构一开始就很复杂;
  • 如果大于阈值8还使用链表,会导致链表节点不能被充分利用;
  • 所以,阈值8是科学合理的一个值,是空间和时间的权衡值。
7.为什么加载因子设置为0.75?边界值是12?
  • 如果加载因子是0.4,那么16*0.4=6,致使数组中满6个空间就扩容,造成数组利用率太低了;

  • 如果加载因子是0.9,那么16*0.9=14,这样就会使数组太满,很大几率造成某一个索引节点下的链表过长,进而导致查找元素效率低;

  • 所以兼顾数组利用率又考虑链表不要太长,经过大量测试0.75是最佳值。