深入理解HashMap、ConcurrentHashMap实现原

2019-07-09  本文已影响0人  文艺小程序员

前言

对于初级和中级程序员来说，Java的Api是必须迈过的一个“坎”，许多程序员在对业务代码麻木后就会对代码的实现原理进行理解，而Java的Api中HashMap、ConcurrentHashMap可能是大家使用最为频繁且面试最容易问到数据结构，本文不会对HashMap、ConcurrentHashMap源码进行逐行的解析，只是会对其中我感觉比较重要的点进行总结（建议对HashMap、ConcurrentHashMap数据结构有基本了解后再读下面章节的内容），通过对比JDK7 、JDK8中的HashMap和ConcurrentHashMap，让大家对其原理有一个深入的理解。

一、JDK7中的HashMap

1.HashMap中槽的默认大小（数组长度）为什么要始终保持2的N次方?

2.为什么计算完hashcode要再进行一次hash计算？

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;
            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

3.什么是HashMap中的Fail-Fast机制？
在HashMap中有一个变量为modCount，它的类型为volatile，每次对HashMap进行修改都要修改该值，我们都知道HashMap线程不安全，该变量的作用就是确定在该线程感知其他线程是否对HashMap进行了修改，如果发现了则抛出异常，这个过程简称Fail-Fast，如我再遍历HashMap所有的key与value，其他线程对HashMap进行了修改，当我判断该值与之前取值不同时，则抛出异常。

4.HashMap在插入和扩容时有什么特点？

5.为什么HashMap线程不安全?

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];                      (1)
        table[bucketIndex] = new Entry<>(hash, key, value, e);  (2)
        size++;
    }

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;                           (1)
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];                               (2)
            newTable[i] = e;                                    (3)
            e = next;                                           (4)
        }
    }
}

二、JDK7中的ConcurrentHashMap

1.ConcurrentHashMap数据结构，为什么他是线程安全的？

2.在ConcurrentHashMap中如何确定段（Segment）数和每段数组的大小等参数？

public ConcurrentHashMap(int initialCapacity,float loadFactor,int concurrencyLevel)

  int j = (hash >>> segmentShift) & segmentMask;
        = (hash >>> (32-sshift))&(ssize-1)

3.ConcurrentHashMap的各种操作在获取锁时有什么优化？

三、JDK8中的HashMap

1.JDK8中的HashMap数据结构有什么优化嘛？
数据结构在用了数组+链表+红黑树的数据结构，主要解决了链表过长查询的效率问题。当冲突少的时候使用的是链表来解决冲突，当冲突结点值大于TREEIFY_THRESHOLD值（默认为8）后，会将链表树化（红黑树），当然这个前前提是HashMap的容量要大于64，如果容量小于64（MIN_TREEIFY_CAPACITY默认值）则会先扩容而不是树化。

2.初始化HashMap容量大小时是否进行了优化？
是的，JDK7中采用的是不断移位-比较的算法，JDK8中采用的是移位-异或算法，不断的将1从高位刷新到低位（指数移位），最终得到最接近2的N次方的数，之所以最开始减1后面加1是为了考虑n本身就为2的N次方的情况，这种情况如果不减1的话，最终的结果为N的二倍，总体来说该算法主要是为了提升计算HashMap容量初始值的效率问题。

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

3.两次Hash算法是否进行了优化？
是的，并没有JDK7那么复杂，简化了流程，高位与地位进行与运算，让高位也参加到运算中，减少发生冲突的概率。

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

4.是否了解在冲突时的树化和链化？

       static int tieBreakOrder(Object a, Object b) {
            int d;
            if (a == null || b == null ||
                (d = a.getClass().getName().
                 compareTo(b.getClass().getName())) == 0)
                d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                     -1 : 1);
            return d;
        }

    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
    }

5.resize()方法是否进行了优化？
在JDK8中的resize()方法根据冲突的数据结构进行扩充，如果当前为链表则采用链表的扩容算法，若当前为红黑树则采用红黑树的扩容方法。扩容还是以二倍的方式进行扩容（一定要注意扩容永远是针对槽位而言，也就是HashMap数据结构中的数组）。

四、JDK8中的ConcurrentHashMap

1.JDK8中的ConcurrentHashMap数据结构是否有改变？
是的，在JDK8中摒弃了原有的Segment的概念，而是直接采用数组+链表+红黑树+锁的数据结构。

2.ConcurrentHashMap如何初始化容量，如何计算hash值？
在之前三章的数据结构中都是根据初始化值找到大于该值，且最接近2的N次方的数组，而在该算法中不再这样，即使initialCapacity为2的N次方，那最后的容量也是initialCapacity的2倍，之所以这么考虑我想应该是尽可能的多申请一些空间，减少扩容和锁带来的性能问题。

  tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));

在计算hash方面，与JDK8的HashMap很相似，但是唯一不同的是多了一步与操作 & HASH_BITS（0x7fffffff），主要的目的是确保最后的值是正数，在插入操作中也是用hash值的正负来判断是链表节点还是树节点。

 static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;
    }

3.ConcurrentHashMap如何初始化容量在扩容时与之前有什么差别？
当槽位的冲突的元素的个数超过8（TREEIFY_THRESHOLD）个时，会将链表转成红黑树，但如果当前的ConcurrentHashMap数组大小小于64（MIN_TREEIFY_CAPACITY）时，则不会转成红黑树，会优先考虑对数组的大小进行扩容（tryPresize方法）。

java.util.concurrent.ConcurrentHashMap#treeifyBin
  if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                tryPresize(n << 1);

ConcurrentHashMap的扩容不是仅仅2倍的扩容，而是2的N次方倍，如当前数组的长度为16，那执行扩容方法tryPresize时参数为32，在方法中会确认最终的扩容大小，根据下方的算法可以确认扩容后的大小为64，tryPresize方法没有加锁，多线程环境下执行，当前线程会帮助去扩容。

java.util.concurrent.ConcurrentHashMap#tryPresize
 int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
            tableSizeFor(size + (size >>> 1) + 1);

4.ConcurrentHashMap如何在多线程下进行扩容并保证线程安全？
在JDK8的ConcurrentHashMap中，有一个ForwardingNode的数据结构，如果该槽位已经完成扩容会将Node节点替换为ForwardingNode节点，其它线程如果发现该槽位没有完成扩容会帮助其进行扩容，若发现已经完成扩容则不会再进行扩容。
扩容的核心方法为transfer，第一个进行扩容的线程会创建2倍的数组容量来进行扩容。扩容的大体的过程是，每个线程在transfer都会领取任务，任务会说说明该线程需要迁移的节点的范围，剩下的就是很多的判断，如是否全部槽位已经完成扩容、一个槽位是否已经完成扩容，在扩容的时候与HashMap类似，对对应的槽位上锁以后，则进行扩容，如果为链表则拆分为两个链表，如果为红黑树则拆分为两个红黑树，若红黑树的节点数小于8则再转化为链表。

上一篇 下一篇

猜你喜欢

热点阅读