Java HashMap

HashMap 底层

  • 在 JDK 1.7 中 HashMap 是以数组加链表的形式组成的,JDK 1.8 之后新增了红黑树的组成结构,当链表大于 8 时,链表结构会转换成红黑树结构

  • 数组中的元素我们称之为哈希桶,它的定义如下

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
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;

Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}

public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }

public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}

重要属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// HashMap 初始化长度
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// HashMap 最大长度
static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824

// 默认的加载因子 (扩容因子)
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 转换红黑树的临界值,当链表长度大于此值时,会把链表结构转换为红黑树结构
static final int TREEIFY_THRESHOLD = 8;

// 转换链表的临界值,当元素小于此值时,会将红黑树结构转换成链表结构
static final int UNTREEIFY_THRESHOLD = 6;

// 最小树容量
static final int MIN_TREEIFY_CAPACITY = 64;
  • 什么是加载因子?加载因子为什么是 0.75?
    • 加载因子也叫扩容因子或负载因子,用来判断什么时候该进行扩容
    • 假如加载因子是 0.5,HashMap 的初始化容量是 16,那么当 HashMap 中有 16 * 0.5 = 8 个元素时,HashMap 就会进行扩容
    • 0.75 是出于容量性能之间平衡的结果
      • 当加载因子设置比较大的时候,扩容的门槛就被提高了,扩容发生的频率比较低,占用的空间会比较小,但此时发生 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
    public V get(Object key) {
    Node<K,V> e;
    // 对 key 进行哈希操作
    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) {
    // 如果节点是树结构, 则使用 getTreeNode 直接获取相应的数据
    if (first instanceof TreeNode)
    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    do {
    // 非树结构,循环节点判断
            // hash 相等并且 key 相同,则返回此节点
    if (e.hash == hash &&
    ((k = e.key) == key || (key != null && key.equals(k))))
    return e;
    } while ((e = e.next) != null);
    }
    }
    return null;
    }
  • 当哈希冲突时需要通过判断 key 值是否相等来确认此元素是否是要查询的元素

新增

  • 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
    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;
    // 哈希表为空则创建表
    if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
    // 根据 key 的哈希值计算出要插入的数组索引 i
    if ((p = tab[i = (n - 1) & hash]) == null)
    // 如果 table[i] 等于 null, 则直接插入
    tab[i] = newNode(hash, key, value, null);
    else {
    Node<K,V> e; K k;
    // 如果与第一个元素的 key 相等,直接覆盖第一个元素的 value
    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 转换为红黑树进行处理
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);
    break;
    }
    // 如果与下一个元素的 key 相等,直接覆盖下一个元素的 value
    if (e.hash == hash &&
    ((k = e.key) == key || (key != null && key.equals(k))))
    break;
    p = e;
    }
    }
    if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
    e.value = value;
    afterNodeAccess(e);
    return oldValue;
    }
    }
    ++modCount;
    // 超过最大容量,扩容
    if (++size > threshold)
    resize();
    afterNodeInsertion(evict);
    return null;
    }

扩容

  • 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
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    final Node<K,V>[] resize() {
    // 扩容前的数组
    Node<K,V>[] oldTab = table;
    // 扩容前的数组大小
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 扩容前的扩容阈值
    int oldThr = threshold;
    // 预定义新数组的大小和阈值
    int newCap, newThr = 0;
    if (oldCap > 0) {
    // 超过最大值就不再扩容了
    if (oldCap >= MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return oldTab;
    }
    // 扩大容量为当前容量的两倍,但不能超过 MAXIMUM_CAPACITY
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
    oldCap >= DEFAULT_INITIAL_CAPACITY)
    newThr = oldThr << 1; // double threshold
    }
    // 当前数组没有数据,使用初始化的值
    else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
    else { // zero initial threshold signifies using defaults
    // 如果初始化的值为 0,则使用默认的初始化容量
    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;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 开始扩容
    table = newTab;
    // 原数据不为空,将原数据复制到新 table 中
    if (oldTab != null) {
    // 根据容量循环数组,复制非空元素到新 table
    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 { // preserve order
    // 链表复制,JDK 1.8 扩容优化部分

    // 用于连接扩容时位置不变的元素
    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;
    }
    // 原索引 + oldCap
    else {
    if (hiTail == null)
    hiHead = e;
    else
    hiTail.next = e;
    hiTail = e;
    }
    } while ((e = next) != null);
    // 将原索引放到哈希桶中
    if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
    }
    // 将原索引 + oldCap 放到哈希桶中
    if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
    }
    }
    }
    }
    }
    return newTab;
    }
  • JDK 1.8 在扩容时并没有像 JDK 1.7 那样,重新计算每个元素的哈希值,而是通过 e.hash & oldCap 来确定元素是否需要移动

    • 如 key1 的信息如下:

      • key1.hash = 10 -> 0000 1010

      • oldCap = 16 -> 0001 0000

      • 使用 e.hash & oldCap 得到的结果为 0,则在扩容时位置不会发生任何变化

    • 而 key 2 信息如下:

      • key2.hash = 26 -> 0001 1010
      • oldCap = 16 -> 0001 0000
      • 这时候得到的结果不为 0,新的下标位置等于原下标位置 + 原数组长度
    • 为什么要这么做 ?

      • 首先这里的元素扩容前都是在同一个数组下标中的, 也就是 (oldCap - 1) & hash 值相同
      • 扩容的时候新容量是左移了一位的, 如下
        • oldCap = 16 -> 0001 0000
        • newCap = 32 -> 0010 0000
      • 则相应的
        • oldCap -1 = 15 -> 0000 1111
        • newCap - 1 = 31 -> 0001 1111
      • 所以对于 e.hash & oldCap 不为 0 的元素, 需要放置到原索引 + oldCap 的位置, 因为在 newCap 的情况下插入该元素时, (newCap - 1) & hash 值就是原索引 + oldCap

死循环分析

  • 在 JDK 1.7 中, 假设 HashMap 默认大小为 2,原本 HashMap 中有一个元素 key(5)
  • 我们再使用两个线程
    • t1 添加元素 key(3)
    • t2 添加元素 key(7)
  • 当元素 key(3) 和 key(7) 都添加到 HashMap 中之后,开始进行扩容操作
  • 当线程 t1 在执行到 Entry<K,V> next = e.next; 时,交出了 CPU 的使用权,源码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next; // 线程一执行此处
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
       }
int i = indexFor(e.hash, newCapacity);
       e.next = newTable[i];
       newTable[i] = e;
       e = next;
}
}
}
  • 此时线程 t1 中的 e 指向了 key(3),而 next 指向了 key(7)
  • 之后线程 t2 重新 rehash 之后链表的顺序被反转, 链表的位置变成了 key(5) → key(7) → key(3),其中 “→” 用来表示下一个元素
  • 当 t1 重新获得执行权之后,先执行 newTalbe[i] = e; 把 key(3) 的 next 设置为 key(7)
  • 而下次循环时查询到 key(7) 的 next 元素为 key(3),于是就形成了 key(3) 和 key(7) 的循环引用
  • 发生死循环的原因是 JDK 1.7 链表插入方式为首部倒序插入,这个问题在 JDK 1.8 得到了改善,变成了尾部正序插入
  • HashMap 本身就是非线程安全的, 所以不建议在多线程下使用