集合类
上述集合类都是线程不安全的集合类，若要使其线程安全，使用Collections提供的synchronizedXxx()方法将其包装
详细使用https://www.jianshu.com/p/17adcb394104中前半部分
HashMap
怎么实现线程安全
1.直接使用Hashtable类(性能会降低)
2.直接使用ConcurrentHashMap(没有全局锁，性能高)
3.使用Collections中的synchronizedXxx()将其包装为线程安全Map
怎么解决哈希冲突
链表长度超过阈值 链表->红黑树
链表长度小于阈值 红黑树->链表
ArrayList和LinkedList区别
1.ArrayList实现基于数组，因此随机访问快，插入删除慢，占内存相对后者小
2.LinkedList实现基于链表，因此随机访问慢，插入删除快，占内存相对较大
TreeSet和HashSet区别
1.HashSet中元素可为null，不保证元素排列，采用哈希表实现
2.TreeSet中元素不能为null，元素自然或定制顺序排列，采用红黑树实现
HashMap和HashTable区别
1.Hashtable是一个线程安全的Map实现，但HashMap是线程不安全的实现，所
以HashMap比Hashtable的性能高一点。
2.Hashtable不允许使用null作为key和value，如果试图把null值放进Hashtable中，将会引发空指针异常，但HashMap可以使用null作为key或value。
Map接口的实现类
HashMap：优先使用，性能最好，线程非安全，不保证排序
LinkedHashMap：需要按插入顺序排序
TreeMap：需要将key按自然顺序排序甚至自定义排序序列
ConcurrentHashMap：线程安全，不保证排序
Map和Set区别
Set代表无序的，元素不可重复的集合
Map代表具有映射关系(key-value)的集合，其所有的key是一个Set集合，key无序且不重复
HashMap的底层实现原理
基于hash算法，通过put和get方法存储和获取对象
- 存储对象时，将
K/V传给put方法，它调用K的hashCode计算hash从而得到bucket位置。
之后HsahMap会根据当前bucket的占用情况自动调整容量。 - 获取对象时，将
K传给get，它调用K的hashCode计算hash从而得到bucket位置。
进一步调用equals()方法确定键值对
Map put的过程
put时采用分段锁/CAS的加锁机制
- 首次扩容：先判断数组是否为空，若数组为空则进行第一次扩容（resize）；
- 计算索引：通过hash算法，计算键值对在数组中的索引；
- 插入数据：
如果当前位置元素为空，则直接插入数据；
如果当前位置元素非空，且key已存在，则直接覆盖其value；
如果当前位置元素非空，且key不存在，则将数据链到链表末端；
若链表长度达到8，则将链表转换成红黑树，并将数据插入树中； - 再次扩容：如果数组中元素个数（size）超过
threshold，则再次进行扩容操作。
2021-04-15_103920.png
JDK7和JDK8HashMap的区别
- JDK7：
是基于数组+链表来实现的，它的底层维护一个Entry数组。
计算的hashCode将对应的KV键值对存储到数组中，
发生hashCode冲突，将该KV键值对放到对应的已有元素的后面，
此时便形成了一个链表式的存储结构。
(可频繁发生冲突时会导致链表过于冗长) - JDK8：
基于数组+链表+红黑树来实现的，它的底层维护一个Node数组。
链表存储的数据个数大于等于8的时候，不再采用链表存储，而采用了红黑树存储
结构。
这么做主要是在查询的时间复杂度上进行优化，链表为O(N)，而红黑树一直是O(logN)
JDK8通过链表和红黑树的不断转换，来解决哈希冲突问题
HashSet的底层结构
HashSet是基于HashMap实现的(采用Hash表实现)
默认构造函数是构建一个初始容量为16，负载因子为0.75的HashMap
封装了一个HashMap来存储所有的集合元素
所有放入HashSet的集合元素实际上由HashMap的key来保存
HashMap的value则存储一个PRESENT，是一个静态Object对象
红黑树
自平衡二叉查找树
