同步容器与并发容器

同步容器

性能差，线程不安全

Vector (线程安全)--> ArrayList（线程不安全）

Vector

    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

直接在方法上加同步，保证线程安全，不适用并发执行，性能损耗大

arrayList

1     public boolean add(E e) {
2         ensureCapacityInternal(size + 1);  // Increments modCount!!
3         elementData[size++] = e;
4         return true;
5     }

ArrayList<String> s = new ArrayList<>();

Collections.synchronizedList(s);

保证线程安全

static class SynchronizedList<E>
    extends SynchronizedCollection<E>
    implements List<E>

add()

1         public void add(int index, E element) {
2             synchronized (mutex) {list.add(index, element);}
3         }

锁的级别由方法级别到代码块级别。保证了线程了安全性，但两者性能较差

HashTable(线程安全) --> HashMap（线程不安全）

HashTable

1     public synchronized V put(K key, V value) {
2         // Make sure the value is not null
3         if (value == null) {
4             throw new NullPointerException();
5         }

put()方法加synchronized()

HashMap

put()

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

HashMap<String,Object> res = new HashMap<>();
Collections.synchronizedMap(res);
 
相当于内部代理

1         public V put(K key, V value) {
2             synchronized (mutex) {return m.put(key, value);}
3         }

并发容器

ArrayList --> CopyOnWriteArrayList

适用于大量读操作

add()

 1     public boolean add(E e) {
 2         final ReentrantLock lock = this.lock;
 3         lock.lock();
 4         try {
 5             Object[] elements = getArray();
 6             int len = elements.length;
 7             Object[] newElements = Arrays.copyOf(elements, len + 1);
 8             newElements[len] = e;
 9             setArray(newElements);
10             return true;
11         } finally {
12             lock.unlock();
13         }
14     }

ReentranLock 获得锁，独占锁其他写线程无法进入。

getArray()获取当前数组

创建新数组，把旧数组长度拷贝，并加一

把添加的元素放到新数组中，setArray(),让a 指向 array

    final void setArray(Object[] a) {
        array = a;
    }

rerutn true ; 释放锁

ConcurentLinkedQueue

public class ConcurrentLinkedQueue<E> extends AbstractQueue<E>
        implements Queue<E>, java.io.Serializable


offer()

 1     public boolean offer(E e) {
 2         checkNotNull(e);
 3         final Node<E> newNode = new Node<E>(e);
 4 
 5         for (Node<E> t = tail, p = t;;) {
 6             Node<E> q = p.next;
 7             if (q == null) {
 8                 // p is last node
 9                 if (p.casNext(null, newNode)) {
10                     // Successful CAS is the linearization point
11                     // for e to become an element of this queue,
12                     // and for newNode to become "live".
13                     if (p != t) // hop two nodes at a time
14                         casTail(t, newNode);  // Failure is OK.
15                     return true;
16                 }
17                 // Lost CAS race to another thread; re-read next
18             }
19             else if (p == q)
20                 // We have fallen off list.  If tail is unchanged, it
21                 // will also be off-list, in which case we need to
22                 // jump to head, from which all live nodes are always
23                 // reachable.  Else the new tail is a better bet.
24                 p = (t != (t = tail)) ? t : head;
25             else
26                 // Check for tail updates after two hops.
27                 p = (p != t && t != (t = tail)) ? t : q;
28         }
29     }

poll()

 1     public E poll() {
 2         restartFromHead:
 3         for (;;) {
 4             for (Node<E> h = head, p = h, q;;) {
 5                 E item = p.item;
 6 
 7                 if (item != null && p.casItem(item, null)) {
 8                     // Successful CAS is the linearization point
 9                     // for item to be removed from this queue.
10                     if (p != h) // hop two nodes at a time
11                         updateHead(h, ((q = p.next) != null) ? q : p);
12                     return item;
13                 }
14                 else if ((q = p.next) == null) {
15                     updateHead(h, p);
16                     return null;
17                 }
18                 else if (p == q)
19                     continue restartFromHead;
20                 else
21                     p = q;
22             }
23         }
24     }

ConcurentHashMap

HashMap本身不是线程安全的，因此不能用于多线程并发，因为多线程环境下，使用HashMap进行put操作会引起死循环，导致CPU利用率接近100%，但是java中提供了一个ConcurrentHashMap，这个map是线程安全的，通过对get操作不加锁，对put操作分块加锁的方式来保证线程安全的同时还能有较高的读写性能

JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树。

1.7

segment(分段锁)

ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表,同时又是一个ReentrantLock（Segment继承了ReentrantLock）。

ConcurrentHashMap使用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。

ConcurrentHashMap当中每个Segment各自持有一把锁。在保证线程安全的同时降低了锁的粒度，让并发操作效率更高

HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构，一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。

static final class HashEntry<K,V> { 
    final K key; 
    final int hash; 
    volatile V value; 
    final HashEntry<K,V> next; 
}

HashEntry的一个特点，除了value以外，其他的几个变量都是final的，这意味着不能从hash链的中间或尾部添加或删除节点，因为这需要修改next 引用值，所有的节点的修改只能从头部开始。对于put操作，可以一律添加到Hash链的头部。但是对于remove操作，可能需要从中间删除一个节点，这就需要将要删除节点的前面所有节点整个复制一遍，最后一个节点指向要删除结点的下一个结点。这在讲解删除操作时还会详述。为了确保读操作能够看到最新的值，将value设置成volatile，这避免了加锁。

1.8

ConcurrentHashMap中包含一个table数组，其类型是一个Node数组；而Node是一个继承自Map.Entry<K, V>的链表，而当这个链表结构中的数据大于8，则将数据结构升级为TreeBin类型的红黑树结构。

table：默认为null，初始化发生在第一次插入操作，默认大小为16的数组，用来存储Node节点数据，扩容时大小总是2的幂次方。
nextTable：默认为null，扩容时新生成的数组，其大小为原数组的两倍。
sizeCtl ：默认为0，用来控制table的初始化和扩容操作，具体应用在后续会体现出来。
- -1 代表table正在初始化
- -N 表示有N-1个线程正在进行扩容操作
- 其余情况：
  - 1、如果table未初始化，表示table需要初始化的大小。
  - 2、如果table初始化完成，表示table的容量，默认是table大小的0.75倍，居然用这个公式算0.75（n - (n >>> 2)）。
Node：保存key，value及key的hash值的数据结构。
ForwardingNode：一个特殊的Node节点，hash值为-1，其中存储nextTable的引用。只有table发生扩容的时候，ForwardingNode才会发挥作用，作为一个占位符放在table中表示当前节点为null或则已经被移动。

table 扩容

当table容量不足的时候，即table的元素数量达到容量阈值sizeCtl，需要对table进行扩容。

整个扩容分为两部分：

构建一个nextTable，大小为table的两倍。
把table的数据复制到nextTable中。

完