简介
Java集合类存放于 java.util 包中，是一个用来存放对象的容器。主要是由两大接口派生而来：
Collection接口，主要用于存放单一元素；Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。
List，存放的元素有序的，可重复
Set，存放的元素有序，不可重复
Queue，存放的元素有序，可重复 ；按特定的排队规则来确定先后顺序；出队列有：先进先出，先进后出
Map 接口，主要用于存放键值对。键值不可重复
Java集合体系图
Collection
Collections接口 中提供了大量对集合元素进行添加、删除、查询和修改等操作的方法。
常用的方法
List
有序集合（也称为序列）。用户可精确控制每个元素在列表中的插入位置。用户可以通过索引（在列表中的位置）访问元素，并在列表中搜索元素。元素可重复，可为空
ArrayList
底层维护Object[] elementData ；
线程不安全；
构造函数；
ArrayList(int initialCapacity)，初始化给定容量大小
ArrayList()，默认容量=0
ArrayList(Collection<? extends E> c)
每次扩容是原来的1.5倍
优点
查找高效（每个元素占用空间大小相同，内存地址是连续的，知道首元素的内存地址， 然后知道下标，通过数学表达式计算出元素的的内存地址，所以检索效率最高。）
缺点
增删效率低；(1.增加某个位置，需要移动元素的开销；2.增加时需扩容，也需要copy元素到新数组 ；3.删除，也需要移动元素位置)
外数组无法存储大数据量。（很难找到一块巨大的连续的内存空间）
建议
初始化时给定合理的
initialCapacity，不需要频繁扩容；这样末端添加元素，就很高效
LinkedList
内部是Node节点连接的链表；每个Node，记录前个Node，后一个Node，当前内容；双链表；
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}线程不安全
构造函数
public LinkedList()
public LinkedList(Collection<? extends E> list)
成员变量
transient int size = 0;
transient Node<E> first; //首节点
transient Node<E> last; //尾节点插入操作图
优点：添加、删除高效，无需移动元素，内存地址不连续；
缺点：查询元素慢，每次要从头开始查
建议：
增删多的用LinkedList ; 查询多的用ArraylI
Vector
基本和ArrayList相似，内部是个Object[] elementData；区别，每个方法增加了synchronized
扩容是原来的2倍
线程安全的，但是效率比ArrayList低
Stack
继承Vector , 增加以下函数（且是
synchronized函数）
pop() , peek() , push(E) ，empty() , search(Object)
LIFO ,后进先出
SparseArray
android.util.SparseArray ,安卓独有
成员变量，2个数组：int[] mKeys ， Object[] mValues ；当某个值被删除，被设置为DELETE ，mGarbage 设置为true ;
private static final Object DELETED = new Object();
private boolean mGarbage = false;
private int[] mKeys;//存储key ,根据key 二分查找，找到的index == 实际Value的位置
private Object[] mValues;
private int mSize;构造函数，可以设置容量，默认为0
内部操作，添加，查找，删除
添加过程
通过二分查找，找到对应的位置，并赋值mValues[index]的值
public void put(int key, E value) {
//通过二分查找找到对应的位置
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {//找到了
mValues[i] = value; //直接赋值
} else {
i = ~i;//没有找到，对i取反，就是该元素应该放的位置
if (i < mSize && mValues[i] == DELETED) {//该位置为空，直接复制
mKeys[i] = key;
mValues[i] = value;
return;
}
//数组中可能存在延迟删除元素且当前数组长度满，无法添加
if (mGarbage && mSize >= mKeys.length) {
gc();
//清除后重新确定当前key在数组中的目标位置
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); //赋值 key
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);//赋值 value
mSize++;
}
}//若数组有10个元素，按从小到大排放；比第5个元素小，说明在0~5序号中继续查找；否则在6-10个元素中查找
static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // value found
}
}
//没找到，取反 比如lo = 6 ,~lo = -7
return ~lo; // value not present
}删除过程
通过二分查找index ,找到后没有真正删除，并将mGarbage = true; 等到设置
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {//还没删除，就赋值DELETED
mValues[i] = DELETED;
mGarbage = true;
}
}
}查找过程
通过二分查找，找到就返回
public E get(int key, E valueIfKeyNotFound) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
return (E) mValues[i];
}
}gc过程
整理数组，有效元素往前移动，将无效数据覆盖，mSize 重新赋值；mSize范围外的不会作为 被gc删除，只会被之后的put数组后移覆盖；
private void gc() {
int n = mSize;
int o = 0; //从新开始计数 size
int[] keys = mKeys;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
Object val = values[i];
if (val != DELETED) {//没被删除，有效元素
if (i != o) {//当前i != o ,往前移动
keys[o] = keys[i];
values[o] = val;
values[i] = null;
}
o++;
}//else ，被删除的，o不自增
}
mGarbage = false; //此时无垃圾
mSize = o;
}CopyOnWriteArrayList
1.内部维护 volatile Object[] array ，并且修改时用 ReentrantLock lock（写锁） ；
/** 所有的写入操作 都会加锁 */
final transient ReentrantLock lock = new ReentrantLock();
/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;2.添加，删除，修改某个位置的值。均是将原数组复制一份到新数组，并在新数组中设值，成功后将新数组设置到成员变量Object[] array
//添加元素
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();//原数组
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1); //从原数组复制元素 给 新数组
newElements[len] = e; //并在新元素队尾 赋值
setArray(newElements); //设置到类成员变量 Object[] array
return true;
} finally {
lock.unlock();
}
}
//删除某个位置的元素
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) //不需要移动，直接复制[0 ,len-1]位置的元素
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();
}
}线程安全。setArray() 均用到锁
优点：读操作性能高，无需同步，适合读多写少的场景；在遍历时操作数组，不会抛ConcurrentModificationException
缺点：
1.内存占用，每次写操作都要拷贝，若数据量大，内存压力大
2.无法保证实时一致。遍历的时候，可能是旧的数据
Queue
继承Collection，增加了peek() ,poll() , offer(E) ,element()
public interface Queue<E> extends Collection<E> {
/**
* 添加元素到队列
*/
boolean add(E e);
/**
* 插入元素
*/
boolean offer(E e);
/**
* 移除和返回头元素，若没有就抛异常
*/
E remove();
/**
*返回并移除头元素，若无返回null
*/
E poll();
/**
* 返回头元素，不删除，若没有，就抛异常
*
*/
E element();
/**
* 返回头元素，不删除
*/
E peek();ConcurrentLinkedQueue
内部维护 head 和 tail 节点；初始节点，头尾指向同一个元素
private transient volatile Node<E> head;
private transient volatile Node<E> tail;
//以下是cas
private static final sun.misc.Unsafe UNSAFE;
private static final long headOffset;
private static final long tailOffset;
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class<?> k = ConcurrentLinkedQueue.class;
headOffset = UNSAFE.objectFieldOffset
(k.getDeclaredField("head"));
tailOffset = UNSAFE.objectFieldOffset
(k.getDeclaredField("tail"));
} catch (Exception e) {
throw new Error(e);
}
}
public ConcurrentLinkedQueue() {
head = tail = new Node<E>(null);
}无界队列；FIFO；线程安全的队列，乐观锁；
添加元素，元素不可为空
单链表
入栈
public boolean offer(E e) {
checkNotNull(e);
final Node<E> newNode = new Node<E>(e);
for (Node<E> t = tail, p = t;;) {
Node<E> q = p.next;
if (q == null) {
// p是最后一个节点
if (p.casNext(null, newNode)) {
//CAS成功,更新线性节点，让e成为queue的新节点
if (p != t) // p 节点不是 tail节点
casTail(t, newNode); //c更新tail节点
return true;
}
//否则其他线程在操作，下次再试
}
else if (p == q)//指向自己的情况
//t != (t=tail(新尾节点))，p = 新尾节点
//t == 还是新尾节点，p = 头节点 ；重新开始
p = (t != (t = tail)) ? t : head;
else //3.重新定位新尾节点
//p!=t:p不再是原来的尾节点
//t != (t = tail):尾节点被修改过
//p不再是原来的尾节点 并且 尾节点被修改过 就让p等于修改过的尾节点；否则让p等于它的后继节点
p = (p != t && t != (t = tail)) ? t : q;
}
}
出栈
public E poll() {
restartFromHead:
for (;;) {
for (Node<E> h = head, p = h, q;;) {
E item = p.item;
if (item != null && p.casItem(item, null)) {//item 不是空节点（不是初始化那个头节点），并且更新成功
if (p != h) // 头节点不是当前p节点 ，就更新新的头节点（延迟更新尾节点）, 即 head 指向第一个元素，且原head 指向自己
updateHead(h, ((q = p.next) != null) ? q : p);
return item;
}
else if ((q = p.next) == null) {//p.next == null ，说明当前为空队列，尝试CAS将头节点修改为p（p此时可能是哨兵节点）
updateHead(h, p);
return null;
}
else if (p == q) //p = p.next && p.next !=null ,指向自己了
continue restartFromHead;//重头开始
else //p != p.next && p.next !=null
p = q; //p 指向下个节点
}
}
}
size()返回可能不准确：如果在执行此方法的过程中添加或删除了元素，则返回的结果可能不准确。
ArrayBlockingQueue
成员变量有
final Object[] items;//实际存放的数组
/** 下次 take, poll, peek or remove 的index */
int takeIndex;
/**下次 put, offer, or add 的index */
int putIndex;
/**元素数量 */
int count;
/*
* 并发控制使用经典的双条件算法
*/
/** Main lock guarding all access */
final ReentrantLock lock;
/** take的条件，非空 */
private final Condition notEmpty;
/** puts的条件，不满 */
private final Condition notFull;
/**
* Shared state for currently active iterators, or null if there
* are known not to be any. Allows queue operations to update
* iterator state.
*/
transient Itrs itrs = null;有界阻塞队列，FIFO；
构造函数，需传入容量大小
典型的“有界缓冲区” ，这是一个经典的“有界缓冲区”，其中固定大小的数组包含生产者插入和消费者提取的元素。一旦创建，容量就无法更改。将元素放入完整队列将导致操作阻塞；从空队列中获取元素的尝试将类似地被阻止。
放入操作
public void put(E e) throws InterruptedException {
checkNotNull(e);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == items.length)
notFull.await(); //队列满，等待空位
enqueue(e);
} finally {
lock.unlock();
}
}
//将元素加入队列，
private void enqueue(E x) {
final Object[] items = this.items;
items[putIndex] = x;
if (++putIndex == items.length)
putIndex = 0;
count++;
notEmpty.signal(); //非空条件唤醒
}获取操作
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == 0)
notEmpty.await();//队列空了，等待放入
return dequeue();
} finally {
lock.unlock();
}
}
//元素取出
private E dequeue() {
// assert lock.getHoldCount() == 1;
// assert items[takeIndex] != null;
final Object[] items = this.items;
@SuppressWarnings("unchecked")
E x = (E) items[takeIndex];
items[takeIndex] = null;
if (++takeIndex == items.length)
takeIndex = 0;
count--;
if (itrs != null)
itrs.elementDequeued();
notFull.signal();//不满条件唤醒
return x;
}size()访问也是带锁的
public int size() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return count;
} finally {
lock.unlock();
}
}LinkedBlockingQueue
内部成员有以下。
static class Node<E> {
E item;
/**
* One of:
* - the real successor Node
* - this Node, meaning the successor is head.next
* - null, meaning there is no successor (this is the last node)
*/
Node<E> next;
Node(E x) { item = x; }
}
/** The capacity bound, or Integer.MAX_VALUE if none */
private final int capacity;
/** Current number of elements */
private final AtomicInteger count = new AtomicInteger();
/**
* Head of linked list.
* Invariant: head.item == null
*/
transient Node<E> head;
/**
* Tail of linked list.
* Invariant: last.next == null
*/
private transient Node<E> last;
/** Lock held by take, poll, etc */
private final ReentrantLock takeLock = new ReentrantLock();
/** Wait queue for waiting takes */
private final Condition notEmpty = takeLock.newCondition();
/** Lock held by put, offer, etc */
private final ReentrantLock putLock = new ReentrantLock();
/** Wait queue for waiting puts */
private final Condition notFull = putLock.newCondition();可选有界队列；构造函数，不传容量则为Integer.MAX_VALUE ，否则有具体容量大小
每次插入对象，都要创建Node节点，对比ArrayBlockingQueue，这可能在长时间内需要高效并发地处理大批量数据时，对于GC可能存在很大的影响。
offer 和 take 2把锁；offer 的同时可以take ,对比ArrayBlockingQueue提高吞吐量，增加整个队列的并发性
放入元素，元素必须非空
public boolean offer(E e) {
if (e == null) throw new NullPointerException();//非空
final AtomicInteger count = this.count;
if (count.get() == capacity)
return false;
int c = -1;
Node<E> node = new Node<E>(e);
final ReentrantLock putLock = this.putLock;
putLock.lock();
try {
if (count.get() < capacity) {
enqueue(node); //增加元素
c = count.getAndIncrement(); //count = 0 ,increment后 count = 1,c = prev of count = 0
if (c + 1 < capacity) //增加后，仍然有空位还可增加，则唤醒其他生产者线程
notFull.signal();
}
} finally {
putLock.unlock();
}
if (c == 0) //添加成功，唤醒消费者
signalNotEmpty();
return c >= 0;
}
private void signalNotEmpty() {
final ReentrantLock takeLock = this.takeLock;
takeLock.lock();
try {
notEmpty.signal();
} finally {
takeLock.unlock();
}
}取出元素
public E take() throws InterruptedException {
E x;
int c = -1; //队列长度
final AtomicInteger count = this.count;
final ReentrantLock takeLock = this.takeLock;
takeLock.lockInterruptibly();
try {
while (count.get() == 0) {//没有元素，非空条件.await
notEmpty.await();
}
x = dequeue(); //移除元素
c = count.getAndDecrement();//队列元素自减，自减后，c = prev of count
if (c > 1) //移除后仍然有元素，非空条件唤醒其他消费线程
notEmpty.signal();
} finally {
takeLock.unlock();
}
if (c == capacity) //c == capacity 表示 操作前是满的， 现在不满了，唤醒生产者，
signalNotFull();
return x;
}
private void signalNotFull() {
final ReentrantLock putLock = this.putLock;
putLock.lock();
try {
notFull.signal();
} finally {
putLock.unlock();
}
}PriorityBlockingQueue
SynchronousQueue
这是阻塞队列，继承BlockingQueue
每个插入操作都必须等待另一个线程执行相应的移除操作，反之亦然。同步队列没有任何内部容量，甚至没有一个容量。
peek() 无法返回元素，即使有值；可以通过take() , poll() ,取出同时移除
无法使用迭代器，iterator()返回的是空的迭代器
取出函数：take() ,poll()
插入函数：put(e) ,offer(e) ;元素非空
DelayQueue
TransferQueue
LinkedTransferQueue
ArrayDuque
LinkedList
IdentityLinkedList
Deque
继承Queue的接口
线性集合，头和尾均支持插入和删除；Deque 是 “double ended queue”的缩写 , 双端队列；
定义了访问deque两端元素的方法。提供了插入、移除和检查元素的方法。这些方法中的每一种都有两种形式：一种是在操作失败时抛出异常，另一种是返回特殊值（null或false，具体取决于操作）。
无界；
不支持索引服务
当作栈是FILO；也可以当作队列FIFO
LinkedBlockingDeque
ConcurrentLinkedDeque
内部维护 头节点、尾节点
private transient volatile Node<E> head;
private transient volatile Node<E> tail;
//以下是cas 更新具体节点
private static final sun.misc.Unsafe UNSAFE;
private static final long headOffset;
private static final long tailOffset;
static {
PREV_TERMINATOR = new Node<Object>();
PREV_TERMINATOR.next = PREV_TERMINATOR;
NEXT_TERMINATOR = new Node<Object>();
NEXT_TERMINATOR.prev = NEXT_TERMINATOR;
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class<?> k = ConcurrentLinkedDeque.class;
headOffset = UNSAFE.objectFieldOffset
(k.getDeclaredField("head"));
tailOffset = UNSAFE.objectFieldOffset
(k.getDeclaredField("tail"));
} catch (Exception e) {
throw new Error(e);
}
}Node节点
static final class Node<E> {
volatile Node<E> prev;
volatile E item;
volatile Node<E> next;
}元素不可为空；线程安全；size() 不实时；批量操作addAll、removeAll、retanall、containsAll、equals和toArray不能保证以原子方式执行。
支持FIFO ,FILO
添加头元素、尾元素 ；这里也用到了延迟更新head 和 tail 的指向，每隔一次插入，更新一次head 和 tail
//添加头元素
private void linkFirst(E e) {
checkNotNull(e);
final Node<E> newNode = new Node<E>(e);
restartFromHead:
for (;;)
for (Node<E> h = head, p = h, q;;) {
if ((q = p.prev) != null &&
(q = (p = q).prev) != null)
// 每次都要检测头节点更新
// 如果 p == q, 我们要更新p = 新的头节点 （其他线程插入了）
p = (h != (h = head)) ? h : q;
else if (p.next == p) // PREV_TERMINATOR
continue restartFromHead;
else {
// p是头节点，现在新节点设置成头节点
//lazySetNext 就是在不需要让共享变量的修改立刻让其他线程可见的时候，以设置普通变量的方式来修改共享状态，可以减少不必要的内存屏障，从而提高程序执行的效率。(保证操作的有序性，不保证可见性)
newNode.lazySetNext(p); // CAS piggyback
if (p.casPrev(null, newNode)) { //是否能更新成头节点
// newNode成功 插入到p 的前面
if (p != h) // 一次跳2个节点
casHead(h, newNode); //更新头节点
return;
}
//没有成功CAS 操作，被其他线程捷足先登；继续重读
}
}
}
//添加尾元素
//情况1 ： p = tail ,p.next != null && p.next.next != null ,此时 Deque.tail 后面有2个节点 ，此时要重新将p 指向 为新的最后节点
//情况2： p.pre = p ， 前一个节点 指向自己了，则重新开始
//情况3： p 是最后节点 ，newNode插入，即更新 newNode.prev = p 和 p.next = newNode 。若 p != t ，更新tail = newNode ,此时为tail = 最后节点 ；若 p == t ，此时为tail != 最后节点 , newNode == 最后节点
private void linkLast(E e) {
checkNotNull(e);
final Node<E> newNode = new Node<E>(e);
restartFromTail:
for (;;)
for (Node<E> t = tail, p = t, q;;) {
if ((q = p.next) != null &&
(q = (p = q).next) != null)
//每次校验，并 p = 新尾节点 （其他线程插入了）
// Check for tail updates every other hop.
// If p == q, tail 已被插入 ;
//t == tail , 说明Deque.tail 更新指向， p = t
//t != tail ，说明Deque.tail 延迟更新，p = q ，q 是最后一个节点，但tail 不指向它
p = (t != (t = tail)) ? t : q;
else if (p.prev == p) // NEXT_TERMINATOR
continue restartFromTail;
else {
// p 是最后一个 ，newNode 的前节点设置为p
newNode.lazySetPrev(p); // CAS piggyback
if (p.casNext(null, newNode)) {
//newNode 更新插入到 p 的后面
if (p != t) //一次跳2个节点
casTail(t, newNode);
return;
}
//没有成功CAS 操作，被其他线程捷足先登；继续重读
}
}
}移除头元素、尾元素
public E pollFirst() {
//每次循环 p = 第1个元素
//第1个元素 不为空，就 p 的item = null ,并从队列中移除
for (Node<E> p = first(); p != null; p = succ(p)) {
E item = p.item;
if (item != null && p.casItem(item, null)) {
unlink(p);
return item;
}
}
return null;
}
//每次循环 p = 最后元素
//最后元素 不为空，就 p 的item = null ,并从队列中移除
public E pollLast() {
for (Node<E> p = last(); p != null; p = pred(p)) {
E item = p.item;
if (item != null && p.casItem(item, null)) {
unlink(p);
return item;
}
}
return null;
}