List，Set，Map三者的区别？
Java 容器分为 Collection 和 Map 两大接口，Collection集合的子接口有Set、List、Queue三种子接口。我们比较常用的是Set、List。
Collection集合主要有List和Set两大接口：
- List：基于数组、链表两种结构实现，一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null元素。常用的实现类有 ArrayList、LinkedList 和 Vector。
- Set：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet（后两个可以实现有序）。
Map是一个键值对集合，存储键、值之间的映射。
- Map：Key无序，唯一；value 不要求有序，允许重复。Map没有继承于Collection接口，从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。Map 的常用实现类：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap
- Set和Map有基于哈希存储和红黑树实现。
List，Set，Map和Queue的底层数据结构
（1）Set
TreeSet：通过 TreeMap 实现的，添加元素到集合时按照比较规则将其插入合适的位置，保证插入后的集合仍然有序。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。
HashSet：通过 HashMap 实现，HashMap 的 Key 即 HashSet 存储的元素，所有 Key 都使用相同的 Value ，一个名为 PRESENT 的 Object 类型常量。使用 Key 保证元素唯一性，但不保证有序性。由于 HashSet 是 HashMap 实现的，因此线程不安全。
LinkedHashSet：继承自 HashSet，通过 LinkedHashMap 实现，使用双向链表维护元素插入顺序。
（2） List
ArrayList：基于动态数组实现，支持随机访问。
Vector：和 ArrayList 类似，但它是线程安全的。
LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列（刷题常用）。
（3） Queue
LinkedList：可以用它来实现双向队列。
PriorityQueue：基于堆结构实现，可以用它来实现优先队列。
（4）Map
TreeMap：基于红黑树实现。
HashMap：JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
HashTable：和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程同时写入 HashTable 不会导致数据不一致。它是遗留类，不应该去使用它，而是使用 ConcurrentHashMap 来支持线程安全，ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。LinkedHashMap使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。
comparable和comparator的区别？
- comparable接口实际上是出自java.lang包，它有一个 compareTo(Object obj)方法用来排序；comparable是一种内部自然排序，只能有一种定义。接口里只定义了这一个方法,代表了:传入一个对象,将对象和元素自身进行比较,如果元素自身大,返回1,相等返回0,元素自身小于参数则返回-1.
private static class Student implements Comparable { int id; String name; int age; @Override public int compareTo(Object o) { return this.id - ((Student) o).id; } }
- comparator接口实际上是出自 java.util 包，它有一个compare(Object obj1, Object obj2)方法用来排序；comparator是一种外部比较器，可以定义多个不同的比较器，按需取用。功能是对传入的两个元素进行大小的比较,并且返回结果。
private static class StudentCom1 implements Comparator<Student>{ @Override public int compare(Student o1, Student o2) { return o1.id - o2.id; } }
那么问题来了,都有Comparable了,还要Comparator干什么?
设想一个场景,我们定义了一个学生类,如上面代码所示,那么学生可以按着id的大小进行排序.
然后现在有两个使用的地方,第一个是考试,需要学生按照id排序.第二个是学生统计,需要学生按照年龄进行排序.
怎么实现两种完全不同的排序方式呢?或者更极端一点,一会需要按照id增序,一会需要按照id降序呢?改源代码肯定是不科学的.
这个时候就可以采用以下方案:
- 学生实现自然排序,即最通用的那种排序方式,比如按照id增序，在需要默认排序的情况下,直接调用学生的
comparTo即可. - 实现几个不同的比较器,比如
运动会比较器,吃饭比较器等等，在特定情景下,调用集合类的排序方法,传入一个想要的比较器即可.
总结：一般我们需要对一个集合使用自定义排序时，我们就要重写compareTo方法或compare方法，当我们需要对某一个集合实现两种排序方式，比如一个song对象中的歌名和歌手名分别采用一种排序方法的话，我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌星名排序，第二种代表我们只能使用两个参数版的Collections.sort()。
TreeMap和TreeSet在排序时如何比较元素？Collections 工具类中的sort()方法如何比较元素？
- TreeSet 要求存放的对象所属的类必须实现 Comparable 接口（说明该类是可被排序的），该接口提供了比较元素的 compareTo()方法，当插入元素时会回调该方法比较元素的大小。
- TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进行排序。
Collections 工具类的 sort 方法有两种重载的形式：
- 第一种要求传入的待排序容器中存放的对象要实现 Comparable 接口以实现元素的比较；
- 第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator 接口的子类型（需要重写 compare 方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java 中对函数式编程的支持）。
有没有有顺序的Map实现类，如果有，他们是怎么实现有序的？
- Hashmap和Hashtable 都不是有序的。
- TreeMap和LinkedHashmap都是有序的。（TreeMap默认是key升序，LinkedHashmap默认是数据插入顺序）
TreeMap是基于比较器Comparator来实现有序的。LinkedHashmap是基于链表来实现数据插入有序的。
我们应该如何选用集合?
- 主要根据集合的特点来选用，比如我们需要根据键值获取到元素值时就选⽤Map接口下的集合，需要排序时选择TreeMap/LinkedHashmap,不需要排序时就选择HashMap,需要保证线程安全就选⽤ConcurrentHashMap.
- 当我们只需要存放元素值时，就选择实现Collection接口集合，需要保证元素唯⼀时选择实现Set接口的集合，⽐如TreeSet或HashSet，不需要就选择实现List接口的比如ArrayList或LinkedList，然后再根据实现这些接⼝的集合的特点来选⽤。
综上所述，选用集合，首先是我们具体的使用场景：只是存值，还是建立一种映射，便于查询。其次，考虑集合的元素有序性、元素的唯一性和线程安全性等问题。
拓展
（1）Collections.sort和Arrays.sort的实现原理
Collections.sort方法底层就是调用的Array.sort方法（中间调用了list.sort，然后list.sort调用了Array.sort方法）
因此，Arrays的sort方法底层就是：
- legacyMergeSort(a)，归并排序，
- ComparableTimSort.sort()：即Timsort排序。Timsort排序是结合了合并排序（merge.sort）和插入排序（insertion sort）而得出的排序方法；ps：当数组长度小于某个值，采用的是二分插入排序算法，插入然后合并。
（2）poll()方法和 remove()方法的区别？
Queue队列中，poll() 和 remove() 都是从队列中取出一个元素，在队列元素为空的情况下：
- remove() 方法会抛出异常，
- poll() 方法只会返回 null 。
（3）HashMap，HashTable，ConcurrentHash的共同点和区别
- 底层都是数组+链表+红黑树
- HashMap可以存储null键和null值，另外两个不能存储null键值
- 。。。
HashMap,LinkedHashMap,TreeMap的区别
- Map主要用于存储健值对，根据键得到值，因此不允许键重复(重复了覆盖了),但允许值重复。Hashmap 是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的。HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。
- Hashtable与 HashMap类似,它继承自Dictionary类，不同的是:它不允许记录的键或者值为空;它支持线程的同步，即任一时刻只有一个线程能写Hashtable,因此也导致了 Hashtable在写入时会比较慢。
- LinkedHashMap保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。
- TreeMap实现SortMap接口，能够把它保存的记录根据键排序,默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。
使用场景：
- 一般情况下，我们用的最多的是HashMap,HashMap里面存入的键值对在取出的时候是随机的,它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。在Map 中插入、删除和定位元素，HashMap 是最好的选择。
- TreeMap取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。
- LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现,它还可以按读取顺序来排列，像连接池中可以应用。
总结：
- HashSet是通过HashMap实现的,TreeSet是通过TreeMap实现的,只不过Set用的只是Map的key
- Map的key和Set都有一个共同的特性就是集合的唯一性.TreeMap更是多了一个排序的功能.
- hashCode和equals()是HashMap用的, 因为无需排序所以只需要关注定位和唯一性即可.
a. hashCode是用来计算hash值的,hash值是用来确定hash表索引的.
b. hash表中的一个索引处存放的是一张链表, 所以还要通过equal方法循环比较链上的每一个对象才可以真正定位到键值对应的Entry.
c. put时,如果hash表中没定位到,就在链表前加一个Entry,如果定位到了,则更换Entry中的value,并返回旧value - 由于TreeMap需要排序,所以需要一个Comparator为键值进行大小比较.当然也是用Comparator定位的.
a. Comparator可以在创建TreeMap时指定
b. 如果创建时没有确定,那么就会使用key.compareTo()方法,这就要求key必须实现Comparable接口.
c. TreeMap是使用Tree数据结构实现的,所以使用compare接口就可以完成定位了.
