Collection

前言

集合是java基础的最要模块之一，本文列举了相应集合的知识点。主要从非发包和并发包进行整理，为了日后自己学习使用。
本地仅自己学习笔记！

一、非并发包

Collection

List
ArrayList
数组，默认容量10，1.5倍扩容 oldCap + oldCap >> 1
LinkedList
双向链表
Node<E> {
E item;
Node<E> next;
Node<E> prev;
}

Vector
数组，默认容量10，2倍扩容 oldsize + oldsize(前提是不传入 capacityIncrement)
操作方法都用synchronized修饰，线程安全
Stack
Vector子类，提供先进后出，push依次存入，pop尾部取出，直接把尾部index对应的元素改成null
Set
HashSet
基于HashMap存储，value为成员变量 private static final Object PRESENT = new Object();
也可以使用 LinkedHashMap
LinkedHashSet
HashSet子类，默认初始容量16，加载因子0.75，基于LinkedHashMap
TreeSet
基于TreeMap，可以自定义Comparator，用于排序
Queue
ArrayDeque
数组，默认容量16，可指定大小，如果小于8就等于8，大于8取向上取最近的2的次方
可以从两端进行插入、删除操作
PriorityQueue
数组，默认容量11，扩容 oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1))，按照比较器排序，如果不显示传入比较器，那么存储的对象需要实现Comparable

Map

HashMap
数组 + 单链表／红黑树 Node[] table
Node<K, V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
默认容量16, put(k,v)时 resize()生成
TreeNode<K, V> {
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
boolean red;
}
如果单链表的大于等于 TREEIFY_THRESHOLD(默认8)开始扩容(oldsize << 1)，重新hash，如果数组长度大于 MIN_TREEIFY_CAPACITY(默认64)转成红黑树
HashTable
数组 + 单链表，默认容量11，操作方法都用synchronized修饰，加入链表的方式是头部放入
LinkedHashMap
继承了HashMap，重写了相关操作Node的方法，实现双向链表逻辑，加入的Entry
Entry<K, V> extends HashMap.Node<K, V> {
Entry<K,V> before, after;
}
接在链表尾部

TreeMap

红黑树

Entry<K, V> {
		K key;
   V value;
   Entry<K,V> left;
   Entry<K,V> right;
   Entry<K,V> parent;
   boolean color = BLACK;
}

二、并发包

List
CopyOnWriteArrayList
数组 + ReentrantLock
add的时候加锁，重新copy一份，size = oldsize + 1，然后新增元素放到最后一位，重新指向到变量array
指定位置add，分成两段复制
BlockingQueue
SynchronousQueue
cas + 线程阻塞每个put 一定要等 take 才完成
两种实现一种是 FIFO TransferQueue 公平；一种是 FILO TransferStack 非公平；
offer poll 可以设置超时时间
TransferQueue
put，加入QNode.tail，自旋 maxTimedSpins/maxTimedSpins*16后，调用LockSupport.park(this) 进入阻塞，等待被唤醒
take 拿到 m = head.next，如果是null，就一直自旋；不是，则通过cas替换headoffset = m，唤醒m，返回m.item
用 isData 判断是put 还是 take
TransferStack
如果head 不存在或者 head的mode跟我当前mode一直直接进栈；反之则进行match，唤起头节点的next，把head = head.next.next
PriorityBlockingQueue
数组 + ReentrantLock + comparator + Condition ，操作时需要lock，默认容量11
int newCap = oldCap + ((oldCap < 64) ?
(oldCap + 2) : // grow faster if small
(oldCap >> 1));
offer时要lock，添加完，要唤醒 take阻塞的线程
poll时要lock，从尾部出
LinkedBlockingQeque
单链表 + ReentrantLock + Condition 双锁 , 先进先出
默认容量 Integer.MAX_VALUE
size 用的是原子类 AtomicInteger count
put时加putLock，如果达到最大值，需要阻塞，count.getAndIncrement()，第一次，需要唤醒notEmpty.signal()，锁可以被打断
offer可以传入阻塞时间
插入使用 putLock ，拿出使用 takeLock
操作 remove 、contains、toString、toArray 需要 putLock takeLock 双锁
LinkedBlockingDeque
双向链表 + ReentrantLock + Condition 单锁，双Condition
默认容量 Integer.MAX_VALUE
读写同锁，take阻塞
链表操作都需要用 lock
ArrayBlockingQueue
数组 + 单lock + 双conditon
一定要初始化容量
如果超过容量，就会从0开始覆盖，count仍然累加
顺序读写，维护putIndex takeIndex
DelayQueue
PriorityQueue + ReentrantLock + Condition 存储的对象需要实现 Delayed
poll 没有获取到就返回null，take会阻塞

Map

ConcurrentHashMap v8

Cas + synchronized，cas用来设置值，synchronized锁定对象是当前索引到的Node，锁粒度更小了相对比 v7
元素存储在 Node[] + 单链表／红黑树

transient volatile Node<K,V>[] table;

当单链表长度超过8，且Node数组的长度小于64，这个时候先tryPresize(n << 1)，两倍扩容，如果大于64了，就转成红黑树;

putVal 简述

final V putVal(K key, V value, boolean onlyIfAbsent) {
    // 获取hash值，用来确定Node[]中的位置
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        // 懒加载，没有初始化，就需要init，默认大小16
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 当前索引位置没有，就用cas 设置到当前位置，成功直接break，失败将进入下面流程
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;
        }
        // 用于扩容
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 加入操作加锁，锁对象时当前索引到的node
            synchronized (f) {
                // 再次判断 当前索引位置 有没有变化，如果发生了变化，需要重新来过
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        // 单链表循环 一直到 next = null
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                // 这里是表示 是不是要替换 原来的值
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            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)
                                p.val = value;
                        }
                    }
                }
            }
            // bitcount 不是 0 代表 已经加入了
            if (binCount != 0) {
                // 看是否需要进行转树，转树的时候还会再次校验node[]的容量
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // 增加size baseCount 设置失败 就会利用 CounterCell
    addCount(1L, binCount);
    return null;
}

size()，最大值不超过 Integer.MAX_VALUE；mappingCount()可以获取大真正的大小

final long sumCount() {
	 CounterCell[] as = counterCells; CounterCell a;
     long sum = baseCount;
     if (as != null) {
     	for (int i = 0; i < as.length; ++i) {
             if ((a = as[i]) != null)
                  sum += a.value;
          	}
       	}
      	return sum;
  	}

ConcurrentHashMap v7

实例化时，就新建好了Segment[] ，默认大小16
存储到Segment[] 数组中
分段锁，map中存储的是Segment[]，每个Segment是个重入锁，里面存存储的是HashEntry[]，每个HashEntry是个单链表

static final class Segment<K,V> extends ReentrantLock implements Serializable {
	// 存储元素
    transient volatile HashEntry<K,V>[] table;
    
    transient int count;
    transient int modCount;

}

public V put(K key, V value) {
    // 先将key hash 在 Segment[] 找到 对应的 Segment
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key.hashCode());
    int j = (hash >>> segmentShift) & segmentMask;
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
         (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
        s = ensureSegment(j);
    // 利用 Segment put方法 , 里面put 方法 通过 重入锁 加锁
    // 头部插入
    return s.put(key, hash, value, false);
}

size的获取，通过segment.count 累加，先自旋运行三次，三次以内的值相同，就直接返回；超过的话，就针对每个segment 加锁

public int size() {
    // Try a few times to get accurate count. On failure due to
    // continuous async changes in table, resort to locking.
    final Segment<K,V>[] segments = this.segments;
    int size;
    boolean overflow; // true if size overflows 32 bits
    long sum;         // sum of modCounts
    long last = 0L;   // previous sum
    int retries = -1; // first iteration isn't retry
    try {
        for (;;) {
            if (retries++ == RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j)
                    ensureSegment(j).lock(); // force creation
            }
            sum = 0L;
            size = 0;
            overflow = false;
            for (int j = 0; j < segments.length; ++j) {
                Segment<K,V> seg = segmentAt(segments, j);
                if (seg != null) {
                    sum += seg.modCount;
                    int c = seg.count;
                    if (c < 0 || (size += c) < 0)
                        overflow = true;
                }
            }
            if (sum == last)
                break;
            last = sum;
        }
    } finally {
        if (retries > RETRIES_BEFORE_LOCK) {
            for (int j = 0; j < segments.length; ++j)
                segmentAt(segments, j).unlock();
        }
    }
    return overflow ? Integer.MAX_VALUE : size;
}

前言

一、非并发包

Collection

ArrayList

LinkedList

HashSet

LinkedHashSet

TreeSet

Queue

ArrayDeque

PriorityQueue

Map

二、并发包

CopyOnWriteArrayList

SynchronousQueue

TransferQueue

TransferStack

PriorityBlockingQueue

LinkedBlockingQeque

LinkedBlockingDeque

ArrayBlockingQueue

DelayQueue

ConcurrentHashMap v8

ConcurrentHashMap v7