集合

1、List实现方式

底层数据结构	类	实现方式	线程安全性	初始容量	优点	缺点	备注
数组	ArrayList	增加或减少元素时，需要考虑扩容；直接修改源数据。	非线程安全	初始容量：1.6和之前为10。jdk1.7+默认为0，增加一个元素后为10 扩容增量：1.6和之前为原容量的 1.5倍+1一次扩容后是容量为16。1.7和之后是1.5倍也就是15	按索引查找元素快	新增或减少元素需要考虑数组容量问题，数组的扩容与缩容有一定的性能损耗	java.util
链表	LinkedList	双端链表；增加元素时添加到尾节点；删除元素时，删除首节点。	非线程安全	-	新增、删除元素效率高	查找元素稍慢	java.util
数组	CopyOnWriteArrayList	（读操作时无锁，但是写操作有锁的ArrayList）当某个线程要增加或修改List中的元素时，会把列表中的元素Copy一份，然后在新数组中对元素进行修改，最后把新元素赋值给原来的List的。读写分离，空间换时间	线程安全	0	适合于读多写少	内存占用问题	java.util.concurrent
数组	SynchronizedList	包装list，对每一个list的方法，都用synchronized修饰（静态代理的形式）	线程安全	-	优点与其底层的list一样	缺点与其底层的list一样；同时，因为每一个方法都加锁，所以性能稍差	Collections内部类
数组，泛型动态类型顺序表，底层数据存储在一段连续的空间	Vector	方法上都加上了synchronized	线程安全	10（扩容后为原来的一倍，也就是20）	读取更改效率高	新增减少效率低	java.util

1.2 for循环中容器不能直接remove的原因

• 不能直接remove，要使用迭代器iterator，不然==modCount != expectedModCount会报ConcurrentModificationException
• foreach底层还是使用了迭代器遍历。

fori下标方式循环（**可以**）：底层使用的是ArrayList.remove(index)==方法。

List<String> list = new ArrayList<>();
list.add("1");
for(int i = 0; i < list.size(); i++){
    list.remove(i);
}

foreach循环（**不可以**）：

源码会去调用 fastRemove(index)，里面有个modCount++字段，当进行循环时候使用的是迭代器的next()获取，而next()方法中有个方法checkForComodification进行了校验，里面判断实际操作modCount(案例中值为4，因为操作了一次删除)和预期操作expectedModCount(预期值为3)是否相等，不相等责抛出ConcurrentModificationException

for(String a : list){
    if ("1".equals(a)) {
        // 因为无法获取下标，所以用数组元素内容删除，调用的是ArrayList.remove(object)
        list.remove(a);
    }
}

Iterator方式（**可以**）：

1. Iterator 是工作在一个独立的线程中，并且拥有一个 mutex 锁
2. Iterator 被创建之后会建立一个指向原来对象的单链索引表
3. 当创建完成指向某个集合或者容器的Iterator对象时，这是的指针其实指向的是第一个元素的上方，即指向一个空
4. 当调用hasNext方法的时候，只是判断下一个元素的有无，并不移动指针
5. 当调用next方法的时候，向下移动指针，并且返回指针指向的元素，如果指针指向的内存中没有元素，会报异 常
6. remove方法删除的元素是指针指向的元素。如果当前指针指向的内存中没有元素，那么会抛出异常。

List<String> list = new ArrayList<>();
list.add("1");
Iterator iterator = list.iterator();
while(iterator.hasNext()){
    if ("1".equals(iterator.next())) {
        iterator.remove();
    }
}

Set
Set和List过程和结果一样

• ArrayList继承AbstractCollection,AbstractCollection实现Collection
• HashSet继承AbstractSet，AbstractSet继承AbstractCollection，AbstractCollection实现Collection
  他们最终都继承自Collection的迭代器itreator。

Map

Map其实和List是同样原理(都是modCount != expectedModCount)。keyset遍历

2、Set实现方式

类	数据结构	线程安全性	是否有序	初始容量	容量因子	是否可以为null
HashSet	在 JDK 1.7 之前，哈希表，它是一个以链表为元素的数组。 在 JDK 1.8 之后，链表数组 + 二叉树，当链表长度大于 8 时，就将量表换成二叉树。 数组+链表（底层就是HashMap）	非线程安全	无序	16	0.75	可以有一个Null
TreeSet	红黑树（底层就是TreeMap）	非线程安全	有序（自然排序和定制排序）	-	-	不能为Null
LinkedHashSet	链表和哈希表	非线程安全	以插入顺序存储	-	-	可以有一个Null
CopyOnWriteArraySet	基于CopyOnWriteArrayList（add时调用的是addIfAbsent-若没有则增加方法）	线程安全	无序	0	-	可以有一个Null

3、Map

1、实现方式

类	并发性	线程安全	有序性	底层数据结构	初始容量	负载因子	实例化方式	一致性	k/v是否可为null
HashMap	不支持	不安全	无序	数组+链表/红黑树（1.8才有）。链表转红黑树的阈值是8。红黑树转链表是6。	16一次扩容后是容量为32（2的5次方）	0.75	懒加载	-	k/v可为null
LinkedHashMap	不支持	不安全	有序（插入序或者访问序）	数组+单向链表+双向链表	-	-	-	-	k/v可为null
TreeMap	不支持	不安全	自然序（左小右大）	红黑树	-	-	-	-	仅v能为null
ThreadLocalMap	不支持	不是绝对的线程安全	无序	数组	16	0.75	懒加载	-	仅v能为null
HashTable	支持	安全synchronized实现（锁住全部数据）	无序	数组加链表	11（2n+1，下一次为23）	0.75	初始化创建	强一致性	均不能为null
ConcurrentHashMap(1.7)	支持	安全	无序	分段锁+数组+链表	16	0.75	懒加载	强一致性	均不能为null
ConcurrentHashMap(1.8)	支持	安全	无序	数组+链表/红黑树+锁分段（通过Segment数组+分段锁实现线程安全：每一把锁用于锁容器其中一部分数据）	16	0.75	懒加载	强一致性	均不能为null
ConcurrentSkipListMap	支持	安全	自然序(左小右大)	跳跃表	-	-	-	强一致性	均不能为null

为什么java1.8要对hashMap的数据结构中加入树呢？

• 提高查找效率。此前hashMap中的数据采取【数组+链表】的存储结构，桶数组会将通过hash算法将key值计算得来的相同哈希值数据存储在对应的链表中，而随着链表的数据增多，在检索结点方面，性能会下降，因为链表虽然插入删除的时间复杂度是O(1)，但它遍历的时间复杂度达到了O(n)。为了使得时间复杂度更优，因此引入了树形结构，因为树查找快啊！

树形结构，有二叉查找树、平衡二叉树，为啥还需要红黑树？

二叉查找树的特点：左结点 < 根结点 < 右结点，时间复杂度为O(log n)

极端情况问题：此时的二叉查找树已经近似退化为一条链表，这样的二叉查找树的查找时间复杂度顿时变成了 O(n)

解决方式：可以引入平衡二叉树，平衡二叉树的左右子树高度差为1，但是每次插入或删除的时候都破坏的平衡二叉树高度都为差为1都规则。

• 二叉查找树是为了解决链表查找的性能问题，平衡二叉树是为了解决二叉查找树退化为链表的情况，而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。
• 红黑树相比平衡二叉树，在检索的时候效率其实差不多，都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像平衡二叉树树一样追求绝对的平衡，他允许局部很少的不完全平衡，这样对于效率影响不大，但省去了很多没有必要的调平衡操作，平衡二叉树树调平衡有时候代价较大，所以效率不如红黑树。

2、HashMap扩容过程

hashmap长度为什么是2的n次方？

​ HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法；
这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)，
hash%length==hash&(length-1)的前提是length是2的n次方；
为什么这样能均匀分布减少碰撞呢？2的n次方实际就是1后面n个0，2的n次方-1 实际就是n个1；
例如长度为9时候，3&(9-1)=0 2&(9-1)=0 ，都在0上，碰撞了；
例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞；

阿里面试官最喜欢问的21个HashMap面试题

区别	JDK1.7	JDK1.8
JDK1.7	数组 + 链表	数组 + 链表 + 红黑树
存储结构初始化方式	单独函数：inflateTable()	直接集成到了扩容函数resize()中
hash值计算方式	扰动处理 = 9次扰动 = 4次位运算 + 5次异或运算	扰动处理 = 2次扰动 = 1次位运算 + 1次异或运算
存放数据的规则	无冲突时，存放数组；冲突时，存放链表	无冲突时，存放数组；冲突 & 链表长度 < 8 ：存放单链表；冲突 & 链表长度 > 8 & 数组长度 < 64 : 扩容；冲突 & 链表长度 > 8 & 数组长度 > 64：树化并存放红黑树
插入数据方式	头插法（先将原位置的数据移到后1位，再插入数据到该位置）	尾插法（直接插入到链表尾部/红黑树）
扩容后存储位置的计算方式	全部按照原来方法进行计算（即hashCode ->> 扰动函数 ->> (h&length-1)）	按照扩容后的规律计算（即扩容后的位置=原位置 or 原位置 + 旧容量）

• 调用put方法时：根据key的hashCode，计算出将key放入数组的index下标，index= (数组长度 - 1) & hashCode

3、为什么ConcurrentHashMap是线程安全的？

1. 为什么ConcurrentHashMap是线程安全的
   JDK1.7中，ConcurrentHashMap使用的锁分段技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

2. 那说说JDK1.7中Segment的原理
   刚刚说的一段一段就是指Segment，它继承了ReentrantLock，具备锁和释放锁的功能。ConcurrentHashMap只有16个Segment，并且不会扩容，最多可以支持16个线程并发写。

3. JDK1.8的ConcurrentHashMap怎么实现线程安全的
   JDK1.8放弃了锁分段的做法，采用CAS和synchronized方式处理并发。以put操作为例，CAS方式确定key的数组下标，synchronized保证链表节点的同步效果。

4. JDK1.8的做法有什么好处呢

   • 减少内存开销
     假设使用可重入锁，那么每个节点都需要继承AQS，但并不是每个节点都需要同步支持，只有链表的头节点（红黑树的根节点）需要同步，这无疑消耗巨大内存。
   • 获得JVM的支持
     可重入锁毕竟是API级别的，后续的性能优化空间很小。synchronized则是JVM直接支持的，JVM能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。使得synchronized能够随着JDK版本的升级而不改动代码的前提下获得性能上的提升。

5. HashTable也是线程安全的，为什么不推荐使用HashTable呢
   HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。因为多个线程访问HashTable的同步方法时，可能会进入阻塞或轮询状态。如线程1使用put进行添加元素，线程2不但不能使用put方法添加元素，并且也不能使用get方法来获取元素，所以竞争越激烈效率越低。

4、Map性能比较

类	get	put	remove
HashMap	>=O(1)	O(1)~O(log n)	O(1)~O(log n)
LinkedHashMap	>=O(1)	O(1)~O(log n)	O(1)~O(log n)
TreeMap	O(log n)	O(log n)	O(log n)
ThreadLocalMap	O(1)~O(n)	O(1)~O(n)	O(1)~O(n)
HashTable	>=O(1)	O(1)~O(n)	O(1)~O(n)
ConcurrentHashMap(1.7)	>=O(1)	O(1)~O(log n)	O(1)~O(log n)
ConcurrentHashMap(1.8)	>=O(1)	O(1)~O(log n)	O(1)~O(log n)
ConcurrentSkipListMap	O(log n)	O(log n)	O(log n)

集合框图