一.继承关系

1.1 基于Collection

Iterable接口： 迭代器（负责迭代元素，用于遍历元素）
Collection接口： 集合（常用的方法有添加，全部添加，删除，清空集合，是否存在，集合个数等）
List接口： 列表 （list提供比数组更丰富的API，有序，可重复，）
Queue接口： 队列（遵循先进先出原则，第一个进队列的元素，必定第一个出队列）
Set接口： Set集合（不允许出现重复元素，并且无序的集合）

1.2 不属于Collection

Map接口： 散列表（使用K-V（键值对）存储的一种数据结构，Key 是无序的、不可重复的，value 是无序的、可重复的）不属于Collection接口

二.List

2.1 ArrayList

底层实现： Objcet[] (动态数组)

扩容方式： 当原本ArrayList的底层的数组容量不足以存放新插入的元素或一组元素时，会触发扩容机制，调用的本地C方法。

线程安全性： 不安全
补充：如果要安全的调用ArrayList，使用Collections.synchronizedList()方法。其他API与原先无异

List<Map<String,Object>> data=Collections.synchronizedList(new ArrayList<Map<String,Object>>());

使用场景：
适合于进行大量的随机访问的情况下使用（说人话就是可以直接根据下标取值），时间复杂度O(1)

插入与删除： 默认追加到尾部，时间复杂度O(1)。追加或删除指定位置元素，时间复杂度 O(n-i)

补充：clear()方法可以清空当前List且不改动已分配的空间

2.2 LinkedList

底层实现： 双向链表

扩容方式： 正常链表的新增节点

线程安全性： 不安全
补充：如果要安全的调用，同上。其他API与原先无异

List<Map<String,Object>> data=Collections.synchronizedList(new LinkedList<Map<String,Object>>());

使用场景：
适合频繁的插入或者删除操作，较少的随机访问（说人话就是可以直接根据下标取值），获取元素的时间复杂度O(n)。

插入与删除： 默认追加到尾部，时间复杂度约等于O(1)（为啥不等于一，因为还要创建节点然后追加，而ArrayList直接分配好空间直接赋值就行）。追加或删除指定位置元素，时间复杂度近似 O(n)。

内存空间占用：
ArrayList 的空间浪费体现在 list 列表的结尾会预留一定的容量空间。
LinkedList 的空间花费主要体现在每一个元素都（存放直接后继和直接前驱以及数据） 需要消耗比 ArrayList 更多的空间。

2.3 CopyOnWriteArrayList（不常用）

底层实现： Objcet[] (动态数组)

线程安全性： 安全
补充：如何保证安全性，
读：未加锁。
写：添加或修改时元素时 使用lock()进行加锁并复制 一份 副本，然后添加或修改，然后使用新副本。

使用场景：
适合于进行大量的随机访问的情况下使用（说人话就是可以直接根据下标取值）以及读多写少的情况，不需要强一致性（不能保证即时一致性），时间复杂度O(1)。

内存空间占用：
每一次写都需要复制一份副本。严重浪费内存。

2.4 Vector（历史遗留，古早时代的类）

底层实现： Objcet[] (动态数组)

线程安全性： 安全
补充：如何保证安全性，方法全部加了 synchronized 关键字（恶臭的历史残留。进了用这玩意的公司赶紧跑路吧，代码一定是屎山）

三.Set

3.1 HashSet

底层实现： HashMap(使用了Key部分)

线程安全性： 不安全

使用场景： 无序，数据去重
允许插入Null值

3.2 TreeSet

底层实现： TreeMap，红黑树（自平衡二叉查找树）

线程安全性： 不安全

使用场景： 有序（自然排序，key的开头第一个字符的顺序a-z，或者数字的大小0-9）或自定义排序，数据去重
允许插入Null值

注意：要安全调用非线程安全的Set。调用Collections.synchronizedSet()

四.Map

4.1 HashMap

底层实现： 哈希表（又称散列表，使用杂凑算法），当链表（存放相同Hash值的Value）长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64（存Key），那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

线程安全性： 不安全

扩容机制：
源码规定了默认扩容加载因子为0.75

面试官：为什么是0.75？
如果是0.5，就是说哈希表填到一半就开始扩容了，这样会导致扩容频繁，并且空间利用率比较低。 如果是1，就是说哈希表完全填满才开始扩容，这样虽然空间利用提高了，但是哈希冲突机会却大了。
负载因子0.75就是冲突的机会 与空间利用率权衡的最后体现，也是实验的经验值。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

使用场景： 需要根据键的hashCode值进行存储数据。无序，获取元素的时间复杂度限制为O(1)的时候。
Key与Value可为null

内存空间占用：

① 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
面试官为什么是16？
如果太小，4或者8，扩容比较频繁；如果太大，32或者64甚至太大，又占用内存空间。
位运算更快，不需十进制和二进制相互转换。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

② 创建时如果给定了容量初始值 HashMap 会将其扩充为 2 的幂次方大小，也就是说 HashMap 总是使用 2 的幂作为哈希表的大小。

简单的杂凑算法演示： 设对7求膜，
新增key：6 ，value："随便"

6%7=6

新增key：7 ，value："第二次"

7%7=0

解决Hash冲突： 拉链法（以链表的形式存放相同Hash值的Value），上文的红黑树也可。但是拉链法较简单。

4.2 TreeMap

底层实现： 红黑树

线程安全性： 不安全

使用场景： 有序（自然排序，key的开头第一个字符的顺序a-z，或者数字的大小0-9）或自定义排序。
Key与Value可为null

注意：要安全调用非线程安全的Map。调用Collections.synchronizedMap()

4.3 ConcurrentHashMap（建议使用）

底层实现： 数组+链表/红黑二叉树(JDK1.8)在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）

线程安全性： 安全

保证线程安全的方法：用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。

效率问题：
synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

4.4 Hashtabel（古早的线程安全类）

如何保证安全性，方法全部加了 synchronized 关键字（恶臭的历史残留。进了用这玩意的公司赶紧跑路吧，代码一定是屎山）

资料参考

JavaGuide：https://snailclimb.gitee.io/javaguide
CSDN：https://blog.csdn.net