HashMap，Vector，Hashtable，ConcurrentHashMap等并发容器线程安全的进化过程

太过爱你忘了你带给我的痛 2022-12-11 01:28 95阅读 0赞

## 一 概述 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70][]

## 二 Vector ##

Vector线程安全的集合类，同时它是基于动态数组实现的集合类，借助Synchronized修饰的方法来保证多线程安全。在Vector集合类中Synchronized加在方法上，性能会比较差。

## 三 通过Collections中的指定方法保证线程安全 ##

ArrayList和HashMap为线程不安全的集合类，我们可以通过Collections中提供的方法使得其能够在多线程的情况下保持线程安全。

**Collections.synchronizedList(new ArrayLixt<E>)**

//借助同步锁synchronized (mutex)声明同步代码块实现多线程安全
        public static <T> List<T> synchronizedList(List<T> list) {
            return (list instanceof RandomAccess ?
                    new SynchronizedRandomAccessList<>(list) :
                    new SynchronizedList<>(list));
        }
    
        SynchronizedRandomAccessList(List<E> list, Object mutex) {
                super(list, mutex);
            }
    
        SynchronizedList(List<E> list, Object mutex) {
                super(list, mutex);
                this.list = list;
            }

**Collections.synchronizedMap(new HashMap<K，V>)**

//通过同步锁synchronized(mutext)声明同步代码块保证线程安全
        public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
            return new SynchronizedMap<>(m);
        }
    
        private static class SynchronizedMap<K,V>
            implements Map<K,V>, Serializable {
            private static final long serialVersionUID = 1978198479659022715L;
    
            private final Map<K,V> m;     // Backing Map
            final Object      mutex;        // Object on which to synchronize
    
            SynchronizedMap(Map<K,V> m) {
                this.m = Objects.requireNonNull(m);
                mutex = this;
            }
    
            SynchronizedMap(Map<K,V> m, Object mutex) {
                this.m = m;
                this.mutex = mutex;
            }
         }

由源码可知，SynchronizedList和SynchronizedMap都是借助同步代码块实现使之变得线程安全，所以这种方式性能问题并未得到很好的解决。

## 四 Map接口 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 1][]

**HashMap**

根据key的hashCode进行存储，由于可以直接计算出hashCode值，所以可以直接定位对应值的位置，所以反问速度是很快的，它允许一个key为null，当key为对象的时候，该对象需要重写hashCode()方法和equals()方法保证对象的唯一性，从而满足HashMap中key的唯一性，而HashMap的value是没有任何限制。

在JDK1.7和JDK1.8中的HashMap的默认初始容量为16，loadFactor均为0.75。

**JDK1.7中HashMap扩容的源码**

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        //扩容
        void resize(int newCapacity) {//传入新的容量  
            Entry[] oldTable = table;//引用扩容前的Entry数组  
            int oldCapacity = oldTable.length;  
            if (oldCapacity == MAXIMUM_CAPACITY) {//扩容前的数组大小如果已经达到最大(2^30)了  
                threshold = Integer.MAX_VALUE;//修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了  
                return;  
            }  
      
            Entry[] newTable = new Entry[newCapacity];//初始化一个新的Entry数组  
            //table重新hash到新table上
            transfer(newTable, initHashSeedAsNeeded(newCapacity));//将数据转移到新的Entry数组中  
            table = newTable;//HashMap的table属性引用新的Entry数组  
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改阈值  
        }  
    
        static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            Entry<K,V> next;
            int hash;
    
            /**
             * Creates new entry.
             */
            //h=hash值，k=新元素key,v=新元素的value,n=原链表
            Entry(int h, K k, V v, Entry<K,V> n) {
                value = v;
                next = n;//next指向了原链表，新元素插入到了原链表头部
                key = k;
                hash = h;
            }
    
        //扩容后转移数据
        void transfer(Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
            for (Entry<K,V> e : table) { //遍历旧的Entry数组
                while(null != e) {
                    //造成死循环的关键代码（截图中的步骤一）
                    Entry<K,V> next = e.next;
                    if (rehash) {
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    int i = indexFor(e.hash, newCapacity); //重新计算每个元素在数组中的下标位置  
                    e.next = newTable[i];  //由于采用头插法，链表顺序颠倒（newTable[i]=next）
                    newTable[i] = e;
                    e = next;
                }
            }
        }

**JDK 1.7 HashMap的数据结构**

在JDK1.7中HashMap的数据结构为**数组 + 链表**。

public V put(K key, V value) {
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            if (key == null)
                return putForNullKey(value);
            //通过key计算hash值
            int hash = hash(key);
            //通过hash值的计算数组下标
            int i = indexFor(hash, table.length);
            //遍历该下标位置的链表，如果有存在相同的key,就会进行替换
            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;
                }
            }
            //没有相同的key,就需要插入元素，修改次数+1
            modCount++;
            //添加元素
            addEntry(hash, key, value, i);
            return null;
        }
    
        void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
                //如果size大于阈值后就会扩容成原来的两倍
                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++;
        }
    
         static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            Entry<K,V> next;
            int hash;
    
            /**
             * Creates new entry.
             */
            Entry(int h, K k, V v, Entry<K,V> n) {
                value = v;
                next = n; //next指向了原链表，新元素插入到原链表头部
                key = k;
                hash = h;
            }

**JDK1.7解决hash碰撞（hash冲突）问题**

向HashMap中插入数据时，先根据key进行Hash运算【int h = hash(key)】获取key的hash值h，然后根据方法indexFor()将hash值h与数组的长度进行逻辑与运算【int i = indexFor(hash, table.length)】从而得到数组下标。

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

在进行hash运算的过程中会存在多个key的hash值h相等，这就是所谓的hash碰撞（hash冲突），JDK1.7中通过将冲突的数据通过拉链法并且使用头插法将数据插入转换成的链表中。

使用头插法的原因是在尾部追加元素，时间复杂度是O(n)，头插法能提升性能。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 2][]

**JDK1.7中HashMap扩容可能造成死循环的问题分析（CPU100%问题）**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 3][]

**JDK1.8中HashMap扩容的源码**

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    static final int TREEIFY_THRESHOLD = 8;
    
    static final int UNTREEIFY_THRESHOLD = 6;
    
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                //当两倍扩容后的容量小于2^30时，则扩容为之前的两倍
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            }
            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);
            }
            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;
            if (oldTab != null) {
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        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;
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
                            do {
                                next = e.next;
                                if ((e.hash & oldCap) == 0) {
                                    if (loTail == null)
                                        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) {
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) {
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }

**JDK 1.8 HashMap数据结构**

在JDK1.8中HashMap的数据结构为**数组 + 链表** **+ 红黑树**。

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;
        }
    
        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();
            else if ((e = tab[index = (n - 1) & hash]) != null) {
                TreeNode<K,V> hd = null, tl = null;
                do {
                    TreeNode<K,V> p = replacementTreeNode(e, null);
                    if (tl == null)
                        hd = p;
                    else {
                        p.prev = tl;
                        tl.next = p;
                    }
                    tl = p;
                } while ((e = e.next) != null);
                if ((tab[index] = hd) != null)
                    hd.treeify(tab);
            }
        }

**JDK1.8解决hash碰撞（hash冲突）问题**

JDK1.8中存在Hash冲突时，HashMap的数据结构由数组转换链表【改为尾插法】，当链表长度大于等于8时链表转化为红黑树，但是在转变成红黑树之前，还会有一次判断，只有HashMap中键值对数量超过64时才会发生转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。

此外当红黑树的结点减少的过程，当结点数变为6后，HashMap的数据结构由红黑树转换成链表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 4][]

由于JDK1.8中的数据结构改为尾插法，所以可以直接避免扩容时产生死循环。

**Hashtable**

很多方法与HashMap一致，但其通过Synchronzied关键字来使得方法变成线程安全，所以同一时间只允许允许一个线程对其进行某种操作，所以并发性比ConcurrnetHashMap差很多，所以现在一般都不使用Hashtable，在无需线程并发访问的场景我们可以直接使用HashMap，而在需要高并发场景的时候我们可以直接使用ConcurrentHashMap.

**LinkedHashMap**

HashMap的一个子类，保存记录的插入顺序，这样使得我们遍历的时候同我们的插入的顺序一致。

**TreeMap(排序)**

TreeMap实现了SortMap接口，所以它可以根据key进行排序，默认是升序，也可以自定义排序的实现规则

上述实现是基于key-value中的key是不可变的，因为是通过key定位元素的位置，如果key发生改变就无法定位元素的位置。

## 五 ConcurrentHashMap ##

**JDK1.7中ConcurrentHashMap的结构**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 5][]

JDK1.7中的ConcurrentHashMap最外层默认为16个Segment，Segment的数量可以在初始化的时候设置为其他值，但是一旦初始化之后就无法对其进行扩容。对于每个segment的底层数据结构与HashMap类似，仍然是数组和链表组成的拉链法，进行hash冲突解决。

JDK1.7中的ConcurrentHashMap通过为每个Segment独立加上ReentrantLock锁(分段锁)使得segment之间互不影响，从而保证并发多线程安全，同时提高了并发效率。由于最为存在16个Segments，所以最多同时支持16个线程并发写，可以同时将操作分布在不同的Segment上。

**JDK1.7中ConcurrentHashMap的源码**

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
            implements ConcurrentMap<K, V>, Serializable {
        private static final long serialVersionUID = 7249069246763182397L;
    
        static final int DEFAULT_INITIAL_CAPACITY = 16;
    
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    
        static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
    
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
    
        //继承ReentrantLock的Segment，则每个Segment就是一个锁
        static final class Segment<K,V> extends ReentrantLock implements Serializable {
            
            transient volatile HashEntry<K,V>[] table;
    
           Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
                this.loadFactor = lf;
                this.threshold = threshold;
                this.table = tab;
            }
        }
    }

**JDK1.8中ConcurrentHashMap的结构**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 6][]

JDK1.8中对ConcurrentHashMap进行了重新写，代码从1000来行直接增加到6000来行，同时不再使用Segment，也就无法像再JDK1.7中那样通过给每个Segment增加ReentrantLock来实现多线程并发安全问题，JKD1.8中的ConcurrentHashMap中的每个结点为一个node，然后通过CAS和Synchronized来保证线程并发安全。

**JDK1.8中ConcurrentHashMap的源码**

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
        implements ConcurrentMap<K,V>, Serializable {
        private static final long serialVersionUID = 7249069246763182397L;
    
        private static final int MAXIMUM_CAPACITY = 1 << 30;
    
        private static final int DEFAULT_CAPACITY = 16;
    
        static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
        private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    
        private static final float LOAD_FACTOR = 0.75f;
    
        static final int TREEIFY_THRESHOLD = 8;
    
        static final int UNTREEIFY_THRESHOLD = 6;
    
        static final int MIN_TREEIFY_CAPACITY = 64;
    }

**JDK1.8中Put方法源码详解**

public V put(K key, V value) {
            return putVal(key, value, false);
        }
    
        /**
         * Implementation for put and putIfAbsent
         */
        //插入新值后，如果存在相同的key时，就将新value替换旧value,并返回旧值oldVal
        final V putVal(K key, V value, boolean onlyIfAbsent) {
    
            //禁止key或value为null，如果存在null直接抛出异常
            if (key == null || value == null) throw new NullPointerException();
    
            //根据key获取对应的Hash值
            int hash = spread(key.hashCode());
            int binCount = 0;
    
            //一个无限循环
            for (Node<K, V>[] tab = table; ; ) {
                Node<K, V> f;
                int n, i, fh;
                
                //判断table是否已经被初始化
                if (tab == null || (n = tab.length) == 0)
    
                    //为空初始化table
                    tab = initTable();
    
                //不为空，table已经被初始化
                else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    
                    //判断当前Hash值运算的为空后直接通过cas操作设置当前下标，并将当前插入的值保存
                    if (casTabAt(tab, i, null, new Node<K, V>(hash, key, value, null)))
    
                        //如果保存工作成功表示插入工作完成就会跳出循环
                        break;                   // no lock when adding to empty bin
                }
    
                //如果未完成插入后，判断结点是否为MOVED结点（转义结点），如果是，表明需要扩容
                else if ((fh = f.hash) == MOVED)
                    
                    //通过helpRransfer完成扩容后的转移值操作
                    tab = helpTransfer(tab, f);
                
                //当判断当前Hash值运算的不为空时，即产生hash冲突时
                else {
                    V oldVal = null;
    
                    //链表操作，通过Hash运算的Hash值找到链表上的地址，通过synchronized保证并发安全
                    synchronized (f) {
                        if (tabAt(tab, i) == f) {
                            if (fh >= 0) {
                                binCount = 1;
    
                                //链表操作
                                for (Node<K, V> e = f; ; ++binCount) {
                                    K ek;
    
                                    //根据hash值找到对应的位置
                                    if (e.hash == hash &&
                                            ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
                                        //将对应位置的原值赋值给oldVal
                                        oldVal = e.val;
                                        if (!onlyIfAbsent)
    
                                            //默认用新value将旧值替换
                                            e.val = value;
    
                                        //完成操作后退出
                                        break;
                                    }
    
                                    //表示名当前结点的Key不存在，是一个新的key,则创建一个新结点
                                    Node<K, V> pred = e;
                                    if ((e = e.next) == null) {
    
                                        //并将新结点放到链表的最后
                                        pred.next = new Node<K, V>(hash, key,value, null);
    
                                        //完成增加结点操作后退出循环
                                        break;
                                    }
                                }
                            }
                            //到此处后表示为红黑树结构
                            else if (f instanceof TreeBin) {
                                Node<K, V> p;
                                binCount = 2;
                                if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key, value)) != null) {
                                    oldVal = p.val;
                                    if (!onlyIfAbsent)
                                        
                                        //默认将用新value将旧的替换
                                        p.val = value;
                                }
                            }
                        }
                    }
    
                    //表明完成添加任务
                    if (binCount != 0) {
    
                        //是否将链表转成红黑树，需要保证链表长度为8，且容量为64
                        if (binCount >= TREEIFY_THRESHOLD)
                            treeifyBin(tab, i);
                        if (oldVal != null)
    
                            //返回oldVal
                            return oldVal;
                        break;
                    }
                }
            }
            addCount(1L, binCount);
            return null;
        }
    
        //帮助扩容后的数据转移
        final Node<K, V>[] helpTransfer(Node<K, V>[] tab, Node<K, V> f) {
            Node<K, V>[] nextTab;
            int sc;
            if (tab != null && (f instanceof ForwardingNode) &&
                    (nextTab = ((ForwardingNode<K, V>) f).nextTable) != null) {
                int rs = resizeStamp(tab.length);
                while (nextTab == nextTable && table == tab &&
                        (sc = sizeCtl) < 0) {
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                            sc == rs + MAX_RESIZERS || transferIndex <= 0)
                        break;
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                        transfer(tab, nextTab);
                        break;
                    }
                }
                return nextTab;
            }
            return table;
        }
    
        //帮助链表转换成红黑树
        private final void treeifyBin(Node<K, V>[] tab, int index) {
            Node<K, V> b;
            int n, sc;
            if (tab != null) {
                //要求满足达到ConcurrentHashMap的容量达到64
                if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                    tryPresize(n << 1);
                else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
                    synchronized (b) {
                        if (tabAt(tab, index) == b) {
                            TreeNode<K, V> hd = null, tl = null;
                            for (Node<K, V> e = b; e != null; e = e.next) {
                                TreeNode<K, V> p =
                                        new TreeNode<K, V>(e.hash, e.key, e.val,
                                                null, null);
                                if ((p.prev = tl) == null)
                                    hd = p;
                                else
                                    tl.next = p;
                                tl = p;
                            }
                            setTabAt(tab, index, new TreeBin<K, V>(hd));
                        }
                    }
                }
            }
        }

**JDK1.8中get方法源码详解**

public V get(Object key) {
            Node<K, V>[] tab;
            Node<K, V> e, p;
            int n, eh;
            K ek;
            int h = spread(key.hashCode());
            //table不为null，长度大于0
            if ((tab = table) != null && (n = tab.length) > 0 &&
                    (e = tabAt(tab, (n - 1) & h)) != null) {
                //当hash值找到符合key的结点
                if ((eh = e.hash) == h) {
                    if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                        return e.val;
                }
                //当hash小于0时，表示结点为红黑树结点或者为转移结点
                else if (eh < 0)
                    //通过find方法找到结点
                    return (p = e.find(h, key)) != null ? p.val : null;
                //遍历链表找到相应值
                while ((e = e.next) != null) {
                    if (e.hash == h &&
                            ((ek = e.key) == key || (ek != null && key.equals(ek))))
                        return e.val;
                }
            }
            return null;
        }

**ConcurrentHashMap线程不安全的情况**

一般来说ConcurrentHashMap是线程安全的HashMap，其实它是通过CAS+synchronized来保证它实现的成员方法是线程安全的，如get和put方法，ConcurrentHashMap能保证多个线程同时进行put操作后数据不会错乱，而HashMap在多个线程同时进行put操作后数据会错乱结果无法预知。但是多线程同时操作get方法和put方式时，就无法保证并发线程安全。

> get
> 
> 进行某些操作
> 
> put

如多线程同时执行上述多个方法操作时，ConcurrentHashMap并无法保并发线程安全。为了解决多步操作的线程不安全，Java也为ConcurrentHashMap提供了一些组合方法，这些组合方法本身为线程安全的。

**replace(需要换值的key，oldVal，newVal)**

public boolean replace(K key, V oldValue, V newValue) {
            if (key == null || oldValue == null || newValue == null)
                throw new NullPointerException();
            return replaceNode(key, newValue, oldValue) != null;
        }
    
     final V replaceNode(Object key, V value, Object cv) {
            int hash = spread(key.hashCode());
            for (Node<K,V>[] tab = table;;) {
                Node<K,V> f; int n, i, fh;
                if (tab == null || (n = tab.length) == 0 ||
                    (f = tabAt(tab, i = (n - 1) & hash)) == null)
                    break;
                else if ((fh = f.hash) == MOVED)
                    tab = helpTransfer(tab, f);
                else {
                    V oldVal = null;
                    boolean validated = false;
                    synchronized (f) {
                        if (tabAt(tab, i) == f) {
                            if (fh >= 0) {
                                validated = true;
                                for (Node<K,V> e = f, pred = null;;) {
                                    K ek;
                                    if (e.hash == hash &&
                                        ((ek = e.key) == key ||
                                         (ek != null && key.equals(ek)))) {
                                        V ev = e.val;
                                        if (cv == null || cv == ev ||
                                            (ev != null && cv.equals(ev))) {
                                            oldVal = ev;
                                            if (value != null)
                                                e.val = value;
                                            else if (pred != null)
                                                pred.next = e.next;
                                            else
                                                setTabAt(tab, i, e.next);
                                        }
                                        break;
                                    }
                                    pred = e;
                                    if ((e = e.next) == null)
                                        break;
                                }
                            }
                            else if (f instanceof TreeBin) {
                                validated = true;
                                TreeBin<K,V> t = (TreeBin<K,V>)f;
                                TreeNode<K,V> r, p;
                                if ((r = t.root) != null &&
                                    (p = r.findTreeNode(hash, key, null)) != null) {
                                    V pv = p.val;
                                    if (cv == null || cv == pv ||
                                        (pv != null && cv.equals(pv))) {
                                        oldVal = pv;
                                        if (value != null)
                                            p.val = value;
                                        else if (t.removeTreeNode(p))
                                            setTabAt(tab, i, untreeify(t.first));
                                    }
                                }
                            }
                        }
                    }
                    if (validated) {
                        if (oldVal != null) {
                            if (value == null)
                                addCount(-1L, -1);
                            return oldVal;
                        }
                        break;
                    }
                }
            }
            return null;
        }

**putIfAbsent()如果前key对应的数据不存在再将其进行插入，如果存在就返回存在key对应的值**

public V putIfAbsent(K key, V value) {
            return putVal(key, value, true);
        }
    
    等效代码
    if(!map.containsKey(key))
        return map.put(key,value);
    else
        return map.get(key);
    }

**HashMap和ConcurrentHashMap为什么在链表长度为8的时候转换成红黑树**

>     * The main disadvantage of per-bin locks is that other update
>     * operations on other nodes in a bin list protected by the same
>     * lock can stall, for example when user equals() or mapping
>     * functions take a long time.  However, statistically, under
>     * random hash codes, this is not a common problem.  Ideally, the
>     * frequency of nodes in bins follows a Poisson distribution
>     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
>     * parameter of about 0.5 on average, given the resizing threshold
>     * of 0.75, although with a large variance because of resizing
>     * granularity. Ignoring variance, the expected occurrences of
>     * list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The
>     * first values are:
>     *
>     * 0:    0.60653066
>     * 1:    0.30326533
>     * 2:    0.07581633
>     * 3:    0.01263606
>     * 4:    0.00157952
>     * 5:    0.00015795
>     * 6:    0.00001316
>     * 7:    0.00000094
>     * 8:    0.00000006
>     * more: less than 1 in ten million
>     *
>     * Lock contention probability for two threads accessing distinct
>     * elements is roughly 1 / (8 * #elements) under random hashes.

根据源码注释的阅读可知，刚开始处理Hash冲突并不是使用红黑树，而是采用空间小于一半的，而根据源码中的泊松分布概率分析可知，Hash冲突产生8次的概率为，千万分之六，超过8的概率小于千万分之一，所以在出现这种极端情况下就将其转换成红黑树结构来提高查询效率。

## 六 CopyOnWriteArrayList ##

**CopyOnWriteArrayLsit的源码**

public class CopyOnWriteArrayList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
        private static final long serialVersionUID = 8673264195747942595L;
    
        final transient ReentrantLock lock = new ReentrantLock();
    
        public boolean add(E e) {
            final ReentrantLock lock = this.lock;
            lock.lock();
            //CopyOnWrite操作
            try {
                //旧数组
                Object[] elements = getArray();
                int len = elements.length;
                //复制后的新数组
                Object[] newElements = Arrays.copyOf(elements, len + 1);
                //将新增加的数据放到当前数组的最后位置
                newElements[len] = e;
                //将数组设置为新数组，旧的数组会被回收
                setArray(newElements);
                return true;
            } finally {
                lock.unlock();
            }
        }
    
        //执行读操作，该操作完全未加锁
       @SuppressWarnings("unchecked")
        private E get(Object[] a, int index) {
            return (E) a[index];
        }
    
        public E get(int index) {
            return get(getArray(), index);
        }
    
        public E remove(int index) {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                Object[] elements = getArray();
                int len = elements.length;
                E oldValue = get(elements, index);
                int numMoved = len - index - 1;
                if (numMoved == 0)
                    setArray(Arrays.copyOf(elements, len - 1));
                else {
                    Object[] newElements = new Object[len - 1];
                    System.arraycopy(elements, 0, newElements, 0, index);
                    System.arraycopy(elements, index + 1, newElements, index,
                                     numMoved);
                    setArray(newElements);
                }
                return oldValue;
            } finally {
                lock.unlock();
            }
        }
    }

由源码可知，CopyOnWriteArrayList的并发安全性是由ReentrantLock来保证的。

**CopyOnWriteArrayList的功能**

CopyOnWriteArrayList是一个并发多线程安全的List，由于Vector和SynchronizedList也可以达到类似的功能，但是由于它们分别使用了同步方法和同步代码块来保证多线程安全，所以并发效率相对较低，并且它再迭代的过程中是无法编辑的。

**CopyOnWriteArrayLsit的适用场景**

CopyOnWriteArrayList通过CopyOnWrite机制对上述线程问题进行优化，CopyOnWriteArrayList适合读多写少的业务场景，绝大多数情况下CopyOnWriteArrayList的性能比较好，但是如果需要对某个List经常进行修改操作是，CopyOnWriteArrayList的性能就不如Collections.synchronizedList(new ArrayLixt<E>)。

**CopyOnWriteArrayList修改数据原理**

CopyOnWriteArrayList在操作任何一部分内存内容的时候会将该内存中内容复制到新的内存地址中，然后对新内存地址中的内容进行修改，修改完成后就将指向就内存的地址指针指向新的内存地址，然后将旧内存空间回收。

**CopyOnWriteArrayList的读写规则**

一般的读写锁的情况为：读读共享，写写互斥，读写互斥，写读互斥。

CopyOnWriteArrayList对读写锁规则进行了升级，升级后为：读取是完全不用加锁的，并且更厉害的是写也不会阻塞读操作，只有写入和写入之间需要进行同步等待。

**CopyOnWriteArrayList的数据过期问题**

CopyOnWriteArrayList实例化的List在迭代过程中，迭代器使用的是旧地址空间中的内容，所以迭代出来的数据为修改前的数据。实际上根据CopyOnWrite的读写机制创建副本实现读写分离，它在每次修改过程中都是对副本进行操作，而旧的内容是不可变的。

ArrayList在遍历的过程中如果出现修改操作的时候会抛出ConcurrentModificationException异常。

final void checkForComodification() {
                //expectedModCount是希望被修改的次数，modCount是修改的实际次数，每修改一次modCount就会加一
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }

**CopyOnWriteArrayList的缺点**

1.  **数据一致性问题：CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果想要写入的数据，能够马上被读到，CopyOnWrite容器就不太适合。**
2.  **内存占用问题：由于CopyOnWrite的写时复制，所以在进行写操作的同时，内存中会同时驻扎两个对象的内存。**

## 七 ConcurrentLickedQueue ##

高效的非阻塞并发队列，使用链表实现，可以看做一个线程安全的LinkedList。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 7][]

LinkedList底层是带有头节点和尾结点的双向链表，linkFirst实现头插，linkLast实现尾插。

**LinkedLsit插入操作的部分源码**

/**
         * Links e as first element.
         */
        //头插
        private void linkFirst(E e) {
            final Node<E> f = first;
            final Node<E> newNode = new Node<>(null, e, f);
            first = newNode;
            if (f == null)
                last = newNode;
            else
                f.prev = newNode;
            size++;
            modCount++;
        }
    
        /**
         * Links e as last element.
         */
        //尾插
        void linkLast(E e) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }

## 八 ConcurrentSkipListMap ##

ConcurrentSkipListMap使用跳表的数据结构进行快速查找。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70]: /images/20221123/4f2e972b2f904c9ab73d31d4c08c7740.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 1]: /images/20221123/cfdf444a55a34f6f9b1ff17b5198b94e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 2]: /images/20221123/bad9c909f27f4abdb788a324d2491e6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 3]: /images/20221123/36f8be4f64024636b7596e9aa8889fe3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 4]: /images/20221123/c9a564bf84c3484aa452e609ae354129.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 5]: /images/20221123/04f38b42df454a4e90bd13dcd1512d74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 6]: /images/20221123/7f087bffec784ba2baf6cc39db548192.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 7]: /images/20221123/329e79c9fd0d4a38b313c586e312cda6.png