对象面试官系列之Java集合--面试官看了都说好
1 Java集合综述
Java 集合，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对
图片来源:https://github.com/CyC2018/CS-Notes
扩展(集合的快速失败机制)：
集合有一个变量modCount来指示集合被修改的次数。在创建Iterator迭代器的时候，会给这个变量赋值给expectedModCount。当集合方法修改集合元素时会修改modCount值，但不会同步修改expectedModCount值；通过Iterator的remove()方法移除元素时，会同时更新expectedModCount 值。当使用迭代器遍历元素操作时，会首先对比两个字段是否相等，如果不相等，则马上抛出异常。
2 ArrayList
扩容：如何不指定初始长度，会先生成一个空数组，然后扩容成10;指定长度，生成长度数组，每次扩容会变成原来的1.5倍，然后新建一个数组进行元素复制。
3 Vector
初始容量10，使用synchronized实现同步，扩容不传参增加为2倍，传参时增加参数
4 CopyOnWriteArrayList
4.1 读写分离
4.2 优缺点
5 LinkedList
双向链表实现
6 Hashset
Hashmap实现，无序，唯一
7 LinkedHashSet
基于linkedHashmapt实现，但是维护了一个双向链表，可实现基于插入顺序或者访问顺序存储
8 TreeSet
红黑树实现，内置比较器按照key值字典序排序，唯一
9 Hashmap
9.1 get流程
2.判断数组元素是否为空，遍历链表调用equals方法找value值
9.2 Put流程
2.hashcode值经过一个扰动函数（高八位和低八位进行异或，加大低位的随机性，减小碰撞概率），然后进行取模，取得下标
3.判断数组元素是否为空，为空直接插入，不为空调用equal方法查找key，key存在就进行覆盖；不存在的话1.7采用头插法插入链表中，1.8采用尾插法插入链表中，如果链表长度超过8而且数组长度大于64，会转化成红黑树（O(logn)）；
4.然后判断当前数组元素个数是否大于数组长度*0.75的负载因子，然后新建一个数组长度2倍的数组，重新计算hash值；1.8的时候会先判断扩容后的hash值新增的位是0还是1，是0的话下标不变，是1的话下标会增加扩容的长度
扩展：
1. 线程不安全1.7扩容时会因为头插***造成循环链表和数据覆盖；1.8采用尾插法并进行hash碰撞检测，多线程下容易造成数据覆盖2. 为什么长度为8变成红黑树，6变成链表2.1 红黑树时间复杂度o(logn)，但是空间复杂度高，时间和空间的均衡
2.2 泊松分布得出链表长度超过8的概率很低3.负载因子为什么是0.753.1 提高空间利用率和减少查询成本的折中
3.2 根据泊松分布，0.75时链表长度超过8的概率很低4.红黑树红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树增加了如下的额外要求：
1、节点是红色或黑色。
2、根是黑色。
3、所有叶子都是黑色（叶子是NIL节点）。
4、每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5、从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
10 Hashtable
扩展：
1.取map所有值
1.1 keyset：将key值存入set集合，然后通过get()方法取value值
1.2 entrySet：存放key和value的键值对
2.Hashtable和Hashmap区别
2.1 Hashmap线程不安全，Hashtable线程安全
2.2 Hashmap允许有一个null key，Hashtable不允许
2.3 Hashmap初始容量为16，每次扩容2倍；Hashtable初始容量为11，每次扩容变成2n+1。Hashmap会将给定容量扩容成2的幂次方
11 ConcurrentHashMap
11.1 jdk1.7实现
一个ConcurrentHashMap里包含一个Segment类数组，Segment类实现ReentrantLock，包括一个HashEntry数组和一个count变量表示HashEntry对象的个数；
put操作时会对当前Segment对象进行加锁；get时因为将count和HashEntry的value设置成volatile，保证了可见性，除非读到了null值才会加锁重读；size操作是通过尝试两次统计count的和，如果有变化给每个Segment加锁进行统计。
11.2 Jdk1.8实现
#高频知识点汇总##春招##面经##Java##学习路径#扩展：
1.扩容触发时间：1.1 添加新元素后，元素个数达到扩容阈值触发扩容。
1.2 调用putAll方法，发现容量不足以容纳所有元素时候触发扩容。
1.3 某个槽内的链表长度达到8，但是数组长度小于64时候触发扩容
2.扩容：
2.1 根据数组的长度和cpu数计算每个线程需要处理的数组的长度，每个线程至少处理16个长度
2.2 单个线程从数组尾部开始进行迁移，和1.8的hashmap一样，根据扩容后的hash值新增的位是0还是1，决定在新的数组的下标不变，还是增加扩容的长度，扩容的时候会用synchronized锁定首节点
2.3 迁移完成的部分，如果有其他线程进行修改操作，会参与扩容，get操作会转发到新数组上；正在迁移的部分，其它线程的get操作会操作原数组，put操作会阻塞；还未迁移的部分操作不受影响
投递字节跳动等公司9个岗位 >