说说 List,Set,Map 三者的区别？三者底层的数据结构？

• List：储存元素是有序的、可重复的。
• Set：储存元素是无序的、不可重复的。
• Map：使用键值对（key-value）储存，key是无序、不可重复的；value是无序、可重复的。

数据结构

List：

• ArrayList：Object[] 数组
• Vector：Object[] 数组
• LinkedList: 双向链表(Jdk1.6之前为循环链表，Jdk1.7取消了循环)

Set：

• HashSet（无序、唯一）：基于HashMap实现，底层采用HashMap保存元素
• LinkedHashSet：是HashSet的子类，内部通过LinkedHashMap实现，
• TreeSet（有序、唯一）：红黑树（自平衡的排序二叉树）

Map：

• HashMap：Jdk1.8之前由数组+链表组成，数组是HashMap的主题，链表是为了解决哈希冲突而存在的（拉链法解决冲突）。Jdk1.8之后，当链表长度大于阈值（默认8）将链表转化红黑树，以减少搜索时间。
• LinkedHashMap：继承自HashMap，底层仍基于拉链式散列结构即由数组和链表或红黑树组成。另外在基础结构之上增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表的相应操作，实现了访问顺序的相关逻辑。
• HashTable：数组+链表组成，数组是HashTable的主体，链表则是为了解决哈希冲突而存在的。
• TreeMap：红黑树(自平衡排序的二叉树)