HashMap底层分析

HashMap初始化参数

	//初始化容量大小，如果没有指定容量大小，则会在初始化HashMap时使用
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
     //定义了HashMap最大的内存容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
     //默认的负载因子。
    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;
    
    //节点类
    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; }

		//返回节点的hashCode，是通过将键的hashCode和值的hashCode取异或
        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) {
        	// 判断传入的o是否为当前对象的引用
            if (o == this)
                return true;
                // 判断传入的o是否为Map.Entry的实例
            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
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

HashMap静态方法分析

//获取key的hashCode
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
	}
	
//返回大于指定容量的第一个2的整次幂
static final int tableSizeFor(int cap) {
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

1
2
3
4
5
6
7
8
9
10
11
12

HashMap使用变量（动态参数）

	//节点数组，用于存放节点，可以理解为哈希桶
	transient Node<K,V>[] table;
	
	//用于保存缓存中的entrySet<>
    transient Set<Map.Entry<K,V>> entrySet;
    
    //键值对的数量
    transient int size;
    
    //hashmap结构更改次数
    transient int modCount;
    
    //当需要进行结构map结构更改时，进行判断，下一个容量大小值
    int threshold;
    
    //负载因子
    final float loadFactor;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

put方法

当我们在代码中调用到put方法时，默认调用请求的是Map接口中的方法，由于HashMap是实现了Map接口，所以，具体实现还是在HashMap中，下面是其中的源码并加以分析：

    /**
     * 将指定的值放入到指定的键值，构成一一对应的映射关系
     *
     * @param key   传入的键值
     * @param value 键值所对应的值
     * @return 返回与之前key关联的值
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);

    }

    /**
     * Map.put()方法的具体实现
     *
     * @param hash         键对应的hash
     * @param key          键值
     * @param value        要放入的值
     * @param onlyIfAbsent 如果该选项为true，则不能更改之前的值
     * @param evict        如果该选项为false，则该表处于创建模式中
     * @return 前一个值，或者返回为空
     */
     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // 定义一个节点数组
        Node<K, V>[] tab;
        // 定义一个节点，该节点是需要存放的节点
        Node<K, V> p;
        // 实例变量
        int n, i;
        // 该语句判断节点数组是否为null，或者tab的长度是否为0
        if ((tab = table) == null || (n = tab.length) == 0)
            // 若条件成立，则进行tab重新分配大小
            n = (tab = resize()).length;
        // 该语句通过键的hash值和数组长度来来确定元素的存放位置
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 如果当前位置为空，没有其他元素，则新建节点进行存放
            tab[i] = newNode(hash, key, value, null);
        else {
            // 若不为空，则进行插入操作
            Node<K, V> e;
            K k;
            // 此时我们的数组的位置处已经有了节点，
            // p.hash == hash判断插入节点的hash值和对应键值的hash值
            // (k = p.key) == key 拿出当前节点的键值与需要插入的key对应的hash进行比较（==：这里是比较两个对象在堆内存中的首地址是否相等）
            // (key != null && key.equals(k)) 当key不为空，并且二者指向的是否为同一对象
            // 倘若都满足以的条件，把 p 赋值给 e ，用于后面的是否为二叉树时判断
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
                // 如果 p 是一个TreeNode 的实例变量，说明，该 index 下的节点，构成了一颗二叉树
            else if (p instanceof TreeNode)
                // 使用二叉树中的存储值的方法进行put，将该节点添加到树中去
                e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
                // 如果不是 TreeNode 的实例，说明是按照链表的结构存储键值对的
            else {
                // 遍历这个数组 index 下的节点，链表
                for (int binCount = 0; ; ++binCount) {
                    // 找到尾节点，将新的key-value构建成键值对形式的node放到链表的尾部
                    // 尾插法插入
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //进行检查是否需要进行转换位二叉树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 将该tab转换为二叉树
                            treeifyBin(tab, hash);
                        //如果不需要，跳出循环
                        break;
                    }
                    // 倘若都满足以下的条件，直接跳出本次循环
                    // 再次进行判断，这就说明，已经确确实实将键值对加入链表中去了
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //进行不停的递归，直到尾插法之后，满足上面if中的条件，跳出循环
                    p = e;
                }
            }
            //如果上一步把新键值对放入到集合中，则可以得知，该数组 index 处现在是有值的
            // 同时说明该节点已经有值，值需对应更改我们的值，不用找寻新的键的位置
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null) // 跟redis中的setnx类似
                    // 用新值覆盖旧值
                    e.value = value;
                // 调用LinkedHashMap中的方法
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //版本控制
        ++modCount;
        if (++size > threshold)
            //如果插入后，size大于阈值，就进行扩容操作
            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
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
96
97
98
99

从上面的源码中可以分析到：
1、使用的尾插法进行新键值对的插入
2、插入之后再判断是否需要扩容
3、插入非线程安全（哈希碰撞、扩容导致的旧值覆盖问题）

putTreeVal方法

当将元素放到当前位置存在 hash 碰撞时，且元素个数大于 8 个的时候，就会转换为红黑树进行存储

final TreeNode<K, V> putTreeVal(MyHashMap<K, V> map, Node<K, V>[] tab,
                                        int h, K k, V v) {
            // 定义 key 的 Class 对象
            Class<?> kc = null;
            // 标志位，是否已经遍历过一遍红黑树，并非是从头节点开始遍历的，但是遍历路径上已经包含了后续需要对比的节点
            boolean searched = false;
            // 获取红黑树的头节点
            TreeNode<K, V> root = (parent != null) ? root() : this;
            // 从头节点开始遍历整个红黑树节点
            for (TreeNode<K, V> p = root; ; ) {
                // 定义方向和目前节点的hash值
                int dir = 0, ph;
                // 定义键对象
                K pk;
                // 如果当前节点的hash值大于待插入节点的hash值，则向左进行遍历树
                if ((ph = p.hash) > h)
                    dir = -1;
                // 如果当前节点的hash值小于待插入节点的hash值，则向右进行遍历树
                else if (ph < h)
                    dir = 1;
                // 若相等，则当前节点的键对象和待插入的键对象相等，返回当前节点，外层 put 方法进行值的更新
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;

                else if ((kc == null &&
                        (kc = comparableClassFor(k)) == null) ||
                        (dir = compareComparables(kc, k, pk)) == 0) {
                    /*
                     * 走到这一步说明当前 key 没有实现 Comparable 接口，或者实现了 Comparable 接口并且和当前节点的 key 对象相等
                     * @param searched 标识是否已经遍历过一遍树节点了
                     *                  如果没有遍历过，则遍历整个树节点，找到那个与待插入的 key 对象 equals 相等的节点
                     */
                    if (!searched) {
                        TreeNode<K, V> q, ch;
                        // 标识已经遍历过一遍
                        searched = true;
                        if (((ch = p.left) != null &&
                                (q = ch.find(h, k, kc)) != null) ||
                                ((ch = p.right) != null &&
                                        (q = ch.find(h, k, kc)) != null))
                            // 找到了对应的值
                            return q;
                    }
                    // 到这一步说明遍历了所有节点都没有找到与我们待插入节点 equals 相等的节点 该方法一定能比个高低
                   dir = tieBreakOrder(k, pk);  // 再比较一下但当前节点键和我们指定 key 键的大小
                }

                // 定义一个指向当前节点的节点 xp
                TreeNode<K, V> xp = p;
                // 根据 dir 来判断是走左边还是右边，并判断是否为空，若为空则进行插入值
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    // 获取当前节点的 next 节点
                    Node<K, V> xpn = xp.next;
                    // 创建一个节点，同时使得 x.next = xpn
                    TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn);
                    // 根据 dir 的大小来判断左右子树的插入
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // 链表中的 next 节点指向这个树的新节点
                    xp.next = x;
                    // 这个新的树节点的父节点和前置接点均设置为当前的树节点，
                    x.parent = x.prev = xp;
                    // 如果原来的 next 节点不为空
                    if (xpn != null)
                        ((TreeNode<K, V>) xpn).prev = x;
                    // 重新平衡并且新节点置顶
                    // moveRootToFront(tab, balanceInsertion(root, x));
                    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

treeify()方法

该方法是当链表满足转换为红黑树的条件之后，将当前节点数组转换为红黑树。

/**
         * 红黑树的构建
         * 双向链表跟红黑树创建，主要步骤分3步。
         *
         * 1、从该双向链表中找第一个节点为 root 节点。
         * 2、每一个双向链表节点都在 root 节点为根的二叉树中找位置然后将该数据插入到红黑树中，同时要注意balance。
         * 3、最终要注意将根节点跟当前table[i]对应好。
         * @param tab 元素数组
         */
        final void treeify(Node<K, V>[] tab) {
            TreeNode<K, V> root = null;
            for (TreeNode<K, V> x = this, next; x != null; x = next) {
                // 找到 root 节点，开始遍历链表
                next = (TreeNode<K, V>) x.next;
                x.left = x.right = null;
                // 如果找不到头节点，为什么要判断根节点是否为空呢
                if (root == null) {
                    // 当前节点的父节点为空
                    x.parent = null;
                    // 当前节点的红色属性设置为空，即当前节点为黑色节点
                    x.red = false;
                    // 令当前节点指向根节点
                    root = x;
                } else {
                    // 如果根节点不为空
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    for (TreeNode<K, V> p = root; ; ) {
                        // 开始从根节点开始遍历整个链表，开始构建二叉树
                        // 用 dir 来标识我们的左子树还是右子树
                        int dir, ph;
                        K pk = p.key;
                        if ((ph = p.hash) > h)
                            dir = -1;
                        else if (ph < h)
                            dir = 1;
                        else if ((kc == null &&
                                (kc = comparableClassFor(k)) == null) ||
                                (dir = compareComparables(kc, k, pk)) == 0)
                            // 走到这一步说明当前 key 没有实现 Comparable 接口，或者实现了 Comparable 接口并且和当前节点的 key 对象相等
                            // 再次通过我们的 tieBreakOrder 进行比较
                            dir = tieBreakOrder(k, pk);

                        // 保存当前节点
                        TreeNode<K, V> xp = p;
                        // 这里进行比较挂载链表节点到树节点，根据 dir 进行判断
                        // 之后重新平衡，进行下一个链表操作
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            // 如果左子树和右子树都为空的话，那么将当前节点的父节点指向根节点
                            x.parent = xp;
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;
                            // root = balanceInsertion(root, x);
                            break;
                        }
                    }
                }
            }
            moveRootToFront(tab, root);
        }
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