2.1 集合
Java的集合类被定义在Java.util包中，主要有4种集合，分别为List、Queue、Set和Map，每种集合的具体分类如图2-1所示。
图2-1
2.1.1 List：可重复
List是非常常用的数据类型，是有序的Collection，一共有三个实现类，分别是ArrayList、Vector和LinkedList。
1．ArrayList：基于数组实现，增删慢，查询快，线程不安全
ArrayList是使用最广泛的List实现类，其内部数据结构基于数组实现，提供了对List的增加（add）、删除（remove）和访问（get）功能。
ArrayList的缺点是对元素必须连续存储，当需要在ArrayList的中间位置插入或者删除元素时，需要将待插入或者删除的节点后的所有元素进行移动，其修改代价较高，因此，ArrayList不适合随机插入和删除的操作，更适合随机查找和遍历的操作。
ArrayList不需要在定义时指定数组的长度，在数组长度不能满足存储要求时，ArrayList会创建一个新的更大的数组并将数组中已有的数据复制到新的数组中。
2．Vector：基于数组实现，增删慢，查询快，线程安全
Vector的数据结构和ArrayList一样，都是基于数组实现的，不同的是Vector支持线程同步，即同一时刻只允许一个线程对Vector进行写操作（新增、删除、修改），以保证多线程环境下数据的一致性，但需要频繁地对Vector实例进行加锁和释放锁操作，因此，Vector的读写效率在整体上比ArrayList低。
3．LinkedList：基于双向链表实现，增删快，查询慢，线程不安全
LinkedList采用双向链表结构存储元素，在对LinkedList进行插入和删除操作时，只需在对应的节点上插入或删除元素，并将上一个节点元素的下一个节点的指针指向该节点即可，数据改动较小，因此随机插入和删除效率很高。但在对LinkedList进行随机访问时，需要从链表头部一直遍历到该节点为止，因此随机访问速度很慢。除此之外，LinkedList还提供了在List接口中未定义的方法，用于操作链表头部和尾部的元素，因此有时可以被当作堆栈、队列或双向队列使用。
2.1.2 Queue
Queue是队列结构，Java中的常用队列如下。
◎ ArrayBlockingQueue：基于数组数据结构实现的有界阻塞队列。
◎ LinkedBlockingQueue：基于链表数据结构实现的有界阻塞队列。
◎ PriorityBlockingQueue：支持优先级排序的无界阻塞队列。
◎ DelayQueue：支持延迟操作的无界阻塞队列。
◎ SynchronousQueue：用于线程同步的阻塞队列。
◎ LinkedTransferQueue：基于链表数据结构实现的无界阻塞队列。
◎ LinkedBlockingDeque：基于链表数据结构实现的双向阻塞队列。
2.1.3 Set：不可重复
Set核心是独一无二的性质，适用于存储无序且值不相等的元素。对象的相等性在本质上是对象的HashCode值相同，Java依据对象的内存地址计算出对象的HashCode值。如果想要比较两个对象是否相等，则必须同时覆盖对象的hashCode方法和equals方法，并且hashCode方法和equals方法的返回值必须相同。
1．HashSet:HashTable实现，无序
HashSet存放的是散列值，它是按照元素的散列值来存取元素的。元素的散列值是通过元素的hashCode方法计算得到的，HashSet首先判断两个元素的散列值是否相等，如果散列值相等，则接着通过equals方法比较，如果equls方法返回的结果也为true, HashSet就将其视为同一个元素；如果equals方法返回的结果为false, HashSet就不将其视为同一个元素。
2．TreeSet：二叉树实现
TreeSet基于二叉树的原理对新添加的对象按照指定的顺序排序（升序、降序），每添加一个对象都会进行排序，并将对象插入二叉树指定的位置。
Integer和String等基础对象类型可以直接根据TreeSet的默认排序进行存储，而自定义的数据类型必须实现Comparable接口，并且覆写其中的compareTo函数才可以按照预定义的顺序存储。若覆写compare函数，则在升序时在this．对象小于指定对象的条件下返回-1，在降序时在this．对象大于指定对象的条件下返回1。
3．LinkHashSet:HashTable实现数据存储，双向链表记录顺序
LinkedHashSet在底层使用LinkedHashMap存储元素，它继承了HashSet，所有的方法和操作都与HashSet相同，因此LinkedHashSet的实现比较简单，只提供了4个构造方法，并通过传递一个标识参数调用父类的构造器，在底层构造一个LinkedHashMap来记录数据访问，其他相关操作与父类HashSet相同，直接调用父类HashSet的方法即可。
2.1.4 Map
1．HashMap：数组+链表存储数据，线程不安全
HashMap基于键的HashCode值唯一标识一条数据，同时基于键的HashCode值进行数据的存取，因此可以快速地更新和查询数据，但其每次遍历的顺序无法保证相同。HashMap的key和value允许为null。
HashMap是非线程安全的，即在同一时刻有多个线程同时写HashMap时将可能导致数据的不一致。如果需要满足线程安全的条件，则可以用Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
HashMap的数据结构如图2-2所示，其内部是一个数组，数组中的每个元素都是一个单向链表，链表中的每个元素都是嵌套类Entry的实例，Entry实例包含4个属性：key、value、hash值和用于指向单向链表下一个元素的next。
图2-2
HashMap常用的参数如下。
◎ capacity：当前数组的容量，默认为16，可以扩容，扩容后数组的大小为当前的两倍，因此该值始终为2n。
◎ loadFactor：负载因子，默认为0.75。
◎ threshold：扩容的阈值，其值等于capacity×loadFactor。
HashMap在查找数据时，根据HashMap的Hash值可以快速定位到数组的具体下标，但是在找到数组下标后需要对链表进行顺序遍历直到找到需要的数据，时间复杂度为O(n)。
为了减少链表遍历的开销，Java 8对HashMap进行了优化，将数据结构修改为数组+链表或红黑树。在链表中的元素超过8个以后，HashMap会将链表结构转换为红黑树结构以提高查询效率，因此其时间复杂度为O(log N)。Java 8 HashMap的数据结构如图2-3所示。
图2-3
2．ConcurrentHashMap：分段锁实现，线程安全
与HashMap不同，ConcurrentHashMap采用分段锁的思想实现并发操作，因此是线程安全的。ConcurrentHashMap由多个Segment组成（Segment的数量也是锁的并发度），每个Segment均继承自ReentrantLock并单独加锁，所以每次进行加锁操作时锁住的都是一个Segment，这样只要保证每个Segment都是线程安全的，也就实现了全局的线程安全。ConcurrentHashMap的数据结构如图2-4所示。
图2-4
在ConcurrentHashMap中有个concurrencyLevel参数表示并行级别，默认是16，也就是说ConcurrentHashMap默认由16个Segments组成，在这种情况下最多同时支持16个线程并发执行写操作，只要它们的操作分布在不同的Segment上即可。并行级别concurrencyLevel可以在初始化时设置，一旦初始化就不可更改。ConcurrentHashMap的每个Segment内部的数据结构都和HashMap相同。
Java 8在ConcurrentHashMap中引入了红黑树，具体的数据结构如图2-5所示。
图2-5
3．HashTable：线程安全
HashTable是遗留类，很多映射的常用功能都与HashMap类似，不同的是它继承自Dictionary类，并且是线程安全的，同一时刻只有一个线程能写HashTable，并发性不如ConcurrentHashMap。
4．TreeMap：基于二叉树数据结构
TreeMap基于二叉树数据结构存储数据，同时实现了SortedMap接口以保障元素的顺序存取，默认按键值的升序排序，也可以自定义排序比较器。
TreeMap常用于实现排序的映射列表。在使用TreeMap时其key必须实现Comparable接口或采用自定义的比较器，否则会抛出java.lang.ClassCastException异常。
5．LinkedHashMap：基于HashTable数据结构，使用链表保存插入顺序
LinkedHashMap为HashMap的子类，其内部使用链表保存元素的插入顺序，在通过Iterator遍历LinkedHashMap时，会按照元素的插入顺序访问元素。