HashMap源码分析

发表于 更新于 分类于
HashMap源码分析

HashMap存储结构采用数组+链表（java8以后当链表长度超过8后采用红黑树来存储），当存储数据时会先计算key的哈希值，然后使用哈希值计算数组指针，如果数组指针位置已经存在数据，且key不相同，就会采用链表形式存储数据。存储结构如下图：

HashMap存储结构

在jdk1.8中HashMap引入了红黑树，当链表中的元素达到阈值后，并且数组长度大于64，就会将链表转换为红黑树。引入红黑树的主要目的是解决哈希冲突导致的链化严重的问题。

哈希值与数组指针

哈希值计算方法：获取key的hashCode，然后hashCode右移16位，最后将两者进行异或运算。源码如下：

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

为什么没有直接使用key.hashCode()的值呢？这是因为数组长度都是2的幕，比如默认数组长度16=$2^4$，即1<<4，长度掩码就是15=16-1，二进制掩码就是1111。hash与掩码进行按位与运算后得到数组指针，相当于只取了hash的低4位，高位没有用到，增加了指针冲突的概率。因此将hashCode进行右移16位，再进行异或运算，这样做就是在运算中同时使用了高位和低位。

HashMap是通过数组来存储元素。当通过key来后去元素值的时候，首先计算出key的哈希值，然后通过哈希值来计算得到数组坐标，看下put操作中如何计算数组坐标：

1
2
3
4
5
6
7
8
9
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;
    if ((p = tab[i = (n - 1) & hash]) == null)  //从数组中取出node赋值给p
        tab[i] = newNode(hash, key, value, null);
    ......
}

从代码中可以看出，计算数组坐标的算法是：(n - 1) & hash，其中n表示数组长度。所以坐标指针是hash和长度掩码进行与运算。

下图以key="Hello"为例来说明计算过程：

哈希值与数组指针计算

put插入数据

HashMap插入数据

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
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; //初始状态table为空，进行resize扩容
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null); //没有发生hash碰撞，数据存放到数组
    else { //发生了hash碰撞，或者存在相同的key
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; //存在相同的key，覆盖原值
        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);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash); //链表长度大于8尝试转换为红黑树
                    break;
                }
                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;
}

扩容

HashMap采用数组和链表的形式存储数据，即使不扩容理论上可以存储无限多的数据元素。那么为什么要进行扩容呢？HashMap的扩容实际上指得是数组的扩容，默认的数组长度是16，如果不进行扩容，后续数据都依赖链表存储，那么随着数据的增多，查找效率会越来越低，即复杂度是O(n)，而不是O(1)。扩容的依据是总数据量，包括所有数组、链表、红黑树中的元素。

1
2
3
4
5
6
7
8
9
10
11
//默认容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//负载因子，默认0.75，即75%
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//扩容阈值 = 负载因子 * 容量
int threshold;
final float loadFactor;
transient Node<K,V>[] table; //元素存放在数组中，初始值为null
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

HashMap的无参构造函数中将负载因子loadFactor变量设置为0.75。但是并没有设置扩容阈值或者容量，table数组初始值也是null。既然默认都是空的，那么看一下put方法的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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; //因为table初始值是null，所以肯定会走到resize()方法
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        ....
    }
    ......
}

看样子会在resize方法中设置容量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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) { //初始状态，oldCap==0
        ......
    }
    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);  //计算扩容阈值
    }
    ......
    threshold = newThr;  //将计算得到的扩容阈值赋值给threshold成员变量
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //创建元素数组然后赋值给table
    table = newTab;
    if (oldTab != null) {
        ......
    }
    return newTab;
}

自定义初始容量

通过下面的构造函数用户可以自定义初始容量：

1
2
3
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

但是，HashMap不会完全按照用户指定容量来扩容，因为HashMap的容量必须是2的幕。所以，会通过tableSizeFor方法进行换算：

1
2
3
4
5
6
7
8
9
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;
}

比如用户传入的是18，计算过程如下：

运算公式 二进制运算
$n=18-1=17$
$n=17|(17>>>1)=25$ $n=0b10001|0b01000=0b11001$
$n=25|(25>>>2)=31$ $n=0b11001|0b00110=0b11111$
$n=31|(31>>>3)=31$ $n=0b11111|0b00011=0b11111$
$n=31|(31>>>4)=31$ $n=0b11111|0b00001=0b11111$
$n=31|(31>>>5)=31$ $n=0b11111|0b00000=0b11111$
$n=31|(31>>>6)=31$ $n=0b11111|0b00000=0b11111$
return $31+1$; //$32=2^5$

相当于把18二进制的bit位全部赋值位1，然后再加一。$0b10010$ ⇒ $0b11111$ ⇒ $0b100000$。

参考文章

盘点 HashMap 源码中的那些优雅的设计！
HashMap底层实现原理详解