1. 集合的简介

所有的集合类和集合接口都在java.util包下。

在内存中申请一块空间用来存储数据，在Java中集合就是替换掉定长的数组的一种引用数据类型。

我用过的一些 Java 集合类：

• ArrayList： 动态数组，实现了List接口，支持动态增长。
• LinkedList： 双向链表，也实现了List接口，支持快速的插入和删除操作。
• HashMap： 基于哈希表的Map实现，存储键值对，通过键快速查找值。
• HashSet： 基于HashMap实现的Set集合，用于存储唯一元素。
• TreeMap： 基于红黑树实现的有序Map集合，可以按照键的顺序进行排序。
• LinkedHashMap： 基于哈希表和双向链表实现的Map集合，保持插入顺序或访问顺序。
• PriorityQueue： 优先队列，可以按照比较器或元素的自然顺序进行排序。

2. List

List是有序的Collection，使用此接口能够精确的控制每个元素的插入位置，用户能根据索引访问List中元素。 存储一组不唯一（允许重复），有序的对象。常用的实现List的类有LinkedList，ArrayList，Vector，Stack。

• ArrayList是容量可变的非线程安全列表，其底层使用数组实现。当几何扩容时，会创建更大的数组，并把原数组复制到新数组。ArrayList支持对元素的快速随机访问，但插入与删除速度很慢。
• LinkedList本质是一个双向链表，与ArrayList相比，其插入和删除速度更快，但随机访问速度更慢。

3. Set

Set不允许存在重复的元素，与List不同，set中的元素是无序的。常用的实现有HashSet，LinkedHashSet和TreeSet。

• HashSet通过HashMap实现，HashMap的Key即HashSet存储的元素，所有Key都是用相同的Value，一个名为PRESENT的Object类型常量。使用Key保证元素唯一性，但不保证有序性。由于HashSet是HashMap实现的，因此线程不安全。
• LinkedHashSet继承自HashSet，通过LinkedHashMap实现，使用双向链表维护元素插入顺序。
• TreeSet通过TreeMap实现的，添加元素到集合时按照比较规则将其插入合适的位置，保证插入后的集合仍然有序。

set实现原理：Set集合通过内部的数据结构（如哈希表、红黑树等）来实现key的无重复。当向Set集合中插入元素时，会先根据元素的hashCode值来确定元素的存储位置，然后再通过equals方法来判断是否已经存在相同的元素，如果存在则不会再次插入，保证了元素的唯一性。

4. Map

Map 是一个键值对集合，存储键、值和之间的映射。Key 无序，唯一；value 不要求有序，允许重复。Map 没有继承于 Collection 接口，从 Map 集合中检索元素时，只要给出键对象，就会返回对应的值对象。主要实现有TreeMap、HashMap、HashTable、LinkedHashMap、ConcurrentHashMap。

• HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突），JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间
• LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
• HashTable：数组+链表组成的，数组是 HashTable 的主体，链表则是主要为了解决哈希冲突而存在的
• TreeMap：红黑树（自平衡的排序二叉树）
• ConcurrentHashMap：Node数组+链表+红黑树实现，线程安全的（jdk1.8以前Segment锁，1.8以后volatile + CAS 或者 synchronized）

5. 比较

5.1 结构特点

• List和Set是存储单列数据的集合，Map是存储键值对这样的双列数据的集合；
• List中存储的数据是有顺序的，并且值允许重复；
• Map中存储的数据是无序的，它的键是不允许重复的，但是值是允许重复的；
• Set中存储的数据是无顺序的，并且不允许重复，但元素在集合中的位置是由元素的hashcode决定，即位置是固定的（Set集合是根据hashcode来进行数据存储的，所以位置是固定的，但是这个位置不是用户可以控制的，所以对于用户来说set中的元素还是无序的）。

5.2 实现类

1. List接口有三个实现类：
   1.1 LinkedList
   基于链表实现，链表内存是散列的，增删快，查找慢；
   1.2 ArrayList
   基于数组实现，非线程安全，效率高，增删慢，查找快；
   1.3 Vector
   基于数组实现，线程安全，效率低，增删慢，查找慢；

2. Map接口有四个实现类：
   2.1 HashMap
   基于 hash 表的 Map 接口实现，非线程安全，高效，支持 null 值和 null
   键；
   2.2 HashTable
   线程安全，低效，不支持 null 值和 null 键；
   2.3 LinkedHashMap
   是 HashMap 的一个子类，保存了记录的插入顺序；
   2.4 SortMap 接口
   TreeMap，能够把它保存的记录根据键排序，默认是键值的升序排序

3. Set接口有两个实现类：
   3.1 HashSet
   底层是由 HashMap 实现，不允许集合中有重复的值，使用该方式时需要重写 equals()和 hash Code()方法；
   3.2 LinkedHashSet
   继承于 HashSet，同时又基于 LinkedHashMap 来进行实现，底层使用的是 LinkedHashMap

5.3 区别

1. List 集合中对象按照索引位置排序，可以有重复对象，允许按照对象在集合中的索引位置检索对象，例如通过list.get(i)方法来获取集合中的元素。
2. Map 中的每一个元素包含一个键和一个值，成对出现，键对象不可以重复，值对象可以重复；
3. Set 集合中的对象不按照特定的方式排序，并且没有重复对象，但它的实现类能对集合中的对象按照特定的方式排序，例如 TreeSet 类，可以按照默认顺序，也可以通过实现 Java.util.Comparator<Type >接口来自定义排序方式。

6. 其他问题

6.1 集合与数组的区别

• 数组是固定长度的数据结构，一旦创建长度就无法改变，而集合是动态长度的数据结构，可以根据需要动态增加或减少元素。
• 数组可以包含基本数据类型和对象，而集合只能包含对象。
• 数组可以直接访问元素，而集合需要通过迭代器或其他方法访问元素。

6.2 哪些集合类是线程安全的

• Vector：就比Arraylist多了个 synchronized （线程安全），因为效率较低，现在已经不太建议使用。
• HashTable：就比hashMap多了个synchronized (线程安全)，不建议使用。
• ConcurrentHashMap：是Java5中支持高并发、高吞吐量的线程安全HashMap实现。它由Segment数组结构和HashEntry数组结构组成。Segment数组在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键-值对数据。一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构；一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素；每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。（推荐使用）

7. 参考链接

List、Map、Set的区别与联系
Java【集合面试题】