容器总结

容器总结(不是详解)

- List
	ArrayList
	LinkedList
	Vector
	Stack
	CopyOnWriteArrayList
- Set
	HashSet
	TreeSet
	LinkedHashSet
	ConcurrentSkipListSet
- Map
	HashMap
	LinkedHashMap
	ConcurrentHashMap
	HashTable
	TreeMap
	ConcurrentSkipListMap
- Queue
	ConcurrentLinkedQueue
	LinkedBlockingQueue
	ArrarBlocakingQueue
	PriorityQueue

一、概览

1.List、Set、Map是否继承自Collection接口？

List、Set 是，Map 不是。Map是键值对映射容器，与List和Set有明显的区别，而Set存储的零散的元素且不允许有重复元素（数学中的集合也是如此），List是线性结构的容器，适用于按数值索引访问元素的情形。

2、Collection和Collections的区别？

Collection是一个接口，它是Set、List等容器的父接口；
Collections是个一个工具类，提供了一系列的静态方法来辅助容器操作，这些方法包括对容器的搜索、排序、线程安全化等等。

二、List

1、各个List的存储性能和特性

- ArrayList
	底层：数组
- Vector
	底层：数组
	Vector是线程安全的容器，性能上较ArrayList差
- Stack
	底层：Vector
- LinkedList
	底层：双向链表
	从JDK1.7开始，LinkedList 由双向循环链表改为双向链表
- CopyOnWriteArrayList
	原理：写复制
	在很多应用场景中，读操作都远远多于写操作，对于这些场景，我们希望其读操作尽可能快，即使写操作慢一些也没关系。而因为读操作不会对数据进行修改，所以产生了读写锁，其读与读之间不会阻塞，但是读与写、写与写之间还是会阻塞。而CopyOnWriteArrayList进一步优化，将读取性能发挥到了极致，这个容器读与读之间不会阻塞，读与写之间也不会阻塞，只有写与写之间需要同步等待，这样读操作性能得到了提升
	其原理就是写复制，当这个List需要修改时，并不改变原有内容，而是将原有数据进行复制出一个副本，对副本内容进行修改，修改完成后用修改后的副本替换原有数据。这样就保证写操作不会影响读操作了，而且其内部数组使用了volatile修饰，读取线程可以立即察觉到这个修改。
	存在问题
	1.内存占用问题：因进行写操作的时候，内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象。如果这些对象占用的内存比较大，那么这个时候很有可能造成频繁的 GC。
	数据一致性问题：CopyOnWrite 容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果希望写入的的数据马上能读到，就不要使用此容器。

- ArrayList和LinkedListed都是非线程安全的，可以通过工具类Collections中的synchronizedList方法将其转换成线程安全的容器（这是对装潢模式的应用，将已有对象传入另一个类的构造器中创建新的对象来增强实现）

三、Set

- HashSet
	底层使用HashMap，遇到hashcode相同的元素不会直接拉链，而是使用equals进行比对，确认不重复再进行插入
	元素是无序的add(),remove(),contains()方法的时间复杂度是O(1)
- TreeSet 
	底层使用TreeMap，TreeMap是底层是红黑树
	它里面的元素是有序的,add(),remove(),contains()方法的时间复杂度是O(logn) 
- LinkedHashSet
	继承自HashSet，内部使用LinkedHashMap
- ConcurrentSkipListSet
	底层使用ConcurrentSkipListMap，跳表，输出有序

四、Map

HashMap
	以前有写过
HashTable
	HashTable和HashMap内部原理相同，Hashtable使用了synchronized关键字，是线程安全的，而HashMap不是线程安全的
	HashMap允许K/V都为null  HashMapK/V都不允许为null
TreeMap
	红黑树
LinkedHashMap
	继承自HashMap，每个节点变为双向链表，可以实现按照插入顺序输出元素
ConcurrentHashMap
	HashMap不是线程安全的，基于减小锁粒度的原理，我们将HashMap内部分为16段分别加锁，相互之间不需要同步，从而提升其吞吐量
ConcurrentSkipListMap
	原理： 跳表，对内部Node所有操作都时基于CAS

五、Queue

- ConcurrentLinkedQueue
	基于CAS
- BlockingQueue
	- 内部使用生产者消费者模式，当有线程来取数据时，若队列为空，则将其休眠，有数据时将其唤醒。
- LinkedBlockingQueue
	-内部使用链表的阻塞队列，适合做无界队列，内部元素可以动态增加，不会因为初始值很大，而占据很大的内存
- ArrarBlockingQueue
	- 内部使用队列，适合做有界队列，存取快，但是在创建时需要指定队列大小，提前创建好队列。创建完成后大小不能调整。类似循环链表，有takeIndex和putIndex两个指针，每次从putIndex处存，从takeIndex处取。
- PriorityQueue
	-优先队列，使用小顶堆实现，保证根节点为最小元素，每次存取后需要重新调整堆

五、异同

List和Set区别

List元素以线性方式存储，集合中可以存放重复对象
Set集合中的对象不按特定的方式排序，并且没有重复对象

ArrayList和Array有什么区别？

Array可以容纳基本类型和对象，而ArrayList只能容纳对象。
Array是指定大小的，而ArrayList大小是固定的