Collection

Collection是Java的一个集合容器抽象。这里面分为三种类型的集合容器：List、Set、Queue，其中List主要是提供类似数组一样的数据结构。Set提供不重复数据的数据结构。Queue提供队列来存储数据的方式。

List

• ArrayList: 基于动态数组实现，保证添加数据的顺序。可以随机访问。

• Vector：实现与ArrayList差不多，但是是线程安全的。每个方法都直接使用synchronized修饰。现在基本不用。

• LinkedList：双向链表结构，数据是有序的，访问时可从链表头部开始访问，也可从尾部开始访问。主要看要获取的数据是偏链表头部还是链表尾部。偏向通过size >> 1也就是链表的大小size / 2来判断，如果index < (size >> 1)从头部开始迭代访问，反之从尾部开始访问。可用作于栈、队列和双向队列。

Set

• HashSet：底层基于HashMap实现，数据是无序的，数据不可重复。查找速度很快，因为HashMap底层根据key的hash值来定位数据位置。

• TreeSet：继承于SortedSet，保证数据的自然排序，不保证插入顺序，基于TreeMap实现。TreeMap底层基于红黑树实现。查找速度比HashSet慢。

• LinkedHashSet：继承于HashSet，本类只有几个构造器，构造器都基于super HashSet，而HashSet中提供的有几个构造器是基于LinkedHashMap的。所以LinkedHashSet拥有LinkedHashMap的双向链表特性。而且查找也通过hash来查找，具有与HashSet的查找速度。

Queue

• LinkedList：LinkedList保证数据的插入顺序，可从头部和尾部访问数据。

• PriorityQueue：优先队列，使用二叉树最小堆顶结构实现。

Map

Map以key,value的格式存储数据。

• HashMap：可存放null key， 1.7以前基于数组+单向链表+hash实现，1.8以后基于数组+单向链表+红黑树+hash实现。查找速度很快。只需通过计算key的hash，即可得到数据的位置。

• TreeMap：不可存放null key，基于红黑树实现，查找速度比HashMap慢，因为要通过与Entry节点的数据做对比，当迭代到key值一样时，才能找出数据。

• Hashtable：不可存放null key， 基于hash+单向链表实现，线程安全的map。相关方法都使用了synchronized修饰。现在基本不用，如果要使用线程安全的map一般使用JUC的ConcurrentHashMap。

• LinkedHashMap：LinkedHashMap基于HashMap实现，是一个双向链表结构的HashMap。