并发编程篇-java集合框架

本文主要是介绍并发编程篇-java集合框架，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

HashMap

JDK1.7 HashMap

PUT方法详解：

	public V put(K key, V value) {
		//Entry<K,V>[] table，一个Entry数组
        if (table == EMPTY_TABLE) {
        	//初始化数组容量
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        //HashMap自带的hash()方法，让hashcode更加散列，使得元素分布更为均匀
        int hash = hash(key);
        //hash & (length-1) 等价于 hash%length，但实现思路不一样，%运算比较慢
        //由于length一定为2的幂次方数，length-1低位一定全为1，当进行hash & (length-1)运算时，则保证了index实际上取的值就是与length-1同长度的hashcode后面几位。
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

	/**
     * Inflates the table.
     */
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        // 找到一个比toSize大的最小2的幂次方数。假设toSize=15，则capacity的值为16。
        // 如果toSize本身是2的幂次方数，则返回toSize。
        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

	void addEntry(int hash, K key, V value, int bucketIndex) {
		//threshold = table.length * loadFactor，即数组长度乘以加载因子。
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

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

1. 若Entry<K,V>[] table数组为空时，会调用java.util.HashMap#inflateTable方法初始化一个数组。根据HashMap实例化时传入的initialCapacity（不传时默认为16）通过inflateTable方法得出一个数组长度。
2. 如果key为null时，hashcode为0，且会将这个元素放在数组第一个位置。
3. 根据key计算出hashcode。再用hashcode和数组的长度计算出数组存储的下标。
4. 当此数组对应的下标存在元素时，如果key已经存在（hash值和key相等）时，会替换旧值并返回。
5. 计算出的下标不存在元素时，先判断当前HashMap中的元素个数（非数组长度）是否大于阈值并且当前index位置的元素不为空，当结果为true时，会对数组进行扩容（多线程同时进行扩容时，由于引用发生改变出现循环链表，下一次get或put方法时就会造成死锁，原因位于java.util.HashMap#transfer方法中）。
6. 扩容后长度翻倍。然后会遍历所有的key重新计算数组下标（此时数组长度变化，index也会发生改变），并使用头插法赋值到新数组中，然后重新计算阈值。

计算数组下标

	/**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

假设数组长度是16，则进行&运算的实际值就是15，二进制表示 0000 1111，hashcode 是 0101 0010。当进行&运算时，此时不论hashcode高四位如何变化，下标取值都是 0010，所以当key不同时，数组下标是有可能相同的。

HashMap本身有一个hash方法，目的是为了让hashcode更加散列，使得元素分布更为均匀。

HashMap扩容

目的是为了分散元素，使链表中的元素分散到数组中，使得链表变短，提高HashMap的访问速度。因为数组的访问性能由于链表。

remove

HashMap中有个remove方法，如果使用此方法进行移除元素是，有可能会抛出异常。
原因：HashMap维护了一个modCount的属性，每次对HashMap进行修改时，modCount都会自增一次。当使用循环去遍历删除时，编译的本质时一个迭代器，迭代器初始化时会有一个expectedModCount属性，当这两个属性不相等时就会抛出异常。
这是一种fast-failed容错机制。

JDK1.8 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;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            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))))
                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;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

1. 首先判断Node数组是不是为空或者长度为0，如果是则会初始化一个数组。
2. 根据key的hashcode和数组长度-1使用&操作，算出数组下标（假设为i），如果当前下标不存在元素，则创建一个Node对象，将Node对象赋值给第i个元素。
3. 如果第i个元素不为空且key已存在于当前HashMap中，如果onlyIfAbsent参数为True或者旧值为空，则会替换旧值并返回。
4. 如果第i个元素不为空且类型为红黑树，
5. 如果第i个元素不为空且类型为链表（else分支），则会去遍历链表，若当前节点的下一个节点为null时，会创建一个Node对象并赋值给当前节点的下一个节点（尾插法）。然后会判断当前链表的长度，如果链表长度为8（算上新增的节点应为9个节点），则会转换为红黑树。
6. 转红黑树钱会对数组进行一次判断，如果数组为空，或者数组长度小于64，会进行扩容，而不会转红黑树。当上述两个条件都不满足时，才会转红黑树。转红黑树时首先会将链表转换位于一个双向列表（Node->TreeNode），然后再遍历双向链表转为红黑树。然后赋值给第i个元素，并将双向链表中与红黑树root节点对应的元素至于顶部。
7. 元素个数加一，如果大于阈值会进行扩容，modcount++。

HashMap扩容

数组长度翻倍。

• 如果当前数组元素节点（假设数组下标为i）为链表，会新建两个Node对象，一个是低位Node对象，一个是高位Node对象。首先用Node的hash值和新数组长度进行&运算，如果结果是0插入低位Node对象中下一个（e.next），否则插入到高位Node对象中的下一个（e.next）。假设旧数组长度是16，新数组长度是32，则新数组的第i个元素为低位Node，第i+16（16为旧数组长度）个元素为高位Node。
• 如果当前数组元素节点（假设数组下标为i）为红黑树，会遍历红黑树对应的双向链表，与上述类似拆分高低位双向链表，并统计高低位双向链表个数，如果拆分后高低位的链表元素个数小于等于6，会遍历链表将TreeNode转换为Node（双向链表转单向链表），并赋值给第i个元素（高位是i+16）。

ConcurrentHashMap

JDK1.7 ConcurrentHashMap

不同于HashMap使用Entry数组实现，ConcurrentHashMap使用的是Segment数组实现的。Segment是由HashEntry数组实现的。

构造函数：

	public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (concurrencyLevel > MAX_SEGMENTS)
            concurrencyLevel = MAX_SEGMENTS;
        // Find power-of-two sizes best matching arguments
        int sshift = 0;
        int ssize = 1;
        while (ssize < concurrencyLevel) {
            ++sshift;
            //与HashMap类似，ssize是大于concurrencyLevel最小的二的幂次方数
            ssize <<= 1;
        }
        this.segmentShift = 32 - sshift;
        this.segmentMask = ssize - 1;
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        int c = initialCapacity / ssize;
        if (c * ssize < initialCapacity)
        	//每个segment中hashEntry的数量。向上取整，以确保每个元素都能存放，不会丢失
            ++c;
        //MIN_SEGMENT_TABLE_CAPACITY 默认为2
        int cap = MIN_SEGMENT_TABLE_CAPACITY;
        while (cap < c)
            cap <<= 1;
        // create segments and segments[0]
        Segment<K,V> s0 =
            new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                             (HashEntry<K,V>[])new HashEntry[cap]);
        Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
        UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
        this.segments = ss;
    }

• initialCapacity：HashEntry的数量，默认为16。
• loadFactor：加载因子，默认为0.75。
• concurrencyLevel：并发级别，Segment数量，默认为16，最大为2^16。由concurrencyLevel/initialCapacity 算出每个Segment有多少个HashEntry，每个Segment最少有2个HashEntry。

PUT方法详解

1. 使用UNSAFE.getObject获取key所在的Segment对象。
2. 使用java.util.concurrent.locks.ReentrantLock#tryLock()方法尝试获取锁，获取锁的过程中会遍历链表，如果当前的key不存在，会新建一个node插入到头部并返回。
3. 计算得到Segment，然后获取HashEntry，根据HashEntry的长度和key的hash值获取这个key存储在HashEntry数组的下标index。
4. 根据index获取到HashEntry对象，然后去遍历这个HashEntry链表，如果如果对应的key已经在链表中，如果onlyIfAbsent参数为false，则会进行更新。
5. 如果如果对应的key不在链表中，会新建一个HashEntry对象，然后根据阈值判断需不需要扩容，如果不需要再使用头插法放入链表中。
6. 如果需要扩容（使用java.util.concurrent.ConcurrentHashMap.Segment#rehash进行扩容）时，首先获取到当前Segment对象内部的HashEntry数组（变量名为table），然后进行双倍扩容，然后遍历数组及HashEntry链表，根据key的hash值和新数组长度-1进行与计算，得到当前key的新的数组下标，然后将这个key对应的元素使用头插法转移到新数组中计算好的下标数组中。注意：链表中相连的元素，如果计算的index相等只需要转移第一个（对象的引用）即可，后续的链表元素引用不需要改变。

GET方法

使用UNSAFE.getObjectVolatile保证获取的值为内存中最新的值。

JDK1.8 ConcurrentHashMap

List

ArrayList

LinkedList

红黑树

特性：

• 结点是红色或黑色。
• 根结点是黑色。
• 所有叶子都是黑色。（叶子是NIL结点）
• 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
• 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。

当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。为了保持红黑树的性质，通过对树进行旋转（例如左旋和右旋操作），即修改树中某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的性质。

插入

插入过程首先是根据一般二叉查找树的插入步骤， 把新结点插入到某个叶结点的位置上，然后将新结点着为红色。 为了保证红黑树的性质能继续保持，再对有关结点重点着色并旋转。

java8中java.util.HashMap.TreeNode#balanceInsertion方法有对这一操作的实现。

这篇关于并发编程篇-java集合框架的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！