JAVA集合基础高频面试点（二）

周刘盛

java集合不用说了，不仅在实际业务代码中用到非常多，也是面试的高频考点，必须要掌握，最好把源码实现翻完。
java集合包含两大类：Collections和Map。Collection存储的是单个值，Map存储的是键值对。
还有java并发里面的集合类也在这里一并说明。
一.Collections



1.List

• ArrayList
  

ArrayList底层存放数据的容器是数组，数组长度是不可更改的，因此往ArrayList里面添加元素的时候，如果数组的容量不够，就需要给数组扩容。这是就需要复制数组，会造成很大的内存开销。

• Vector
  

vector的底层和ArrayList是一样的，只不过在更新方法上都加了Synchronized关键字，因此是线程安全的。
Vector和ArrayList的区别？
  -Vector是线程安全的，ArrayList不是。
     -Vector在容量满的时候扩容到原来的两倍，ArrayList扩容到之前的1.5倍。

• LinkedList
  

LinkedList底层是基于双向列表实现的，可以实现快速插入和删除，但是只能顺序访问。
2.Queue

• LinkedList
  
• PriorityQueue
  
• ArrayDeque
  

3.Set

• HashSet: hashSet就是基于hashMap封装而来的，不同的是hashSet插入的时候遇到哈希冲突直接返回false。
  
• LinkedHashSet：LinkHashSet在hashSet的基础上维护了一个双向列表来维护插入的顺序。
  
• TreeSet：基于红黑树，查找效率不如hashSet，log(n),但支持有序性的操作。
  

4.CopyOnWriteArrayList

写时复制。其实就是每次写入的时候加一个可重入锁，retrantLock，然后复制一个数组,size+1去插入新的元素，然后返回释放锁。
二.Map



1.HashMap

（1）基本结构

• 1.7是基于哈希表实现的，使用的是冲突链表的方式来解决哈希冲突；1.8是哈希表+链表+红黑树，为了降低过长的链表的查询开销O(n)，当链表的元素达到8时，会将链表转化为红黑树，查找的时间复杂度为log(n).
  
• hashMap没有考虑线程安全。
  
• hashMap的kv键值对可以为null
  

（2）hashMap的put(k,v)操作怎么执行的？
step1:先通过key计算出其hash值作为哈希表的下标i，如果table为空或者没初始化，扩容哈希表。
step2:根据下标i找到对应位置的k值，如果不存在，则直接插入；如果存在，就判断要插入的k和这个k是不是相同，相同就替换掉，不相同就进行下一步的判断。
step3:如果Node(i)是红黑树，则将新增的值直接插入红黑树中；如果Node(i)是链表，则遍历链表插入，如果链表的长度大于8，将该链表转化为红黑，否则直接插入即可。
（3）hashMap怎么扩容？
hashmap在两种情况下会扩容：一是在初始化哈希表的时候会扩容；而是容量不足的时候会扩容。
决定是否扩容的有两个参数：初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。
（4）hashMap怎么解决hash冲突？

• 将有冲突的hash值组成成列表放在同一个hash bucket下。
  
• 将如果使用hashCode取余，那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的，所以我们的思路就是让hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动。
  
• jdk1.8增加了红黑树，减少了由于哈希冲突导致链表过长查找效率低的问题。
  

（5）jdk1.7和jdk1.8的hashMap有什么不同？


2.HashTable

• hashTable的底层就是一个hashMap。
  
• 在更新操作上会加上Synchronized关键字，因此是线程安全的。
  
• hashTable的kv键值对不能为空。
  
• hashTable继承了Dictionary，而hashMap继承了AbstractMap。
  

3.ConcurrentHashMap

ConcurrentHashMap是面试重点，面试官经常会问1.7和1.8两个版本的区别
(1) jdk1.7的ConcurrentHashMap
   java使用了分段锁来保证ConcurrentHashMap的安全性。
概括来说就是，ConcurrentHashMap在hashMap的基础上，将原有的hashMap分为了好几个部分，称之为Segment。一个Segement数组就构成了ConcurrentHashMap。每次加锁通过hash找到对应的Segment，一个segment维护了一个hashEntry(哈希表+链表)，当写入一个键值对时，只对Segment加锁，也被称为分段锁。Segment 是一种可重入的锁 ReentrantLock。
(2) jdk1.8的ConcurrentHashMap
1.8摒弃了1.7的segment的设计，使用了哈希表+链表+红黑树的数据结果欧，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现。
三.JAVA集合的快速失败机制（fast-fail）

是java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。
例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。
原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
解决办法：
1. 在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。
2. 使用CopyOnWriteArrayList来替换ArrayList。