HashMap源码解析和安全性问题

概要

• hashmap的实现
• hashmap为什么是线程不安全的
• JDK8 如何修复多线程扩容Bug

hashmap的实现

1.hashmap的组成

• 数组+链表+红黑树

  HashMap的实现使用了一个数组，每个数组项里面有一个链表的方式来实现，因为HashMap使用key的hashCode来寻找存储位置，不同的key可能具有相同的hashCode，这时候就出现哈希冲突了，也叫做哈希碰撞，为了解决哈希冲突，有开放地址方法，以及链地址方法。HashMap的实现上选取了链地址方法，也就是将哈希值一样的entry保存在同一个数组项里面，可以把一个数组项当做一个桶，桶里面装的entry的key的hashCode是一样的。在Java8中当一个桶entry数量超过8时,就会转化为红黑树

上面的图片展示了我们的描述，其中有一个非常重要的数据结构Node<K,V>，这就是实际保存我们的key-value对的数据结构，下面是这个数据结构的主要内容：

//单链表结构
 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;
        }
  }

2.源码解析

1.HashMap的put方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K, V>[] tab;
    Node<K, V> p;
    int n, i;
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
        // 桶中已经存在元素
    else {
        Node<K, V> e;
        K k;
        // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            // 将第一个元素赋值给e，用e来记录
            e = p;
            // hash值不相等，即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);
                    // 跳出循环
                    break;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) {
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

流程图如下

2.resize机制

HashMap的扩容机制就是重新申请一个容量是当前的2倍的桶数组，然后将原先的记录逐个重新映射到新的桶里面，然后将原先的桶逐个置为null使得引用失效。

final Node<K, V>[] resize() {
    //获得原来的table数组
    Node<K, V>[] oldTab = table;
    //原table数组的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //原扩容阈值
    int oldThr = threshold;
    //定义新容量与阈值
    int newCap, newThr = 0;
    //如果原容量>0
    if (oldCap > 0) {
        //如果原容量已经达到最大了1<<30，则不进行扩容，只调整阈值为最大，随其碰撞了
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //如果没达到最大，则变为原来容量的2倍
        //其实这句可分解
        //newCap = oldCap << 1
        //如果扩容后的容量小于最大容量才会将阈值变为原来的2倍
        //else if (newCap < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
        //         newThr = oldThr << 1; // double threshold
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //如果oldCap = 0，oldThr > 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);
    }
    //如果扩容后的容量大于最大容量了1<<30
    if (newThr == 0) {
        float ft = (float) newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                (int) ft : Integer.MAX_VALUE);
    }
    //设置为新的值
    threshold = newThr;
    @SuppressWarnings({"rawtypes", "unchecked"})
    Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
    table = newTab;
    //完成rehash
    if (oldTab != null) {
        //遍历原数组的每一个位置     所以rehash过程的是很耗费时间的
        for (int j = 0; j < oldCap; ++j) {
            Node<K, V> e;
            //e = oldTab[j])
            if ((e = oldTab[j]) != null) {
                //将原位置设为null
                oldTab[j] = null;
                //如果没有碰撞，也就是只有这一个元素，直接定位设置到新数组的位置
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                    //如果当前节点是TreeNode类型，说明已经树化了，红黑树的rehash过程
                else if (e instanceof TreeNode)
                    ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                    //表明当前节点冲突是链表存储的，完成rehash   
                    //注意：这是1.8的优化点，这也是容量声明为2的次幂的另一个应用
                else { // preserve order
                    //rehash后将桶中的值重新分配
                    Node<K, V> loHead = null, loTail = null;//记录低位链表头尾位置
                    Node<K, V> hiHead = null, hiTail = null;//记录高位链表头尾位置
                    Node<K, V> next;//记录当前链表元素在原来链表中的下一个元素，便于下次循环使用
                    //遍历哈希桶的链表，拆分成高位和低位链表(为了更好的理解扩容,实际上只有一条单向链表)  
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) { //新增的有效哈希位为0，即当前元素扩容后分配到 低位链表 其实位置相比以前没变
                            if (loTail == null) //低位链表尚未初始化
                                loHead = e; //设置低位链表头部
                            else
                                loTail.next = e; //低位链表尾部增加当前元素，以保持原链表顺序
                            loTail = e; //更新低位链表的尾部
                        } else { //新增的有效哈希位为1，即当前元素扩容后分配到 高位链表  扩容后的位置
                            if (hiTail == null) //高低位链表尚未初始化
                                hiHead = e; //设置高位链表头部
                            else
                                hiTail.next = e; //高位链表尾部增加当前元素，以保持原链表顺序
                            hiTail = e; //更新高位链表的尾部
                        }
                    } while ((e = next) != null);
                    //更新两个链表到哈希表中
                    if (loTail != null) { //扩容后低位链表不为空，需要处理
                        loTail.next = null; //低位链表设置尾部结束
                        newTab[j] = loHead; //哈希桶设置链表入口
                    }
                    if (hiTail != null) { //扩容后高位链表不为空，需要处理
                        hiTail.next = null; //高位链表设置尾部结束
                        newTab[j + oldCap] = hiHead; //哈希桶设置链表入口
                    }
                }
            }
        }
    }
    return newTab;
}

3.get方法（返回指定键所映射的值）

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

   final Node<K, V> getNode(int hash, Object key) {
       Node<K, V>[] tab;
       Node<K, V> first, e;
       int n;
       K k;
       // table已经初始化，长度大于0，根据hash寻找table中的项也不为空
       if ((tab = table) != null && (n = tab.length) > 0 &&
               (first = tab[(n - 1) & hash]) != null) {
           // 桶中第一项(数组元素)相等
           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;
   }

   final TreeNode<K, V> getTreeNode(int h, Object k) {
       //找到红黑树的根节点并遍历红黑树
       return ((parent != null) ? root() : this).find(h, k, null);
   }

   //找到从根p开始的节点和给定的散列和键。kc参数在第一次使用比较键时缓存了comparableClassFor。
   final TreeNode<K, V> find(int h, Object k, Class<?> kc) {
       TreeNode<K, V> p = this;
       do {
           int ph, dir;
           K pk;
           TreeNode<K, V> pl = p.left, pr = p.right, q;
           if ((ph = p.hash) > h)
               p = pl;
           else if (ph < h)
               p = pr;
           else if ((pk = p.key) == k || (k != null && k.equals(pk)))
               return p;
           else if (pl == null)
               p = pr;
           else if (pr == null)
               p = pl;
           else if ((kc != null ||
                   (kc = comparableClassFor(k)) != null) &&
                   (dir = compareComparables(kc, k, pk)) != 0)
               p = (dir < 0) ? pl : pr;
           else if ((q = pr.find(h, k, kc)) != null)
               return q;
           else
               p = pl;
       } while (p != null);
       return null;
   }

4.treeifyBin方法（将容器中的node变为treeNode）

final void treeifyBin(Node<K, V>[] tab, int hash) {
    int n, index;
    Node<K, V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
        //Node e=tab[该hash对应的角标]，e就是这个角标下的第一个元素。  
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K, V> hd = null, tl = null;
        do {
            //replacementTreeNode == new TreeNode(),就是包装了一个TreeNode对象  
            TreeNode<K, V> p = replacementTreeNode(e, null);
            if (tl == null)
                //遍历链表上的第一个元素的时候，t1==null，将p赋值给hd  
                //也就是先记录一下，方便后面的元素记录pre，next  
                hd = p;
            else {
                //现在p是个tree了，pre记录上一个元素  
                p.prev = tl;
                //顺便把自己的引用在上一个元素上做记录  
                tl.next = p;
            }
            //将当前操作的元素的引用传递给t1  
            tl = p;
            //遍历整个链表，直到没有元素。  
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            //遍历完了，再执行hd.treeify方法  
            //hd=p是在t1==null时执行，也就是只有在第一个元素的时候执行了一次  
            //所以hd代表的是这个树的根。  
            hd.treeify(tab);
    }
}

5.remove方法（移除指定键的映射关系）

public V remove(Object key) {
    Node<K, V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}

final Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    Node<K, V>[] tab;
    Node<K, V> p;
    int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
        Node<K, V> node = null, e;
        K k;
        V v;
        // 直接命中
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            // 红黑树中查找
            if (p instanceof TreeNode)
                node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
            else {
                // 链表中查找
                do {
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 命中后删除
        if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;  // 链表首元素删除
            else
                p.next = node.next;  //多元素链表节点删除
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

hashmap为什么是线程不安全的

• 多线程环境put的时候导致的数据不一致问题

  这个问题比较好想象，比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。下面是一个简单的例子

public class Test {

    private static final Map<String, String> hashMap = new HashMap<>();

    public static void main(String[] args) {

        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 25; i++) {
                hashMap.put(i + "", i + "");
            }
        });

        Thread t2 = new Thread(() -> {
            for (int i = 25; i < 50; i++) {
                hashMap.put(i + "", i + "");
            }
        });

        t1.start();
        t2.start();
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        for (int i = 0; i < 50; i++) {
            System.out.println(i + "/" + hashMap.get(i + ""));
        }
    }

}

结果如下

0/0
1/1
2/2
3/3
4/4
5/null
6/6
7/7
8/8
9/9
10/10
11/null
12/12
13/13
14/14
15/null
16/16
17/17
18/18
19/19
20/20
21/21
22/22
23/23
24/24
25/25
26/null
27/27
28/28
29/29
30/30
31/31
32/32
33/null
34/34
35/35
36/36
37/37
38/null
39/39
40/40
41/41
42/42
43/43
44/44
45/45
46/46
47/47
48/48
49/49

JDK8 如何修复多线程扩容Bug

源码分析上面有

• JDK8 中Node<K,V>[] resize()每次扩容哈希表大小都增倍特性，每次扩容，一个哈希桶里的元素在扩容后的位置，只会是原位置，或者原位置+原哈希表。
• 扩容后，原来哈希桶的链表被拆分为两个，两个链表中的元素都能继续维持原有的顺序。这样就算在多线程环境下同时扩容，一个线程A读取链表状态后停止工作，另一个线程B对同一链表的前几个元素进行扩容分成两个链表，此时线程A恢复工作，由于线程B对链表元素的顺序没有发生变化，所以线程A恢复工作后只是重复了拆分链表的工作，而不会因为链表已被改变顺序而导致环的生成，因此不会发生死循环的问题。
• 也就是说 JDK8 的HashMap扩容方法不但效率提升了（根据哈希值特点拆分链表，红黑树），而且还维持了扩容前后的链表顺序，从而解决了多线程扩容使链表产生环，导致死循环的问题。