集合（三）面试篇

1、说明Set、List、Map三个接口存取元素时，各有什么特点？

• List:以特定的索引来存取元素，可以有重复的元素
• Set:不允许有重复的元素，用对象的equals()方法来判断元素是否相等。
• Map:以键值对的方式存取元素，映射关系可以为一对一，也可以为一对多，key值不允许有重复

Set和Map容器都有基于哈希（HashSet、HashMap）和基于排序树的两种实现版本，基于哈希存取时间复杂度为O(1)；
基于排序树的实现是根据元素和元素的键构成排序树从而达到排序和去重的效果

---

2、ArrayList、Vector、LinkedList的存储性能和特点

• ArrayList和Vector都是基于数组实现的，Vector出现的最早，基于索引来访问元素，当插入元素时候，所有元素需要移动内存操作，因此插入元素慢，访问快。

• ArrayList 是线程不安全的，Vector是线程安全的

• LinkedList通过双向链表实现存取数据（链式存储较数组的连续存储，内存利用率高），按照序号索引数据需要前向或者后向遍历，而插入数据只需要记录本项的前后项即可，所以插入速度快。同样也是线程不安全的

Collection c = Collection.synchronizedCollection(new ArrayList);
List list = Collection.synchronizedList(new ArrayList);

---

3、HashMap和HashTable区别

• HashMap 的 key 和 value允许为空，而HashTable不允许
• HashMap 是线程不安全的，HashTable 是线程安全的
• HashMap的迭代器(Iterator)是fail-fast，HashTable的迭代器不是fail-fast的

---

4、快速失败和安全失败

• 快速失败（fail-fast）
  在用迭代器遍历一个集合对象时，如果对集合中的对象进行了修改（修改、删除、增加），则会抛出Concurrent.Modification.Exception
  原理：迭代器在遍历时候，直接访问集合中内容，并在遍历过程中使用一个modCount变量。集合在被遍历期间，如果内容发生了改变，modCount的值就会被改变。每当迭代器使用hasNext()/next()遍历下一个元素时，都会检测modCount变量是否为expectedmodCount值，是的话，就返回遍历；否则抛出异常，终止遍历
  场景：java.util包下的集合类都是快速失败的，不能再多线程下发生并发修改
• 安全失败（fail-safe）
  采用安全失败机制的集合容器，在遍历时，不是直接访问集合元素，而是先复制集合，对复制后的集合进行遍历。
  原理：由于迭代时是对拷贝的集合进行遍历，对原来的集合进行操作不会被迭代器检测到，所以不会抛出 Concurrent Modification Exception
  缺点：迭代器不能访问到修改后的内容。即迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的改变迭代器是不知道的。

场景：java.util.concurrent包下的容器都是安全失败的，可以在
多线程并发使用，并发修改

---

5、Iterator和ListIterator的区别
ListIterator实现了Iterator接口，增加了其他的函数、包括（增加、替换、获取前后一个元素的索引）

	Iterator	ListIterator
遍历	Set 和 List	List
方向	前向	前后向

---

6、HashMap的实现原理
参考：https://www.jianshu.com/p/db248e97a437

---

7、ConCurrentHashMap实现原理

image.png
image.png

ConCurrentHashMap类中包含两个静态内部类HashEntry和Segment。HashEntry用来封装映射表的键/值对；Segment用来充当锁的角色，（Segment继承ReentrantLock）。每个Segment对象守护整个散列表的若干个桶。每个桶由若干个HashEntry对象链接起来的链表。一个ConCurrentHashMan实例包含若干个Segment对象组成的数组。HashEntry用来封装散列映射表中的键值对。
在HashEntry类中，key,hash,next域都被声明为final型，value被声明为volatie型。

image.png

put方法：从源码看出，put的主要逻辑也就两步：
1.定位segment并确保定位的Segment已初始化
2.调用Segment的put方法。

JAVA8 需要理解 CAS锁
参考链接，详细将源码：https://blog.csdn.net/sihai12345/article/details/79383766

参考链接1：https://baijiahao.baidu.com/s?id=1631204589699207043&wfr=spider&for=pc
参考链接2：

---

8、请解释下TreeMap
TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。
TreeMap 继承于AbstractMap，所以它是一个Map，即一个key-value集合。
TreeMap 实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。
TreeMap 实现了Cloneable接口，意味着它能被克隆。
TreeMap 实现了java.io.Serializable接口，意味着它支持序列化。

TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。
另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。
红黑树有如下特点：

---

9、ArrayList是否会越界
ArrayList 并发add可能会出现下标越界异常。