线性表

由零个或者多个数据元素组成的有限序列。第一个元素无前驱，最后一个元素没有后继，其他元素有且只有一个前驱或者后继

栈、队列

栈Queue	队列Stack
先进先出	先进后出
LinkedList：可以用它来实现双向队列。PriorityQueue：基于堆结构实现，可以用它来实现优先队列。

线性结构数组和链表区别

	定义	优点	缺点
数组	顺序存储，存储元素连续	查询快	增删慢，增删需要挪动后面的元素
链表	链式存储，存储不连续，每个元组知道其下一个元素的位置	增删快	查找慢，需要从第一个一直往后遍历直到找到要查的元素

JAVA数据集合

List

有序可重复，用户可以通过索引访问元素

	ArrayList	LinkedList	Vector
元素null	可以	可以	最后一个元素后面的任何数组元素都为null
线程安全	否	否	是（一个线程同时只能访问一个方法）
内存	动态数组实现，连续存储空间	链表(双向)存储，空间不连续	存储矢量分量的数组缓冲区, 矢量的容量是这个数组缓冲区的长度，并且至少足够大以包含所有矢量的元素。
优点	支持随机访问	增删快，LinkedList 还可以用作栈、队列和双向队列。	线程安全

set

无序不可重复，最多一个null值

treeSet	基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。
HashSet	基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
LinkedHashSet	具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序。

Map

key-value键值对，不允许重复键

	HashMap	HashTable	CurrentHashMap	TreeMap	LinkedHashMap
线程安全	否	是	是	否	否
键值	可以为空	不可以为空	可以	不可以	可、
底层结构	数组+链表（1.7，头插）/数组+链表+红黑树（1.8尾插）	数组+链表	分段数组+链表	红黑树，每个key-value是一个节点。能够把他保存的记录按照键进行排序（默认升序），也可以自定义排序（重写比较器）	继承了HashMap，内部维护了一个双向链表，保存了记录的插入顺序（accessOrder=false或者访问顺序accessOrder=true）
扩容	8<链表长度<64,转为红黑树；数组默认长度为16，元素个数达到长度*0.75，扩容到两倍大。插入后扩容	通过加同步关键字实现线程安全，但锁是对整个结构的锁，性能较差。插入后扩容。插入后扩容	插入前扩容，同HashMap	就红黑树添加元素

备注：fail-safe(hashtable)和fail-fast(hashmap)区别：
fail-fast机制是在遍历一个集合时，集合元素不能被改动，否则抛Concurrent Modification Exception异常（注意：这种机制在多线程情况下可能会有集合元素发生改动，但未被检查出错误的情况发生。fail-fast只能说是尽力去发现改动并抛出异常，因此此类迭代器应该仅适用于检测bug）
fail-safe机制是任何对集合结构的修改都会在另一个此集合的复制品上体现，因此不会抛Concurrent Modification Exception异常。因此该机制也有一定缺陷（1. 需要复制集合 2. 无法保证读取的数据是原集合中的数据，即可能出现在线程A遍历集合的过程中线程B，对集合中某一元素进行了修改，导致线程A可能读取到线程B所修改的数据，而原始的数据）