集合框架
集合框架也可以叫容器。（集合是用于存储数据的容器）
常问的有下面几个
- ArrayList
- LinkList
- HashSet
- TreeSet
- HashMap
List(对付顺序的好帮手)： 存储的元素是有序的、可重复的。Set(注重独一无二的性质): 存储的元素是无序的、不可重复的。Map(用 Key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，“x”代表 key，"y"代表 value，Key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。
# 线程安全的集合
- ConcurrentHashMap（线程安全的map，这个会考一下那个锁升级的过程，指的是 synchronized 关键字）
- CopyOnWriteArrayList（线程安全的list）
- CopyOnWriteArraySet（线程安全的set）
- Vector和HashTable（早期的线程安全集合，不过被弃用了）
参考：Java线程安全的集合详解_长风-CSDN博客_线程安全的集合有哪些 (opens new window)
# HashMap（重点）
# HashMap的底层原理
在JDK1.8之前，我们使用的是位桶+链表实现
1.8之后使用的是位桶+链表+红黑树实现
# Hashmap扩容（1.8以后）
- 当我们的链表长度超过8时，就会把链表转换为红黑树，长度小于6时有红黑树变成链表
- 当链表数组（也叫hash表）的容量超过0.75时（加载因子），那么整个HashMap就会扩大为原来的两倍
- 默认hash表大小为16（为了实现均匀分布）
- 扩容分两部，第一是创建一个新Entry的数组，长度为原来的两倍，然后在遍历原Entry数组，把所有的Entry重新Hash到新数组。（为什么要Rehash？是因为长度扩大以后，Hash的规则也随之改变。）
# 头插法和尾插法
1.8之前使用的是头插法（即每次插入都是在链表的头部插入的），1.8之后使用的是尾插法，为什么？
因为头插法会存在链表成环的问题
# 数据插入流程
往map插入元素的时候首先通过对key hash然后与数组长度-1进行与运算((n-1)&hash)，都是2的次幂所以等同于取模，但是位运算的效率更高。找到数组中的位置之后，如果数组中没有元素直接存入，反之则判断key是否相同，key相同就覆盖，否则就会插入到链表的尾部，如果链表的长度超过8，则会转换成红黑树，最后判断数组长度是否超过默认的长度*负载因子也就是12，超过则进行扩容。
# 其他的一些问题
# hashMap使用红黑树而不使用AVL树
最主要的一点是：在CurrentHashMap中是加锁了的，实际上是读写锁，如果写冲突就会等待， 如果插入时间过长必然等待时间更长，而红黑树相对AVL树他的插入更快！
红黑树和AVL树都是最常用的平衡二叉搜索树，它们的查找、删除、修改都是O(lgn) time
AVL树和红黑树有几点比较和区别： （1）AVL树是更加严格的平衡，因此可以提供更快的查找速度，一般读取查找密集型任务，适用AVL树。 （2）红黑树更适合于插入修改密集型任务。 （3）通常，AVL树的旋转比红黑树的旋转更加难以平衡和调试。
总结： （1）AVL以及红黑树是高度平衡的树数据结构。它们非常相似，真正的区别在于在任何添加/删除操作时完成的旋转操作次数。 （2）两种实现都缩放为a O(lg N)，其中N是叶子的数量，但实际上AVL树在查找密集型任务上更快：利用更好的平衡，树遍历平均更短。另一方面，插入和删除方面，AVL树速度较慢：需要更高的旋转次数才能在修改时正确地重新平衡数据结构。 （3）在AVL树中，从根到任何叶子的最短路径和最长路径之间的差异最多为1。在红黑树中，差异可以是2倍。 （4）两个都给O（log n）查找，但平衡AVL树可能需要O（log n）旋转，而红黑树将需要最多两次旋转使其达到平衡（尽管可能需要检查O（log n）节点以确定旋转的位置）。旋转本身是O（1）操作，因为你只是移动指针。
参考
- 《吊打面试官》系列-HashMap (qq.com) (opens new window)
- Java中HashMap底层实现原理(JDK1.8)源码分析_tuke_tuke的博客-CSDN博客_hashmap底层 (opens new window)
# 为什么红黑树要小于6才转换，而不是8呢
和hashcode碰撞次数的泊松分布有关，主要是为了寻找一种时间和空间的平衡。 红黑树中的TreeNode是链表中的Node所占空间的2倍，虽然红黑树的查找效率为o(logN)，要优于链表的o(N)，但是当链表长度比较小的时候，即使全部遍历，时间复杂度也不会太高。固，要寻找一种时间和空间的平衡，即在链表长度达到一个阈值之后再转换为红黑树。
之所以是8，是因为Java的源码贡献者在进行大量实验发现，hash碰撞发生8次的概率已经降低到了0.00000006，几乎为不可能事件，如果真的碰撞发生了8次，那么这个时候说明由于元素本身和hash函数的原因，此次操作的hash碰撞的可能性非常大了，后序可能还会继续发生hash碰撞。所以，这个时候，就应该将链表转换为红黑树了，也就是为什么链表转红黑树的阈值是8。
最后，红黑树转链表的阈值为6，主要是因为，如果也将该阈值设置于8，那么当hash碰撞在8时，会反生链表和红黑树的不停相互激荡转换，白白浪费资源。
# Hash冲突解决方法
HashMap采用的是链地址法
开放地址法
开放定址法也称为
再散列法，基本思想就是，如果p=H(key)出现冲突时，则以p为基础，再次hash，p1=H(p),如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地址pi。 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次hash，所以只能在删除的节点上做标记，而不能真正删除节点。缺点:容易产生堆积问题;不适合大规模的数据存储;插入时会发生多次冲突的情况;删除时要考虑与要删除元素互相冲突的另一个元素，比较复杂。
再哈希法(双重散列，多重散列)
提供多个不同的hash函数，当
R1=H1(key1)发生冲突时，再计算R2=H2(key1)，直到没有冲突为止。 这样做虽然不易产生堆集，但增加了计算的时间。链地址法(拉链法)
链地址法:将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。HashMap采用的就是链地址法来解决hash冲突。(链表长度大于等于8时转为红黑树)
建立公共溢出区
将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。
# LinkedHashMap
LinkedHashMap 继承自 HashMap，在 HashMap 基础上，通过维护一条双向链表，解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。除此之外，LinkedHashMap 对访问顺序也提供了相关支持。在一些场景下，该特性很有用，比如缓存。具体结构如下：
参考：
LinkedHashMap 源码详细分析（JDK1.8）_慕课手记 (imooc.com) (opens new window)
# List
这个地方问的会少一些
- ArrayList是基于数组实现的，非线程安全，每次扩容为1.5倍，默认大小为10（源码里：DEFAULT_CAPACITY = 10;），扩容时会创建一个型的大数组，然后把之前的内容拷贝到新数组里
- LinkedList是基于双向链表，非线程安全，不需要扩容（因为是基于链表），（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
- ArrayList最大容量不超过Integer的最大值
适用场景
ArrayList适用于频繁查询和获取数据，LinkedList适合频繁地增加或删除数据
# Set
主要考TreeSet和HashSet，Set 注重独一无二的性质,用于存储无序元素， 值不能重复。
- HashSet基于HashMap实现，其实就是把HashMaP的值改成空
- TreeSet基于TreeMap实现
- LinkedHashSet（继承自HashSet，底层是LinkedHashMap HashSet+LinkedHashMap）
- BitSet（位集，底层是long数组，用于替代List）
- CopyOnWriteArraySet（线程安全的，底层是CopyOnWriteArrayList）
参考：java Set学习_冷雨清的博客-CSDN博客 (opens new window)
# ConcurrentHashMap
1.8之前
采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。虽然效率提高了，但是查询遍历的效率还是太低了
1.8之后
采用CAS+Synchronized
参考