Java

集合

Collection

List

ArrayList

实现原理：基于可变数组实现，默认容量10，最大为Integer.MAX_VALUE

适用场景：非线程安全，支持随机访问，插入和删除涉及到数组的拷贝，性能较低，适用于读多写少的场合。

LinkedList

实现原理：基于双向链表实现，所占空间相比ArrayList要少，因为ArrayList扩容1.5倍，存在空间浪费。

适用场景：非线程安全，不支持随机访问，实现了Queue接口，对头部或尾部做插入或删除操作效率很高，最多只影响一个节点。遍历用迭代器效率最高。

Vector

ArrayList的线程安全版本，通过synchronized关键字实现。性能较低，不常用。

CopyOnWriteArrayList

实现原理：写操作加锁，读操作不加锁。不直接对当前容器进行写操作，而是copy一个新容器，然后在新容器里写。写完后，将原容器的引用指向新容器。

适用场景：ArrayList线程安全版本，内存占用较大，只能保证数据的最终一致性。适用于读多写少的场合。

Set

HashSet：基于HashhMap，HashSet里存储的元素就是内部HashMap的key。

TreeSet：基于TreeMap，TreeSet里存储的元素就是内部TreeMap的key。

CopyOnWriteArraySet：基于CopyOnWriteArrayList，只不过不能添加重复元素。

ConcurrentSkipListSet：基于ConcurrentSkipListMap。

Queue

ArrayBlockingQueue：数组实现的有界阻塞队列，当队列满时，生产的线程会被阻塞。当队列为空时消费的线程被阻塞。基于ReentrantLock和Condition实现。

LinkedBlockingQueue：链表实现的有界阻塞队列。

ConcurrentLinkedQueue：链表实现的无阻塞队列，CAS+volatile保证线程安全。

PriorityQueue：基于堆实现。

DelayQueue:基于PriorityQueue实现的延迟队列。

Map

HashMap

实现原理

1.7 基于数组和链表实现。put时，通过k的hashcode算出索引，然后将Entry放到该位置。如果该位置已存在元素，则比较hashcode和equals方法，判断是否是同一个key，若相同则替换为新值并返回旧值。添加Entry节点前会判断是否要做resize操作，resize在多线程下可能会导致链表成环，造成cpu100%。

1.8 相比于1.7，多了红黑树。当链表长度超过8的时候，会变成红黑树。

LinkedHashMap

特点：继承自HashMap，可以按插入顺序或访问顺序(accessOrder为true时)遍历。

TreeMap

特点：红黑树实现，可按元素的顺序或特定比较器进行遍历。

ConcurrentHashMap

实现原理

1.7 基于分段锁，get不加锁，put先计算要put到哪个segment，再通过segment加锁put。

1.8 基于Node+CAS+synchronized

ConcurrentSkipListMap

特点：线程安全，基于跳跃表实现。

实现原理：插入和删除操作只需要改变影响到的节点的右引用，而右引用是用volatile修饰的。

并发

synchronized

实现：基于编译器时插入moniterenter和moniterexit指令，由JVM内部实现。

优点：不需要显式释放锁

缺点：效率低，线程上下文切换较多。但jdk1.6做了优化。偏向锁，轻量级锁，重量级锁。

java.util.concurrent

实现：基于Java语言实现。

优点：性能相对高，线程上下文切换较少。对锁的可控性更强，共享获取及超时获取。

缺点：需要显式释放锁。

AbstractQueuedSynchronizer

特点：其它并发工具的基础，内部封装了同步状态管理，线程的排队、等待与唤醒等等底层操作。

ReentrantLock

特点：分为公平锁和非公平锁，非公平锁是默认实现。公平锁对获取锁的条件更为苛刻，当锁没有被线程持有，还要保证等待队列为空，或者等待队列中没有其它线程在等待。（锁的释放到唤醒等待队列的线程有一个延迟过程）

获取锁：都是先尝试获取锁，没有获取到，则以当前线程构造一个节点加入到等待队列尾。加入到等待队列后，线程使用自旋的方式获取锁。如果前驱节点为头节点则尝试获取锁，否则进入等待状态。

释放锁：锁的释放就是将state-1直到为0。释放完还要唤醒等待队列的线程争夺锁。

ReentrantReadWriteLock

特点：读写锁在同一时刻可以允许多个读线程访问，但是在写线程访问时，所有的读线程和其它的写线程均被阻塞。读写锁比排它锁有更好的并发性和吞吐量。

读锁

获取：如果已经有读锁或者当前线程不是已经获取写锁的线程，则等待。如果获取了写锁，则增加写状态。写锁被获取，则其它读写线程被阻塞。

释放：基本和ReentrantLock相同

写锁

获取：如果已经有其它线程获取了写锁，则当前获取的线程被阻塞。

释放：基本和ReentrantLock相同

CountDownLatch

特点：一个或多个线程等待其它线程完成某操作后，再继续执行。

实现：构造方法初始化state变量的值。线程调用await方法，实际上是获取锁状态等不等于0，等于0则继续执行，否则循环cas并判断是否要进入阻塞状态。其它线程调用countDown方法，实际上就是释放锁的过程。当释放到0时，被阻塞线程则可以继续执行。

CyclicBarrier

特点：一组线程到达一个同步点后再一起往下执行，任意一个线程没到，则其它线程被阻塞。

实现：基于ReentrantLock和Condition。构造方法初始化需要被等待的线程数。调用await方法将值减1，当减到0时，唤醒被阻塞线程继续执行。否则该线程被阻塞。

Semaphore

特点：控制同时访问某资源的最大线程数量。

实现：基于AQS。线程调用acquire获取许可，release释放许可。若许可数量小于1，则等待其它线程释放许可。

StampedLock

特点：为控制读写访问采用了三种模式。StampedLock锁状态包含一个版本号和模式。

写：

读：

乐观读：

LockSupport：阻塞或唤醒一个线程。基于Unsafe的native实现。