Java集合

类库关系图

类库关系图

List

ArrayList：Object数组

• CopyOnArrayList

  
  CopyOnArrayList

  读远多于写场景的ArrayList线程安全替代者。

Vector： Object数组

LinkedList： 双向循环链表

Set

HashSet（无序，唯一）

• LinkedHashSet

  LinkedHashSet 继承与 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。

TreeSet（有序，唯一）

红黑树(自平衡的排序二叉树。)

• ConcurrentSkipListSet

  TreeSet的线程安全替代者。

  https://blog.csdn.net/sunxianghuang/article/details/52221913

并发场景使用跳跃表替代红黑树原因：

1.树的增删操作维持平衡时，涉及多个节点的转换，并发场景只能锁上整棵树。

2.基于链表的跳跃表增删操作可基于CAS实现粒度更小的加锁。

Queue

boolean add(E e)

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.

E element()

Retrieves, but does not remove, the head of this queue.

boolean offer(E e)

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.

E peek()

Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

E poll()

Retrieves and removes the head of this queue, or returns null if this queue is empty.

E remove()

Retrieves and removes the head of this queue.

关系图

关系图

BlockingQueue

void put(E e)

Inserts the specified element into this queue, waiting if necessary for space to become available.

E take()

Retrieves and removes the head of this queue, waiting if necessary until an element becomes available.

• ArrayBlockingQueue

  基于数组的阻塞队列实现，在其内部维护了一个定长数组，以便缓存队列中的数据对象，由于ArrayBlockingQueue内部只有一个锁对象（ReentrantLock），因此读写没有实现分离，也就意味着生产消费不能完全并行。由于长度需要定义，因此也叫有界队列。

• LinkedBlockingQueue

  基于链表的阻塞队列实现，同ArrayBlockingQueue类似，其内部也维持着一个数据缓冲队列（链表构成）。

  LinkedBlockingQueue之所以较ArrayBlockingQueue更加高效的处理并发数据，是因为内部实现采用了2把锁，也就是实现了入队、出队分别上锁，即读写分离，从而生产者、消费者完全到达了并行。

  无需定义长度，也叫无界队列。当然不定义长度时，需要注意下生产者的速度和消费者的速度，因为默认情况下队列长度是Integer.MAX_VALUE。

• SynchronousQueue

  一个没有缓冲的队列，生产者生产的数据会直接被消费者获取到并消费。它是一个轻量级的阻塞队列，因为不具备容量，在用法上，只能是一个线程阻塞着取元素，等待另一个线程往队列里面放入一个元素，然后会被等待着的线程立即取走，其实就是实现了线程间的轻量级的单元素交换。

• PriorityBlockingQueue

  基于优先级（二叉树堆）的阻塞队列（优先级的判断通过构造函数传入的Compator对象决定，也就是传入队列中对象必须实现Comparable接口）。

  在实现PriorityBlockingQueue时，内部控制线程同步的锁采用的是公平锁，也是一个无界的队列。

  通俗的来说，不是先进先出的队列了，而是谁的优先级低谁先出去。那么可以思考下，是否每次add/offer都会进行一次排序呢？我们是否需要按照优先级进行全排序呢？实际上，可以大致看一看add/take方法，会了解到PriorityBlockingQueue的设计思想：在add时，并不进行排序处理，当进行take时，选择优先级最小的拿出来而已，这样既避免了在add时花费时间排序，又在take时节省了时间，因为并没有全排序，仅仅是挑选了一个优先级低的元素而已。

• DelayQueue

  带有延迟时间的Queue,其中的元素只有当指定的延迟时间到了，才能从队列中获取到该元素。队列中的元素必须实现Delayed接口，没有大小限制。本质上来说，是借助于PriorityBlockingQueue来实现的，以延迟时间作为优先级。延迟队列的应用场景很多，比如缓存超时的数据进行移除，任务超时处理，空闲连接的关闭等等。

Deque

ConcurrentLinkedQueue

一个适用于高并发场景下的队列，通过无锁的方式（CAS+volatile），实现了高并发下的高性能，通常ConcurrentLinkedQueue的性能好于BlockingQueue。

它是一个基于链接节点的无界线程安全队列，遵循先进先出的原则，头是最先加入的，尾是最近加入的，不允许加入null元素。

注意add()/offer()都是加入元素的方法，这里没有区别；poll()/peek()是取出头元素的方法，区别点在于poll会删除元素，而peek不会。

要特别注意到由于它的非阻塞性，并不像其他普通集合那样，获取队列的SIZE的方法并不是常量时间的花费，而是O（N）的，因此我们应该尽可能避免使用size()方法，可以考虑使用isEmpty()代替。

虽然使用到了CAS+VOLATILE的机制避免了锁，但是我们要明白的是，这只是保证单个操作，如peek()的安全，但是多个操作如果想保证的话，需要使用锁机制来达到同步的效果。

Map

HashMap

非线程安全

JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

HashMap 的长度为什么是2的幂次方？

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

这个算法应该如何设计呢？

我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。

• LinkedHashMap

  LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。

• ConcurrentHashMap

  HashMap的线程安全替代者。

底层数据接口和HashMap一致，1.7之前数组+链表，1.8之后数组+链表+红黑树。

实现线程安全的方式（重要）： ① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。（默认分配16个Segment，比Hashtable效率提高16倍。） 到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

HashTable

线程安全

数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的

TreeMap

红黑树（自平衡的排序二叉树）

• ConcurrentSkipListMap

  TreeMap的线程安全替代者。

LinkedHashMap

在HashMap基础上，引入了链表保存元素加入顺序，方便实现基于最近访问原则的淘汰机制（删除链表尾）。

WeakHashMap

https://www.cnblogs.com/yw-ah/p/5830458.html

http://www.importnew.com/23182.html