底层的数据结构

List

• ArrayList：Object[] 数组。详细可以查看：ArrayList 源码分析。
• Vector：Object[] 数组。
• LinkedList：双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)。详细可以查看：LinkedList 源码分析。

Set

• HashSet(无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素。
• LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。
• TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)。

Queue

• PriorityQueue: Object[] 数组来实现小顶堆。详细可以查看：PriorityQueue 源码分析。
• DelayQueue:PriorityQueue。详细可以查看：DelayQueue 源码分析。
• ArrayDeque: 可扩容动态双向数组。

Map

• HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。详细可以查看：HashMap 源码分析。
• LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。详细可以查看：LinkedHashMap 源码分析
• Hashtable：数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的。
• TreeMap：红黑树（自平衡的排序二叉树）。

LIst

操作的时间复杂度

ArraysList

数组实现的

插入：头部要移动，指定位置要移动所以是线性复杂度

尾部直接插入所以是常量

删除：头部和指定都是线性，

尾部常量级

LinkedList

头部和尾部删除和插入都是常量级

指定位置删除和插入都是线性级

AL和LL区别

线程安全

都不同步

底层

ArrayList是数组，LinkedLIst早期是循环链表，1.7后是双向循环

随机访问

LinkedList不支持

ArrayList实现了随机访问接口

扩容

ArrayList 的扩容机制是动态的，当数组容量不足以容纳新元素时，会进行扩容：

1. 当添加元素到 ArrayList 时，如果当前数组已满，ArrayList 会创建一个更大的数组。
2. 新数组的大小通常是原数组的1.5倍（具体实现可能有所不同）。
3. 然后将原数组中的元素复制到新数组中。
4. 最后，原数组被新数组替换。

速记技巧：阿狸扩容，一点五倍翻。

谐音：阿狸扩容，一点五倍翻（yi dian wu bei fan）。

重点：扩容时数组大小增加到原来的1.5倍，复制原数组元素到新数组是关键步骤。

ArrayList的扩容机制在细节上是这样的：

1. 初始容量：ArrayList 可以指定初始容量，如果没有指定，默认是10。
2. 扩容触发：当添加元素导致现有容量不足时，触发扩容。
3. 扩容因子：扩容时，新容量通常是旧容量的1.5倍，但具体实现可能略有差异。
4. 复制操作：扩容后，需要将旧数组中的所有元素复制到新数组中，这是一个时间成本较高的操作。
5. 内存分配：新数组分配的内存可能比实际需要的多，这有助于减少频繁扩容的需要，但同时也可能导致内存浪费。
6. 性能影响：频繁的扩容操作会影响性能，尤其是在大量元素添加的情况下。

速记技巧：阿狸扩容，倍数翻，复制忙，容量宽。

谐音：阿狸扩容，倍数翻（beishu fan），复制忙（fu zhi mang），容量宽（rong li kuan）。

重点：理解扩容的触发条件、扩容因子、复制操作及其对性能的影响是关键。

Set

HashSet、LinkedHashSet和TreeSet都是Java中的集合实现，用于存储不包含重复元素的集合。以下是它们的异同：

• HashSet：基于哈希表实现，无序，查找速度快，不保证元素的插入顺序。
• LinkedHashSet：继承自HashSet，同时维护了一个双向链表，保持了元素的插入顺序。
• TreeSet：基于红黑树实现，有序，元素自动排序，查找速度相对较慢。

速记技巧：哈希无序（HashSet），链表有序（LinkedHashSet），树形排序（TreeSet）。

谐音：哈希无序（ha xi wu xu），链表有序（lian biao you xu），树形排序（shu xing pai xu）。

重点：根据元素是否需要有序，以及是否关心元素的插入顺序来选择合适的集合类型。无序快速选哈希，有序插入选链表，全序排序选树形。

Queue

Map