一起学习HashMap

| | |

绕树三匝，何枝可依。——曹操《短歌行》

HashMap是什么？

HashMap是基于哈希表实现了Map接口的一个类，它不是线程安全的，即不是同步的。是一种存储键值对的集合，它允许null值和null键，它可以根据给定的key通过哈希函数计算得到存储的位置。

HashMap默认初始容量一般是16，默认负载因子是0.75，当散列表中的数目超过容量的75%时，散列表将会重建为原来的两倍，通过包含两个步骤，即重新开辟空间和重新计算散列。

为什么默认初始容量是16，默认负载因子是0.75？

默认初始容量16更加符合hash算法的均匀分布原则，倘若是其他则会更加容易引起哈希冲突。负载因子是综合考虑了时间与空间成本的良好折中，更高会降低空间成本，但会增加查找开销（包括put和get）。

HashMap的put与get方法

put

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

当我们调用put方法，传入key和value时，该类又调用了putVal方法，并传入相关参数，其中hash(key)方法源码是：

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

可以看到，hash方法是计算我们传入put方法key的哈希码，若key为null则哈希值为0，否则获取key的哈希码并将它与它无符号右移16位后的值做异或运算（无符号右移：高位用0补，右移；异或运算：相异为1，相同为0）。即首先需要计算key的哈希值。

putVal的源码：

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
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 首先判断tab是否初始化，若没有则先调用resize()进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    /*若已经初始化，首先将key的哈希码与(n-1)做与运算，得到i值指向已有散列表中的某个对象，
    判断该指向是否为空，若为空直接将key对应的value存在这里*/
    /*此处i = (n-1) & hash，是基于数据结构之散列函数设计方法除留余数法的改进，
      除留余数法是指关键码key mod p 得到散列地址，p是适当正整数，这里是n-1，即散列表长度减一，
     （为什么要减一后面再聊），通过这样设计散列函数得到的散列地址更加随机，更加不会引起冲突*/
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 判断我要存入的键值对与该散列地址已有的键值对是否相同(先后比较了两个对象key的哈希值和key的地址)，若相同，直接将该键值对赋给我们要插入的键值对
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)  // 判断已存在Hash中p是否为TreeNode类型，若是调用putTreeVal插入数据
            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;
                p = e;// 继续查找空位置
            }
        }
        // 通过以上不断查找后存储，若e != null，说明我们要插入的数据已经存好了，最后更新相应的value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount; // 记录HashMap内部结构修改次数
    // 判断插入后的大小是否超过阈值，若超过需要扩容处理
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

get

get源码：

1
2
3
4
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

可以看到，我们是通过给出key而获取value值，首先也是与put方法一样获取key的哈希码，然后调用getNode方法获取对应的Node对象，判断对象是否为空，若为空则返回空，否则返回我们所需要的value值。接下来看看getNode方法的源码，瞅瞅它是如何通过key获取到与key对应的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
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    /* 首先就是判断node列表是否为空（table是已有的存有node对象的列表），再判断列表长度是否大于0，
    然后通过（(n-1) & hash）（上面有介绍到）获得key对应的散列地址，通过该散列地址得到对应的node，
    判断该node是否为空。 */
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        /* first是指node列表中某个node链表的头节点 */
        /* 首先判断头节点的hash是否是我们要找的hash，然后判断头节点的key是否是我们想要找的key，
        或者另一种情况，key不为空的情况下判断我们给的key和头节点的key内容上是否相等 
        (这里是区别equals和==吗？没有太读懂。。。)*/ 
        // 若满足条件直接返回头节点，即可得到想要的value
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        /* 若是没有在头节点找到想要的，则循着链表依次往下找，首先判断头节点的下一节点是否为空 */
        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;
}

总结与体会

HashMap的key与value是通过“中介”node去存储相应的key和value的，存储方式通过散列函数(n-1) & key，这样得到的地址减少了地址冲突，有益于存储。再有就是对相同额的散列地址是通过链表额的形式存储，通过指针next去加或找相应的node，也存在通过红黑树作为相同散列地址存储方式的（但是我对这个不熟悉，因此没有深入的分析，记住教训，即将学习它）。emmm。。。还有很多。希望自己多多读源码，找到感觉，再接再厉！

第一次读源码，读得很吃力，有很多不足之处，请多多指教！阿里嘎多^_^

HashMap高并发下引起的死锁

前面有聊到HashMap的默认负载因子是0.75，这是因为HashMap的容量达到这个阈值会增加哈希冲突，于是就有了扩容rehash这个动作。扩容是扩充到原来的两倍，扩充动作是两步，首先扩充entry数组到原来的两倍，然后再重新hash原来的map到新的entry，此时需要重新计算散列地址，因为长度变了。由于HashMap并非线程安全的，于是当重新hash时，便可能会引起线程死锁。

具体来说是：

请看大佬^_*^，我的理解是当我们重新计算哈希时，由于相同位置的node链表形成了循环链表，当查找该位置的node值为null时，就会不断查找，于是形成了死锁。

对于该死锁，大佬的解决方案是使用另一个集合类ConcurrentHashMap，该类兼顾了线程安全和性能。通过学习该文章，我的理解是jdk1.7是在插入时通过该类继承ReentranLock类而使用类方法加锁的方式去对插入的node进行同步控制，而jdk1.8是对代码块使用synchronized关键字进行同步控制。

关于ConcurrentHashMap的深入研究被挂起，等到进一步源码学习^%_*^