1. 简介

HashMap 主要用来存放键值对 ，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。

HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于等于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。并且， HashMap 总是使用 2 的幂作为哈希表的大小。

2. 源码分析

2.1 结构

继承关系
属性
内部类
方法
构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 默认初始容量，使用位运算设置为 2 的 4 次方（16）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

// 最大容量，使用位运算设置为 2 的 30 次方
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认加载因子，用于确定何时进行哈希表的扩容操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转化为红黑树的阈值，即链表长度大于等于 8 时，将链表转化为红黑树
static final int TREEIFY_THRESHOLD = 8;

// 红黑树转化为链表的阈值，即红黑树节点数量小于等于 6 时，将红黑树转化为链表
static final int UNTREEIFY_THRESHOLD = 6;

// 最小容量，当哈希表的容量小于此值时，不会进行红黑树的转化操作
static final int MIN_TREEIFY_CAPACITY = 64;
    
/* ---------------- Fields -------------- */

// 哈希表数组，存储键值对的桶
transient Node<K, V>[] table;

// 哈希表中的键值对集合的视图
transient Set<Map.Entry<K, V>> entrySet;

// 哈希表中键值对的数量
transient int size;

// 对哈希表进行结构修改的次数，用于实现迭代器的快速失败机制
transient int modCount;

// 哈希表的阈值，当键值对数量超过阈值时，进行扩容
int threshold;

// 哈希表的加载因子
final float loadFactor;

2.2 巧用运算快速定位下标

小知识
  1. 按位与 (&)：对应位置上的两个二进制位都为1时，结果位为1，否则为0。
    1
    2
    3
    int a = 5;  // 二进制: 0101
    int b = 3;  // 二进制: 0011
    int result = a & b;  // 结果: 0001 (1)
  2. 按位异或 (^)：对应位置上的两个二进制位相异时，结果位为1，相同时为0。
    1
    2
    3
    int a = 5;  // 二进制: 0101
    int b = 3;  // 二进制: 0011
    int result = a ^ b;  // 结果: 0110 (6)
  3. 左移 (<<)：将二进制位向左移动指定的位数，右侧用0填充。 
    1
    2
    int a = 5;  // 二进制: 0101
    int result = a << 2;  // 结果: 10100 (20)
  4. 右移 (>>)：将二进制位向右移动指定的位数，左侧用符号位填充（对于正数，用0填充）。
    1
    2
    int a = 20;  // 二进制: 10100
    int result = a >> 2;  // 结果: 0101 (5)
  5. 无符号右移 (>>>)：将二进制位向右移动指定的位数，左侧用0填充。
    1
    2
    int a = -20;  // 二进制: 11111111111111111111111111101100（负数的补码表示）
    int result = a >>> 2;  // 结果: 00111111111111111111111111111011 (1073741827)
1
2
3
4
static final int hash(Object key) {
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }
1. 计算 hash 值 int hash = key.hashCode()

key的hashCode值

2. 异或上 hash 值无符号右移16 位。 hash = hash ^ (hash >>> 16)

可以省略吗？
就 （n-1）& hash 这个运算来说，实际参与计算的只有低位，高位意义不大。所以对低16位进行扰动能大大降低下标冲突的概率。让 高16位与低16位进行 ^ 运算（高位不变，低位变化），既满足要求又足够简单！

3. 位置计算公式 index = (n - 1) & hash ，其中 n 是容量

为什么要使用 & 运算符？
& ：对应位置上的数都是1时，结果值才是1，&运算符保证了计算出的下标一定小于n-1

2.3 get方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 数组元素相等
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 桶中不止一个节点
        if ((e = first.next) != null) {
            // 在树中get
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 在链表中get
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

2.4 put方法

流程图
代码
流程说明

HashMap put 过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

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未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素（处理hash冲突）
    else {
        Node<K,V> e; K k;
        //快速判断第一个节点table[i]的key是否与插入的key一样，若相同就直接使用插入的值p替换掉旧的值e。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
        // 判断插入的是否是红黑树节点
        else if (p instanceof TreeNode)
            // 放入树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 不是红黑树节点则说明为链表结点
        else {
            // 在链表最末插入结点
            for (int binCount = 0; ; ++binCount) {
                // 到达链表的尾部
                if ((e = p.next) == null) {
                    // 在尾部插入新结点
                    p.next = newNode(hash, key, value, null);
                    // 结点数量达到阈值(默认为 8 )，执行 treeifyBin 方法
                    // 这个方法会根据 HashMap 数组来决定是否转换为红黑树。
                    // 只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是对数组扩容。
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 跳出循环
                    break;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) {
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}
  1. 计算 key 的 hash 值。
    • 计算方式是 (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  2. 检查当前数组是否为空，为空需要进行初始化，初始化容量是 16 ，负载因子默认 0.75。
  3. 计算 key 在数组中的坐标。
    计算方式：(容量 - 1) & hash.
    因为容量总是2的次方，所以-1的值的二进制总是全1。方便与 hash 值进行与运算。
  4. 如果计算出的坐标元素为空，创建节点加入，put 结束。
    如果当前数组容量大于负载因子设置的容量，进行扩容。
  5. 如果计算出的坐标元素有值。
    • 如果坐标上的元素值和要加入的值 key 完全一样，覆盖原有值。
    • 如果坐标上的元素是红黑树，把要加入的值和 key 加入到红黑树。
    • 如果坐标上的元素和要加入的元素不同（尾插法增加）。

      • 如果 next 节点为空，把要加入的值和 key 加入 next 节点。

      • 如果 next 节点不为空，循环查看 next 节点。
        如果发现有 next 节点的 key 和要加入的 key 一样，对应的值替换为新值。

      • 如果循环 next 节点查找超过8层还不为空，把这个位置元素转换为红黑树。

2.5 resize方法

  1. resize流程

    流程说明
    代码
    code-1
    code-2
    code-3

    先计算 新的hash表容量和新的容量阀值，然后初始化一个新的hash表，将旧的键值对重新映射在新的hash表里。如果在旧的hash表里涉及到红黑树，那么在映射到新的hash表中还涉及到红黑树的拆分

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    final Node<K,V>[] resize() {
          Node<K,V>[] oldTab = table;
          int oldCap = (oldTab == null) ? 0 : oldTab.length;
          int oldThr = threshold;
          int newCap, newThr = 0;
          //code-1：扩容
          if (oldCap > 0) {
              if (oldCap >= MAXIMUM_CAPACITY) {
                  threshold = Integer.MAX_VALUE;
                  return oldTab;
              }
              else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                       oldCap >= DEFAULT_INITIAL_CAPACITY)
                  newThr = oldThr << 1; // double threshold
          }
          //code-2：设置阈值
          else if (oldThr > 0) // initial capacity was placed in threshold
              newCap = oldThr;
          else {               // zero initial threshold signifies using defaults
              newCap = DEFAULT_INITIAL_CAPACITY;
              newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
          }
          if (newThr == 0) {
              float ft = (float)newCap * loadFactor;
              newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                        (int)ft : Integer.MAX_VALUE);
          }
          threshold = newThr;
          @SuppressWarnings({"rawtypes","unchecked"})
              Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
          table = newTab;
          //code-3：旧数据保存在新数组里面
          if (oldTab != null) {
              for (int j = 0; j < oldCap; ++j) {
                  Node<K,V> e;
                  if ((e = oldTab[j]) != null) {
                      oldTab[j] = null;
                      //只有一个节点，通过索引位置直接映射
                      if (e.next == null)
                          newTab[e.hash & (newCap - 1)] = e;
                      //如果是红黑树，需要进行树拆分然后映射
                      else if (e instanceof TreeNode)
                          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                      else {
                           //如果是多个节点的链表，将原链表拆分为两个链表
                          Node<K,V> loHead = null, loTail = null;
                          Node<K,V> hiHead = null, hiTail = null;
                          Node<K,V> next;
                          do {
                              next = e.next;
                              if ((e.hash & oldCap) == 0) {
                                  if (loTail == null)
                                      loHead = e;
                                  else
                                      loTail.next = e;
                                  loTail = e;
                              }
                              else {
                                  if (hiTail == null)
                                      hiHead = e;
                                  else
                                      hiTail.next = e;
                                  hiTail = e;
                              }
                          } while ((e = next) != null);
                          //链表1存于原索引
                          if (loTail != null) {
                              loTail.next = null;
                              newTab[j] = loHead;
                          }
                          //链表2存于原索引加上原hash桶长度的偏移量
                          if (hiTail != null) {
                              hiTail.next = null;
                              newTab[j + oldCap] = hiHead;
                          }
                      }
                  }
              }
          }
          return newTab;
      }

    如果超过了数组的最大容量，那么就直接将阈值设置为整数最大值，然后如果没有超过，那就扩容为原来的2倍。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //code-1：扩容
    if (oldCap > 0) {
          if (oldCap >= MAXIMUM_CAPACITY) {
               threshold = Integer.MAX_VALUE;
               return oldTab;
          }
          else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
              oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    //code-2：设置阈值
    else if (oldThr > 0) //阈值已经初始化了，就直接使用
          newCap = oldThr;
    else {    // 没有初始化阈值那就初始化一个默认的容量和阈值
          newCap = DEFAULT_INITIAL_CAPACITY;
          newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
          float ft = (float)newCap * loadFactor;
          newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
    }
    //为当前的容量阈值赋值
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;

    扩容后长度为原hash表的2倍，是把hash表分为两半，分为低位和高位，通过（e.hash & oldCap） == 0 来判断，把原链表的键值对， 一半放在低位，一半放在高位。
    举个例子：容量n = 16，二进制为10000，第5位为1，e.hash & oldCap 是否等于0就取决于e.hash第5 位是0还是1，这就相当于有50%的概率放在新hash表低位（位子不变），50%的概率放在新hash表高位（原始位子+原始容量）。

  2. resize时机

  • 第一次添加元素时，即当HashMap的数组为null或者数组的长度为0时；
  • 链表转红黑树、且数组容量小于64时；
  • 数组容量大于扩容阈值时；

3. 常见问题

3.1 底层数据结构是什么？

数组+链表

3.2 如何扩容？

3.3 如何解决哈希冲突？

拉链法

3.4 HashCode的作用？

总的来说，Java中的集合（Collection）有两类，一类是List，再有一类是Set。前者集合内的元素是有序的，元素可以重复；后者元素无序，但元素不可重复。

要想保证元素不重复，可两个元素是否重复应该依据什么来判断呢？这就是Object.equals方法了。但是，如果每增加一个元素就检查一 次，那么当元素很多时，后添加到集合中的元素比较的次数就非常多了。也就是说，如果集合中现在已经有1000个元素，那么第1001个元素加入集合时，它 就要调用1000次equals方法。这显然会大大降低效率。

于是，Java采用了哈希表的原理。哈希算法也称为散列算法，是将数据依特定算法直接指定到一个地址上。这样一来，当集合要添加新的元素时，先调用这个元素的hashCode方法，就一下子能定位到它应该放置的物理位置上。如果这个位置上没有元素，它就可以 直接存储在这个位置上，不用再进行任何比较了；如果这个位置上已经有元素了，就调用它的equals方法与新元素进行比较，相同的话就不存了；不相同，也就是发生了Hash key相同导致冲突的情况,那么就在这个Hash key的地方产生一个链表,将所有产生相同hashcode的对象放到这个单链表上去,串在一起。所以这里存在一个冲突解决的问题（很少出现）。这样一来实际调用equals方法的次数就大大降低了，几乎只需要一两次。

所以，Java对于eqauls方法和hashCode方法是这样规定的：
1、如果两个对象相等，那么它们的hashCode值一定要相等；
2、如果两个对象的hashCode相等，它们并不一定相等(在同一个链表上)。
简单来讲 hashCode() 是用来查找用的，equals() 是用来判断两个对象是否相等用的。

3.5 HashMap死循环问题

HashMap在多线程环境下，同时进行put操作，并且同时进行扩容时，链表上的元素顺序会反过来，会出现链表环，导致死循环。

注意：jdk8虽然改用了头插法避免了这个问题，但是在jdk8中 当某个桶中的元素数量很多时，HashMap 在将元素转化为红黑树之前，需要将桶中的元素进行扩容和重新散列，以减少冲突。但是，如果在扩容和重新散列期间，另一个线程对 HashMap 进行了修改操作（如插入或删除元素），就可能会导致两个线程之间的竞争，进而导致死循环的问题。

参考资料

快来参与讨论吧~

博客近期分类标签归档
项目软件开发人工智能Staller
社交友链
更多关于本站
本站由 卡卡龙 使用 Stellar 1.29.1主题创建

本站访问量 次. 本文阅读量 次.

Stellar Copyright Licenses Hexo 备案 描述文字 描述文字