集合框架（Collections）

List(ArrayList,LinkedList)

ArrayList：

• 底层是一个动态数组，支持快速随机访问，但插入和删除效率低；
• 对于指定下标的查找，时间复杂度为O(1)，对于指定值的查找，需要遍历数组，时间复杂度为O(n)；
• 初始化时容量为0，当add一个元素后变为10；
• 扩容时，默认扩容为原来的1.5倍。

与Array的区别：

• Array大小是固定的，ArrayList是一个大小可变的动态数组，可以动态的添加或删除元素；
• Array只能存放同样类型的对象，ArrayList可以存储类型不同的对象；
• Array存放的数据类型可以是基本数据类型或者引用数据类型，ArrayList只能存放引用数据类型。

LinkedList:

• 底层是一个双向链表，不支持快速随机访问，但插入和删除元素更方便；
• 查询方式是链式查询，需从头开始，一个个比较，故查询较慢；
• 提供两种插入方式，指定索引位置的插入LinkedList.add(int index,E e)和尾插LinkedList.add(E e)

需要在线程安全的情况下使用List：

1. Vector(较为老土，不推荐)。加了synchronized关键字，线程安全，扩容时默认扩容为原来的2倍
2. Collections.synchronizedList。自动将List方法进行改变，返回一个加锁的List
3. JUC框架下的CopyOnWriteArrayList。适用于读多写少的场景，以空间换时间的思想

Map(HashMap,ConcurrentHashMap,LinkedHashMap)

HashMap：

• 底层是数组+链表(JDK1.7)，数组+单链表/红黑树(JDK1.8)，且数组的长度必须为2的幂次数；
• 数组：支持快速随机访问，查找效率高；
• 链表：解决哈希冲突。两个不同的元素，计算hashcode，取模得到的值相同，即桶号相同，用链表的链式存储结构来解决冲突。
• 单链表–>红黑树：(单链表长度>=8 && hash桶>=64)；
• 红黑树–>单链表：(tree的节点数<=6)；
• 初始化时，数组长度默认为16，threshold(阈值)为0，当add元素后，threshold默认为16，负载因子loadFactory=0.75；
• 扩容时，当已有元素的桶个数>size*loadFactory，且新加入的元素需进入一个新桶（即占用一个空桶）时，进行自动扩容，默认扩容为原来的2倍；
• 添加时，头插法(JDK1.7)(插在头上，然后将整体向下移一个位)，可能产生环形链表，导致死循环，线程不安全。尾插法(JDK1.8)

ConcurrentHashMap：

• 底层是一个分段数组(JDK1.7)，为保证线程安全，加了Segment锁(继承于ReentrantLock)，每个锁管理一部分桶。数组+单链表/红黑树(JDK1.8)，并逐渐放弃分段锁机制，转而使用CAS和synchronized

LinkedHashMap

• 继承于HashMap，具有较高的查询效率
• 在HashMap的基础上维护了一个双向链表