IOTXING随手记

记录技术学习之路

0%

HashMap源码解读

Posted on Edited on In Changyan:

Hashmap

1.hashmap的家族

1
2
public class HashMap<K, V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

能够看出，hashmap是map的一个实现类

2.基础知识

1
hashmap是有链表加数组或者红黑树构成的，对加入的key计算得到hash值，然后经过计算得到索引，如果原有的索引位置上已经有了元素，那么就会形成一个bucket，然后把新的元素加入到bucket中去，至于bucket是链表还是红黑树，由bucket里面的元素的个数决定。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//默认的初始容量，如果初始化的时候没有设置容量，则使用默认容量，也就是2的四次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;     

//最大容量，默认值为2的30次方，如果用户设置了，则必须为2的n次方
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认的负载因子，负载因子定义了何时去进行扩容
//一般不建议修改，例如cap为100，负载因子为0.75,那么在size>=75的时候，就会调用resize去进行扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/** bucket中的对象由链表转为红黑树的临界值。如果是默认情况，那么当相同hashcode，不同key的对象数量达到8的时候，bucket就会由链表转换为红黑树
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 *由红黑树转换成链表的临界值（只在resize的时候会发生）
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 *只有当表中的键值对超过该数量的时候，才会转换成树，避免在前期表刚建立的时候，大量的元素刚好加入同一个链表导致，这种情况应该扩容，而不是转换成红黑树。为了避免在转换成树和扩容之间冲突，应该至少为TREEIFY_THRESHOLD的四倍
 */
static final int MIN_TREEIFY_CAPACITY = 64;
1
2
3
4
5
6
transient Node<K,V>[] table;      //实际存储的数组
transient Set<Map.Entry<K,V>> entrySet;
transient int size;         			//当前hashmap的键值对数量
transient int modCount;    				//当前hashmap的修改次数
int threshold;          					//扩容的阈值
final float loadFactor; 					//负载因子

每个位置上面存放的都是一个node，也就是所说的bucket，一般情况下node是一个链表。

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
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;
        }
    }

3.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
public HashMap( int initialCapacity, float loadFactor){
       if (initialCapacity < 0)
       {
           throw new IllegalArgumentException("Illegal initial capacity: " +
               initialCapacity);
       }
       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);        //这里用到了tableSizeFor，求最近的一个2的n次方  
   }
       
      
   public HashMap( int initialCapacity){
       this(initialCapacity, DEFAULT_LOAD_FACTOR);
   }
       
      
   public HashMap() {
       this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
   }
       
    
   public HashMap(Map < ? extends K, ? extends V > m){
       this.loadFactor = DEFAULT_LOAD_FACTOR;
       putMapEntries(m, false);           //直接使用一个map来初始化hashmap，会把所有的元素传入到新的hashmap中去
   }

4.put

1
2
3
public V put (K key, V value){
       return putVal(hash(key), key, value, false, true);
   }

在put的时候，会先计算key的hash值

1
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

如果key为null，返回0，(h = key.hashCode()) ^ (h >>> 16)这是一个扰动函数，h右移16位之后，再与原来的进行异或计算，因为已经右移了，所以高16位的异或之后还是原来的高16位。也就是说相当于把原来的h的高16位与h的低16位进行异或计算，进而来降低碰撞的概率。该部分内容较多，建议参考 [hash计算原理][https://www.zhihu.com/question/20733617]

在得到hash值之后，就开始了实际的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
final V putVal ( int hash, K key, V value,boolean onlyIfAbsent,
        boolean evict){
        Node<K,V>[] tab;								//初始化相关变量，一个新的数组tab，一个新的node p
        Node<K,V> p;
        int n, i;   //定义节点数组，新节点p
        if ((tab = table) == null || (n = tab.length) == 0)       //检查当前tab是否为空，如果为空的话，就先进行表的初始化，调用resize函数进行扩容
        {
            n = (tab = resize()).length;                          //扩容后的大小
        }
        if ((p = tab[i = (n - 1) & hash]) == null)          //i = (n-1)&hash，n-1表示的容量，(n-1)&hash计算得出的是应该插入的位置，如果table上该位置还没有元素，则把当前元素插进去
        {
            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))))      //如果经过计算之后，发现key一样，直接修改原先的值
            {
                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);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        {
                            treeifyBin(tab, hash);
                        }
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    {
                        break;      //如果要加入的节点中有个key跟要插入的一样，退出循环
                    }
                    p = e;          //返回插入前的上一个节点值
                }
            }
            if (e != null)
            { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)            //如果设置了onlyIfAbsent，就不会更改原来已经存在的元素
                {
                    e.value = value;
                }
                afterNodeAccess(e);                 //返回添加之前的元素
                return oldValue;
            }
        }
        ++modCount;                                //修改修改次数
        if (++size > threshold)                    //如果添加后的size达到了扩容的阈值，开始扩容
        {
            resize();
        }
        afterNodeInsertion(evict);
        return null;
    }

上面在数组还没有初始化，或者达到了扩容的阈值的时候，会调用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
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
100
final Node<K,V>[] resize () {                       //初始化或者扩容table
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;    //如果是扩容的话，先拿到之前的旧的容量，如果是初始化，设定为0
        int oldThr = threshold;                        //定义旧的阈值
        int newCap, newThr = 0;												 //定义新的容量以及新的阈值
        if (oldCap > 0)																 //oldCap > 0，是扩容的情况
        {                   
            if (oldCap >= MAXIMUM_CAPACITY)				 //如果旧的容量已经超过了最大的容量
            {        
                threshold = Integer.MAX_VALUE;        //修改扩容的阈值为int的最大值
                return oldTab;                        //因为之前容量过大，所以已经无法扩容了，直接返回之前的table
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&     //设定新的容量为旧容量的二倍，并且旧的容量比默认的容量大
                oldCap >= DEFAULT_INITIAL_CAPACITY)
            {
                newThr = oldThr << 1; // double threshold               //将阈值翻倍
            }
        }
        else if (oldThr > 0) // 初始化操作，如果之前设置了初始化的容量，则使用定于的阈值，如果没有则使用默认阈值
        {
            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);             //计算新的阈值，如果大于最大容量，使用int的最大值
        }
        threshold = newThr;                                     //修改对象中的阈值
        @SuppressWarnings({"rawtypes", "unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[]) new Node[newCap];     //初始化节点数组
        table = newTab;                                         //赋值table
        if (oldTab != null)
        {                                   //如果旧的table不是空的，就通过循环，把之前的都一个个加入到新的table中去
            for (int j = 0; j < oldCap; ++j)
            {
                Node<K,V> e;
                if ((e = oldTab[j]) != null)
                {                  //取到数组中的第e个元素
                    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
                        Node<K,V> loHead = null, loTail = null;                 //如果有bucket，则需要重新计算其中元素的新位置，使用两个链表来存储
                        do
                        {
                            next = e.next;                          //在计算索引位置的时候，使用的是(n - 1) & hash，例如n为4，100，n-1为3，也就是011。扩容之后的n为8 1000，n-1为0111。
                            if ((e.hash & oldCap) == 0)
                            {                       //这里我们能够发现，在计算位置的时候，低位都是一样的11,只有高位是不同的，旧的为0，而新的为1，
                                if (loTail == null)     //这里我们只需要计算这个高位就行，因为我们在计算的时候使用的n-1,也就是说我们只要与n进行与计算，如果得到的结果为0，说明不需要移动位置
                                {
                                    loHead = e;
                                }
                                else
                                {
                                    loTail.next = e;
                                }
                                loTail = e;
                            }
                            else
                            {
                                if (hiTail == null)
                                {
                                    hiHead = e;
                                }
                                else
                                {
                                    hiTail.next = e;
                                }
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null)
                        {                                   //如果lo链表不是空的，就把lo链表放在新的table中相同索引的位置
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null)
                        {                                   //通过计算能够发现，新老索引位置的差值一定是为旧容量的大小，因为我们在扩容的时候是按照旧容量的两倍来计算的
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;    //把需要移位的元素放入到新的索引位置上去
                        }
                    }
                }
            }
        }
        return newTab;
    }

这里有个需要注意的地方，因为我们在计算元素的索引时候，使用的是(n - 1) & hash来计算元素应该被存储的位置。因为上面使用了tableSizeFor来计算了n，所以n一定是2的n次方，例如n = 4，那么n的二进制表示就是1000，n-1的二进制表示就是0111。

现在如果开始扩容，那么新的容量一定是n的2倍，也就是8，换成2进制就是10000，n-1就是01111

对于同一个元素而言，新旧的位置区别在于 n-1不同，或者是只是n-1的高位不同

  • 旧容量n-1 00111

  • 新容量n-1 01111

我们把上面两个进行或运算，得到1000，而这正是oldCap的值。因此如果 (e.hash & oldCap) == 0，说明即使扩容，得到的索引还是和之前一样，如果为1，则说明需要进行移位。

现在我们已经接近了跟索引的问题，但是因为hashmap中有bucket，也就是同一个索引上面还有很多元素，而之前的元素因为执行了(n - 1) & hash得到了一样的值，才被存到同一个位置的，现在由于n发生了变化，可能某些元素在重新计算之后，需要移到新的位置去。因此才会有后面的loHead和hiHead。

并且通过上面的计算，我们能够发现，新老位置的索引差值，刚好是旧容量的值，因此新的索引位置就等于就旧的索引位置加上旧的容量