List, Set, Queue, Map 四者的区别？
List (对付顺序的好帮⼿): 存储的元素是有序的、可重复的。
Set (注重独⼀⽆⼆的性质): 存储的元素是⽆序的、不可重复的。
Queue (实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
Map (⽤ key 来搜索的专家): 使⽤键值对（key-value）存储，类似于数学上的函数 y=f(x)，“x” 代表 key，“y” 代表 value，key 是⽆序的、不可重复的，value 是⽆序的、可重复的，每个键最 多映射到⼀个值。
集合框架底层数据结构总结
List
ArrayList ： Object[] 数组
Vector ： Object[] 数组
LinkedList ： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)
Set
HashSet (⽆序，唯⼀): 基于 HashMap 实现的，底层采⽤ HashMap 来保存元素
LinkedHashSet : LinkedHashSet 是 HashSet 的⼦类，并且其内部是通过 LinkedHashMap 来实 现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现⼀样，不过还 是有⼀点点区别的
TreeSet (有序，唯⼀): 红⿊树(⾃平衡的排序⼆叉树)
- Queue
- PriorityQueue : Object[] 数组来实现⼆叉堆
- ArrayQueue : Object[] 数组 + 双指针
Map
HashMap ： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突⽽存在的（“拉链法”解决冲突）。
JDK1.8 以后在解决哈希冲突时有了较⼤的变化，当链表⻓度⼤于阈值（默认为 8）（将链表转换成红⿊树前会判断，如果当前数组的⻓度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树）时，将链表转化为红⿊树，以减少搜索时间。（数组长度大于64且该数组下的链表长度大于8 才转红黑树）
LinkedHashMap ： LinkedHashMap 继承⾃ HashMap ，所以它的底层仍然是基于拉链式散列 结构即由数组和链表或红⿊树组成。另外， LinkedHashMap 在上⾯结构的基础上，增加了⼀条 双向链表，使得上⾯的结构可以保持键值对的插⼊顺序。同时通过对链表进⾏相应的操作，实现 了访问顺序相关逻辑。
详细可以查看：LinkedHashMap 源码详细分析（JDK1.8）_慕课手记
Hashtable ： 数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突⽽存在的
TreeMap ： 红⿊树（⾃平衡的排序⼆叉树）
ArrayList 和 Vector 的区别
- ArrayList 是 List 的主要实现类，底层使⽤ Object[ ] 存储，适⽤于频繁的查找⼯作，线程不安全 ；
- Vector 是 List 的古⽼实现类，底层使⽤ Object[ ] 存储，线程安全的 。
ArrayList 与 LinkedList 区别
是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
底层数据结构： ArrayList 底层使⽤的是 Object 数组； LinkedList 底层使⽤的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区 别，下⾯有介绍到！）
插⼊和删除是否受元素位置的影响：
ArrayList 采⽤数组存储，所以插⼊和删除元素的时间复杂度受元素位置的影响。 ⽐如： 执⾏ add(E e) ⽅法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种 情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插⼊和删除元素的话（ add(int index, E element) ）时间复杂度就为 O(n-i)。因为在进⾏上述操作的时候集合中第 i 和第 i 个元素之 后的(n-i)个元素都要执⾏向后位/向前移⼀位的操作。
LinkedList 采⽤链表存储，所以，如果是在头尾插⼊或者删除元素不受元素位置的影响 （ add(E e) 、 addFirst(E e) 、 addLast(E e) 、 removeFirst() 、 removeLast() ），时间复杂 度为 O(1)，如果是要在指定位置 i 插⼊和删除元素的话（ add(int index, E element) ， remove(Object o) ）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插⼊。
是否⽀持快速随机访问： LinkedList 不⽀持⾼效的随机元素访问，⽽ ArrayList ⽀持。快速随 机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) ⽅法)。
内存空间占⽤： ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留⼀定的容量空间， ⽽ LinkedList 的空间花费则体现在它的每⼀个元素都需要消耗⽐ ArrayList 更多的空间（因为要 存放直接后继和直接前驱以及数据）。
我们在项⽬中⼀般是不会使⽤到 LinkedList 的，需要⽤到 LinkedList 的场景⼏乎都可以使⽤ ArrayList 来代替，并且，性能通常会更好！就连 LinkedList 的作者约书亚 · 布洛克（Josh Bloch）⾃⼰都说从来不会使⽤ LinkedList 。
补充内容:RandomAccess 接⼝
public interface RandomAccess { }
查看源码我们发现实际上 RandomAccess 接⼝中什么都没有定义。所以，在我看来 RandomAccess 接⼝不过是⼀个标识罢了。标识什么？ 标识实现这个接⼝的类具有随机访问功能。
在 binarySearch() ⽅法中，它要判断传⼊的 list 是否 RandomAccess 的实例，如果是，调⽤
indexedBinarySearch() ⽅法，如果不是，那么调⽤ iteratorBinarySearch() ⽅法
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) { if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key); else return Collections.iteratorBinarySearch(list, key); }
ArrayList 实现了 RandomAccess 接⼝， ⽽ LinkedList 没有实现。为什么呢？
我觉得还是和底层数据结构有关！ ArrayList 底层是数组，⽽ LinkedList 底层是链表。数组天然⽀持随机访问，时间 复杂度为 O(1)，所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间 复杂度为 O(n)，所以不⽀持快速随机访问。， ArrayList 实现了 RandomAccess 接⼝，就表明了他 具有快速随机访问功能。 RandomAccess 接⼝只是标识，并不是说 ArrayList 实现 RandomAccess 接⼝才具有快速随机访问功能的！
ArrayList 的扩容机制
comparable 和 Comparator 的区别
comparable 接⼝实际上是出⾃ java.lang 包 它有⼀个 compareTo(Object obj) ⽅法⽤来排序
comparator 接⼝实际上是出⾃ java.util 包它有⼀个 compare(Object obj1, Object obj2) ⽅法⽤来排序
详见
比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同
- HashSet 、 LinkedHashSet 和 TreeSet 都是 Set 接⼝的实现类，都能保证元素唯⼀，并且都 不是线程安全的。
- HashSet 、 LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。 HashSet 的底层数 据结构是哈希表（基于 HashMap 实现）。 LinkedHashSet 的底层数据结构是链表和哈希表， 元素的插⼊和取出顺序满⾜ FIFO。 TreeSet 底层数据结构是红⿊树，元素是有序的，排序的⽅ 式有⾃然排序和定制排序。
底层数据结构不同⼜导致这三者的应⽤场景不同。 HashSet ⽤于不需要保证元素插⼊和取出顺 序的场景， LinkedHashSet ⽤于保证元素的插⼊和取出顺序满⾜ FIFO 的场景， TreeSet ⽤于 ⽀持对元素⾃定义排序规则的场景。
