【后端面经-Java】HashMap详解-EW帮帮网

微信交流群：https://732903.hlcode.cn/?id=NK1fWUR

1. HashMap的家族定位

接口java.util.Map有四个常用的实现类，如图是它们之间的类继承关系。
在这里插入图片描述

下面我将一一介绍其性能特点。

HashMap：
- 最常用的Map实现类，通过使用Hash表结构，提高查找速度；
- 使用键值对作为存储节点，只允许一个key值为null，允许多个value值为null；
- 线程不安全，对于线程安全有要求的程序，可以考虑使用：sychronizedMap或者ConcurrentHashMap；
HashTable
- 同样使用Hash表结构，提高查找效率；
- 线程安全，但是安全层级低于ConcurrentHashMap，不常用。
LinkedHashMap
- 继承自HashMap，使用Hash表结构，提高查找效率；
- 链表插入维持插入顺序。
TreeMap
- sortedMap接口的实现类，可使用特定的排序规则对键值对进行排序；

对四种常见的实现类的性能比较如下图所示：
在这里插入图片描述

2. HashMap的数据结构

2.1 Hash表的基本概念

Hash表是数据结构和算法课程中学习到的一种重要的数据结构。主要设计思想是：

使用一个长度为n的数组存储相关数据。
使用hash函数实现内容和数组下标的对应，也就是hash函数的函数值为0~n之间。
- hash函数相同的输入参数一定会产生相同函数值，不同内容尽量做到函数值分散。
在hash函数值对应的下标写入该内容。
下次查找某元素的时候，先根据hash函数生成下标，然后再随机访问数组，这样查找效率大大提高了。

类似于一个叫贾斯汀·费尔兰德·亨利皮特潘（复杂内容）的人，在酒店前台（hash函数）入住酒店的房间编号是1004（hash函数值/数组下标）。需要找他的人，只需要去酒店前台查询他住在1004房间，直接去1004房间找人就可以了，不需要一个一个房间去找。

2.2 Hash冲突

在上面的流程说明中，我们可以发现Hash表的实现关键就在于Hash函数，一个好的hash函数应该保证不同的输入内容尽量分散其函数值。
当存入的数据过多，hash函数性能较差的时候，可能会出现hash冲突：

A和B是两个不同的存储内容，但是经过hash函数计算，得到的hash函数值相同，因此两个内容存储在数组的同一位置。
例如：贾斯汀·费尔兰德·亨利皮特潘和特朗普·懂王·建国同志两个人在酒店前台分配到的房间号都是1004，但是房间只有一张床，这时两个人就会发生冲突。

解决冲突主要有两种思路：

开放定址法：发生冲突的时候，后到来的元素放弃已被占用的位置，寻找新的插入位置。（再找）
链地址法：发生冲突的时候，后到来的元素在原有位置的基础上，使用链表的方式存储。（排队）
- HashMap使用的就是链地址法。

2.3 HashMap数据结构

节点Node
Node是HashMap的一个基本存储单元，从源码中可见Node实现了Map.Entry接口，存放的是键值对。在JDK1.8中的源码中，Node的定义如下所示：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;    //用来定位数组索引位置
    final K key;
    V value;
    Node<K,V> next;   //链表的下一个node

    Node(int hash, K key, V value, Node<K,V> next) { ... }
    public final K getKey(){ ... }
    public final V getValue() { ... }
    public final String toString() { ... }
    public final int hashCode() { ... }
    public final V setValue(V newValue) { ... }
    public final boolean equals(Object o) { ... }
}

JDK1.7的HashMap数据结构
数组+链表
- 如图所示
- 使用链地址方式解决hash冲突。
JDK1.8的HashMap数据结构
数组+链表+红黑树
- 如图所示
```
![在这里插入图片描述](https://img-blog.csdnimg.cn/e80970c484d9427c8c47885eabbe0229.png#pic_center)
```
- 对红黑树的学习可参考此博客。
- 链表和红黑树的转换根据链表长度阈值判断，阈值为8，即链表长度大于8时，由链表转换为红黑树，小于6时，由红黑树转换为链表。
- 红黑树的引入目的：在链表长度较长的情况下，优化查找效率。

3. HashMap的重要变量

3.1 常量

DEFAULT_INITIAL_CAPACITY
- 默认的数组初始容量，值为2^4=16。
- 如果没有指定初始数组的容量的话，就会使用这个默认值。
MAXIMUM_CAPACITY
- 最大的数组容量，值为2^30。
- 在扩容的时候，如果扩容后的容量大于这个值，就会使用这个值作为新的容量。
- 之后如果数据再增加，不再进行扩容，而是直接链表存储或者转为红黑树。
DEFAULT_LOAD_FACTOR
- 默认负载因子，值为0.75。
- 在HashMap中，扩容的临界值计算公式为：
  临界值（threshold） = 负载因子（loadFactor） * 容量（capacity）
- 负载因子可以设置为任意值，但是需要注意的是：
  - 负载因子变大，hash冲突的概率就会变大，查找效率就会降低。【牺牲时间】
  - 负载因子过小，会导致数组空间利用率低，浪费内存空间。【牺牲空间】
TREEIFY_THRESHOLD
- 链表转化为红黑树的阈值，值为8。
- 当一个数组节点所带着的链表长度大于8时，链表会转化为红黑树。
UNTREEIFY_THRESHOLD
- 红黑树转化为链表的阈值，值为6。
- 当一个数组节点的红黑树节点小于6时，红黑树会转化为链表。
MIN_TREEIFY_CAPACITY
- 转换为红黑树的最小容量，值为64。
- 这个变量的意思是，在HashMap不断增加新元素的过程中，如果此时数组中的元素个数小于64，那么就选择扩容。当数组元素个数大于64的时候才会考虑树化。
  3.2 变量
size
- HashMap中存储的键值对个数。
modCount
- 对HashMap进行修改的次数记录，每次增删则加一。
threshold
- 扩容的临界值，计算公式为：threshold = loadFactor * capacity。其中capacity为数组总长度，通常为了提高阈值，会使用扩容增加capacity，而对于负载因子loadFactor，一般不会修改。
loadFactor
- 负载因子，用户可自行设置其值，否则等于默认值0.75。

3.3 辨析size、capacity、threshold

在这里插入图片描述

size:实际存储的键值对个数
capacity:数组的总长度
threshold:扩容的临界值
treeify_threshold/untreeify_threahold:链表和红黑树相互转化的阈值

4. HashMap重要方法和源码解析

4.1 构造方法

HashMap()
无参构造，使用默认的初始容量2^4和负载因子0.75，构造一个空的HashMap。

// 构造一个空的 HashMap，初始容量为 16，负载因子为默认值 0.75
public HashMap() {    
 this.loadFactor = DEFAULT_LOAD_FACTOR;  // all other fields defaulted
}

HashMap(int initialCapacity)
指定初始容量，使用默认的负载因子0.75。

public HashMap(int initialCapacity) {    
 this(initialCapacity, DEFAULT_LOAD_FACTOR);//一次性实现容量和负载因子的赋值
}

HashMap(int initialCapacity, float loadFactor)
指定初始容量和负载因子，构造一个空的HashMap。

public HashMap(int initialCapacity, float loadFactor) {
 // 如果初始容量为负数，抛出非负异常
 if (initialCapacity < 0)
     throw new IllegalArgumentException("Illegal initial capacity: " +  initialCapacity);
 // 初始容量大于最大值时1<<30，则取最大值
 if (initialCapacity > MAXIMUM_CAPACITY)
     initialCapacity = MAXIMUM_CAPACITY;
 // 负载因子不能小于 0，并且必须是数字，否则抛异常
 if (loadFactor <= 0 || Float.isNaN(loadFactor))
     throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
 //数值判断合法之后，赋值
 this.loadFactor = loadFactor;
 this.threshold = tableSizeFor(initialCapacity);//tableSizeFor() 方法返回一个值，比initialCapacity大的最小2的幂。
}

HashMap(Map<? extends K, ? extends V> m)
构造一个非空的HashMap，将m中的键值对存入HashMap中，默认的负载因子 0.75，使用默认的初始容量2^4。

public HashMap(Map<? extends K, ? extends V> m) {
 this.loadFactor = DEFAULT_LOAD_FACTOR;
 // 将 Map 中的 key-value 赋值到新的 Map 中去
 putMapEntries(m, false);
}

4.2 resize方法

当HashMap中数组的使用量超过阈值的时候，就需要进行扩容。JDK1.8的源码如下所示：

final Node<K,V>[] resize() {
 Node<K,V>[] oldTab = table;// 当前 table
 int oldCap = (oldTab == null) ? 0 : oldTab.length;// 当前table的大小
 int oldThr = threshold;// 当前 table 的 threshold
 int newCap, newThr = 0;// 新的 table 的大小和阀值暂时初始化为 0

 // 下面就是开始计算新的 table 的大小和阀值
 // 第一种情况：当前 table 的大小大于 0，则意味着当前的 table 肯定是有数据的
 if (oldCap > 0) {//
     if (oldCap >= MAXIMUM_CAPACITY) {//原始容量大于最大容量，不再扩容，直接返回原始table
         threshold = Integer.MAX_VALUE;
         return oldTab;
     }
     else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
              oldCap >= DEFAULT_INITIAL_CAPACITY)//翻倍之后不超过最大容量，原始容量小于最大容量，且大于默认容量，那么容量翻倍，阈值也对应翻倍
         newThr = oldThr << 1;
 }
 // 第二种情况：当前的 table 中无数据，但是阀值不为零，说明初始化的时候指定过容量或者阀值，但是没有被 put 过数据，
 else if (oldThr > 0) 
     newCap = oldThr;//此时的阀值就是数组的大小，所以直接把当前的阀值当做新 table 的数组大小即可。threshold = tableSizeFor(t);
 // 第三种情况，这种情况就代表当前的 table 是调用的空参构造来初始化的，所有的数据都是默认值。
 else {//初始阈值为0，表示使用默认值，新的 table 也只要使用默认值即可
     newCap = DEFAULT_INITIAL_CAPACITY;
     newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
 }
 // 如果新的阀值是 0，那么就简单计算一遍就行了
 if (newThr == 0) {
     float ft = (float)newCap * loadFactor;
     newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
               (int)ft : Integer.MAX_VALUE);
 }
 threshold = newThr;

 // 根据上文中计算的新表容量和阈值，初始化新的 table
 // 这个 newTab 就是新的 table，数组大小就是上面这一堆逻辑所计算出来的
 @SuppressWarnings({"rawtypes","unchecked"})
 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
 table = newTab;
 if (oldTab != null) {
     // 遍历当前 table，处理每个下标处的 bucket，将其处理到新的 table 中去
     for (int j = 0; j < oldCap; ++j) {
         Node<K,V> e;
         if ((e = oldTab[j]) != null) {
             // 释放当前 table 数组的对象引用（for循环后，当前 table 数组不再引用任何对象）
             oldTab[j] = null;
             // a、只有一个 Node，则直接 rehash 赋值即可
             if (e.next == null)
                 newTab[e.hash & (newCap - 1)] = e;
             // b、当前的 bucket 是红黑树，直接进行红黑树的 rehash 即可
             else if (e instanceof TreeNode)
                 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
             // c、当前的 bucket 是链表
             else { // preserve order
                 Node<K,V> loHead = null, loTail = null;
                 Node<K,V> hiHead = null, hiTail = null;
                 Node<K,V> next;
                 // 遍历链表中的每个 Node，分别判断是否需要进行 rehash 操作
                 // (e.hash & oldCap) == 0 算法是精髓，充分运用了上文提到的 table 大小为 2 的幂次方这一优势，下文会细讲
                 do {
                     next = e.next;
                     // 根据 e.hash & oldCap 算法来判断节点位置是否需要变更
                     // 索引不变
                     if ((e.hash & oldCap) == 0) {
                         if (loTail == null)
                             loHead = e;
                         else
                             loTail.next = e;
                         loTail = e;
                     }
                     // 原索引 + oldCap
                     else {
                         if (hiTail == null)
                             hiHead = e;
                         else
                             hiTail.next = e;
                         hiTail = e;
                     }
                 } while ((e = next) != null);
                 // 原 bucket 位置的尾指针不为空(即还有 node )
                 if (loTail != null) {
                     // 链表末尾必须置为 null
                     loTail.next = null;
                     newTab[j] = loHead;
                 }
                 if (hiTail != null) {
                     // 链表末尾必须置为 null
                     hiTail.next = null;
                     newTab[j + oldCap] = hiHead;
                 }
             }
         }
     }
 }
 return newTab;
}

为什么要*2扩容？或者说，为什么HashMap的数组大小为2的幂
在理论学习中，Hash表的大小最好是素数，因为素数能够有效降低hash碰撞。但是HashMap并没有采用这种做法。
在上面的源码中，我们可以看到，HashMap在扩容的时候，数组的大小都是原来的两倍，这是因为在计算索引的时候，我们使用的是size-1的n个全1二进制串和hash值进行与运算，这样可以保证计算出来的索引值一定在0~size-1之间，不会越界。如图所示：

当HashMap值为2的幂的时候，size-1为全1二进制字符串，且扩容之后，原本有冲突的两个元素会找到各自的新索引位置。如图所示：
在这里插入图片描述

在代码中，这个步骤被进一步简化。如代码片段所示：

if ((e.hash & oldCap) == 0) {
  if (loTail == null)
      loHead = e;
  else
      loTail.next = e;
  loTail = e;
}
// 原索引 + oldCap
else {
  if (hiTail == null)
      hiHead = e;
  else
      hiTail.next = e;
  hiTail = e;
}

因为hash值是一个整数，所以hash & oldCap的结果要么是0，要么是oldCap。所以，hashMap的扩容，实际上是将原来的数组分成两部分，一部分的索引不变，一部分的索引变为原索引+oldCap。这样就保证了原来的两个元素，扩容之后，一定不会在同一个索引位置上。具体解释如图所示：
在这里插入图片描述

4.3 hash方法

也就是之前在理论部分所说的hash函数部分，将关键字key的值转换为唯一hash值，JDK1.8源码如下:

static final int hash(Object key) {
    int h;
    // 高 16 位与低 16 位进行异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hashCode()函数通常和equals()函数进行比较，hashCode()函数是根据对象的内存地址生成一个特定的数，因此，hashCode值相同的对象不一定相同，hashCode值不同的对象一定不相同。
一般判断两个对象是否相等，先使用hashCode()函数判断内存地址，如果hashCode()函数值相同，再使用equals()函数判断内存中的内容，如果hashCode()函数值不同，就不需要再使用equals()函数判断了。

这里h先设置成key值的hashCode，然后右移16位，再和原来的h进行异或运算，这样做的目的是为了减少hash碰撞，提高查找效率。

之后如何从hash值映射到数组下标，在JDK1.7的源码如下所示:

static int indexFor(int h, int length) {
    return h & (length-1);
}

这里也解释了为什么HashMap的数组大小为2的幂，因为这样可以保证length-1为全1的二进制串，与操作之后计算出来的索引值一定在0~size-1之间，不会越界，具体操作如图所示：
在这里插入图片描述

4.4 put方法

put方法主要是在HashMap中存储键值对，JDK1.8源码如下所示：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);//重点在于putVal方法
}

// 参数 onlyIfAbsent,针对已经存在的value，值为true表示不修改；否则表示会替换原本的value值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // ① 如果当前 table 为空则进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 计算得到索引 i，算法在上文有提到，然后查看索引处是否有数据
    // ② 如果没有数据，则新建一个新的 Node
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 索引处有数据
    else {
        Node<K,V> e; K k;
        // ③ 索引处的第一个 Node 的  key 和参数 key 是一致的，所以直接修改 value 值即可（修改的动作放在下面）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // ④ 索引处的 bucket 是红黑树，按照红黑树的逻辑进行插入或修改
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // ⑤ 索引处的 bucket 是链表
        else {
            // 遍历链表上面的所有 Node
            for (int binCount = 0; ; ++binCount) {
                // 索引处的 Node 为尾链
                if ((e = p.next) == null) {
                    // 直接新建一个 Node 插在尾链处
                    p.next = newNode(hash, key, value, null);
                    // 判断是否需要转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 链表转换为红黑树，此方法在上文中也有介绍
                        treeifyBin(tab, hash);
                    break;
                }
                // 当前 Node 的 key 值和参数 key 是一致的，即直接修改 value 值即可（修改的动作放在下面）
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 找到了相同 key 的 Node，所以进行修改 vlaue 值即可
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 修改 value 值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            // 修改操作，直接 return 结束掉代码逻辑
            return oldValue;
        }
    }
    // 记录结构发生变化的次数
    ++modCount;
    // ⑥ 判断是否需要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    // 新增的 Node，返回 null
    return null;
}

源代码所抽象出来的具体的put流程可如下图所示：
在这里插入图片描述

在JDK1.7中，链表插入使用头插法，而在JDK1.8中，链表插入使用尾插法，

JDK1.7 使用头插法的原因：考虑到热点数据，后面插入的元素更有可能被最近使用，因此使用头插法。
头插法会使链表上 Node 的顺序调转，而尾插法则不会，另外，头插法也会造成环形链死循环等问题，
参考文献
知乎专栏-HashMap原理详解，看不懂算我输（附面试题）
掘金社区-详解 HashMap 数据结构
美团技术团队-Java 8系列之重新认识HashMap

本文含有隐藏内容，请开通VIP 后查看

【后端面经-Java】HashMap详解

1. HashMap的家族定位

2. HashMap的数据结构

2.1 Hash表的基本概念

2.2 Hash冲突

2.3 HashMap数据结构

3. HashMap的重要变量

3.1 常量

3.2 变量

3.3 辨析size、capacity、threshold

4. HashMap重要方法和源码解析

4.1 构造方法

4.2 resize方法

4.3 hash方法

4.4 put方法

参考文献

网站公告

今日签到

热门文章

最新发布