HashMap解析

小伙伴们经常用到HashMap，但是你知道HashMap是如何存储数据的吗？HashMap中的扰动函数、拉链寻址是如何使用的？

面试长谈的负载因子、阈值又是什么东东？静下心来，阅读本文章，你将会有大的收获！！！

知识点：
DEFAULT_LOAD_FACTOR：负载因子，默认值0.75，通过大量计算得出的性能最高的常数。
TREEIFY_THRESHOLD：阈值，用于判断链表转红黑树的门槛。
hash ^ (h >>> 16) ：扰动函数，只获取低16位值，让hash值均匀散列。
拉链法：从hash冲突位置起，依次向后遍历，寻找最近的空位置，进行插入。

1、认识HashMap中的构造函数

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
}
// 设置初始容量值
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 设置初始容量值、负载因子
public HashMap(int initialCapacity, float loadFactor) {
    	// 容量<0,抛出初始化容量异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
    	// 最大容量为 1 << 30
        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);
}
// Map入参
public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
}
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

HashMap一共有四个构造函数

• 无参构造会将负载因子设置为默认值

• 入参为initialCapacity的构造方法会设置初始容量值

• 入参为initialCapacity，loadFactor构造会设置初始容量值、负载因子

• 入参为map构造会添加初始Map值

2、创建HashMap对象

我们可以通过new的方式创建HashMap对象，比如这样：

// 通过无参构造创建对象
Map<String, String> map = new HashMap<>();
// 设置初始容量
Map<String, String> initMap = new HashMap<>(32);
// 设置初始容量、负载因子
Map<String, String> loadFactorMap = new HashMap<>(32,0.75f);
// 设置初始Map
Map<String, String> setMap = new HashMap<>(new HashMap<>());
1
2
3
4
5
6
7
8

3、PUT设置Key，Value值

调用put方法，给HashMap设置Key，Value

Map<String, String> map = new HashMap<>();
map.put("法外狂徒","张三");
1
2

源码追踪put流程

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
// hash
static final int hash(Object key) {
        int h;
    	// hash值通过扰动函数均匀散列
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    	// 定义Node[]
        Node<K,V>[] tab; Node<K,V> p; int n, i;
    	// 判断是否是第一次put
        if ((tab = table) == null || (n = tab.length) == 0)
            // 调用resize()进行扩容，默认扩容2倍
            n = (tab = resize()).length;
    	// 判断该位置是否存在值，不存在直接数组插入，存在链表插入
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 判断是否是TreeNode类型，当链表长度>=8，链表转红黑树，<4，红黑树转链表
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 循环
                for (int binCount = 0; ; ++binCount) {
                    // 判断p.next是否为null，如果为null，拉链法插入
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 判断是否需要链表转红黑树，bincount >= 7，bincount为链表长度
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 退出条件，当e.hash为当前插入的hash值，表明这是新增的Node，直接退出
                    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;
                // oldValue = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            // 扩容
            resize();
    	// 调用linkedHashMap移除重复节点
        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

逻辑流程图：

（1）当调用put方法的时候，方法里边会调用putVal方法，需要key做hash操作，hash操作是把高16位hash值与低16位hash值做异或操作。
调用putVal方法时，会判断是否需要扩容，计算bucket中的index，做取模运算，如果该位置为，那么就以Node对象的方式填入其中。
如果该index位置有数据，出现hash碰撞，进行链表操作，若链表的长度大于阈值，链表结构转换为红黑树结构进行存储。
（2）putVal会调用resize方法进行扩容，当数组内容量大于扩容门槛（threshold = (float) newCap * loadFactor ），Node数组进行扩容，左移1位（<<1）默认为2倍。

4、GET获取值

// 
final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 根据Hash获取firstNode
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 判断fistNode Key是否相等，相等返回
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // do-while循环判断key，返回对应节点
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        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

HashMap的get操作，首先根据Hash值获取Node，通过equles方法判断key是否相等，相等返回，不相等通过do-while循环equles判断。

5、总结：

通过以上的put、get方法，我们能清晰知道HashMap是如何操作数据的，当然，上方梳理并非一丝不落，还有很多涉及到tree、linked操作需要小伙伴自己去探索，感兴趣的小伙伴可以通过debug源码，一步一步搞清楚HashMap中的每一个点，了解作者的设计思想。

繁琐的代码千篇一律，有趣的思想万中无一，与君共勉，未来可期！！！