JAVA 中的集合

Java中的集合主要有两个接口，Map 和 Collection。

Collection接口的子接口有List, Set, Queue。

常见的实现类：

List: linkedList, ArrayList

Set:HashSet, TreeSet(继承于SortedSet接口)

Queue: ArrayDeque(继承于Deque)

Map: HashMap, HashTable, TreeMap(根据键的大小排序)， linkedHashMap（根据插入顺序排序）

java.util包下的容器大部分是非线程安全的。

线程安全的实现类有HashTable, Vector，这两个类的内部方法是加了synchronized关键字，所以线程安全，但是性能不好，不建议使用。

Collections使用装饰器模式，提供了线程安全的包装类。

JAVA5之后提供juc包， 提供了线程安全的高性能实现类。主要包括三类：Blocking类，Concurrent类，CopyOnWrite类。

Concurrent：

内部很多操作使用 cas 优化，缩小锁粒度等操作

比如jdk1.7的ConcurrentHashMap,分段加锁。 jdk1.8 CAS + synchronized + Node + 红黑树。

ConcurrentlinkedQueue

Blocking ：

实现基于锁

BlockingQueue

对队列两端设置dummy结点，然后开头和结尾设置两个锁。同时可以有一个生产者和一个消费者执行。

CopyOnWrite

CopyonWrite 之类容器修改开销相对较重

CopyOnWrite写入时拷贝的思想， 更改操作会将底层数据拷贝一份，在拷贝上执行修改，不影响其他线程的读操作，读写分离。

CopyOnWriteArrayList

HashMap的并发死链问题

HashMap在扩容的时候创建一个新的数组，容量是原数组的两倍，然后把旧数组的元素重新计算索引位置放入新数组。jdk 1.7的时候发生hash冲突后新元素在链表的头部插入，而1.8之后改为在链表的尾部插入。1.7的情况下如果两个线程都对数组进行扩容可能会导致并发死链，产生链表的循环。

红黑树在内存中比b树快, 查找的次数少。但是树的深度大，所以磁盘中不适合用红黑树。

TreeMap底层是一个红黑树，根据键的自然顺序或者创建时提供的comparator进行排序

插入，查找，空间有区别。

有哪些线程安全的List

Vector, Collections.SynchronizedList, CopyOnWriteList

一个数组，初始容量为10， 每次扩容50%。 如果是以append的形式则速度还可以，但是根据index插入会很慢。

一个HashMap, 值为一个静态常量Object对象， PRESENT。

插入：add                offer                                        put

获取：remove          poll                                         take

        抛异常               返回错误值（超时）                阻塞