【Java八股文总结】之集合

Java集合

一、集合概述

Java集合，也叫作容器，主要是由两大接口派生而来：—个是 collection 接口
主要用于 存放单一元素 ；另一个是 Map 接口，主要用于 存放键值对 。对于collection接口，下面又有三个主要的子接口：List、set和queue 。
Java集合框架如下图所示：

1、List、Set、Queue、Map的区别？

• List（对付顺序的好帮手）：存储的元素是 有序的、可重复的 。
• set（注重独—无二的性质）：存储的元素是 无序的、不可重复的 。
• Queue（实现排队功能的叫号机）：按特定的排队规则来确定先后顺序，存储的元素是 有序的、可重复的 。
• Map（用key来搜索的专家）：使用键值对(key-value)存储，类似于数学上的函数y=f(x)，"x”代表key ,"y"代表value，key是无序的、不可重复的，value是无序的、可重复的 ，每个键最多映射到一个值。
  
  
  

2、Collections和Collection的区别？

① java.util.Collection 是一个 集合接口 ，它提供了对集合对象进行基本操作的通用接口方法。List，Set，Queue接口都继承Collection，主要用于存放 单⼀元素 。
② java.util.Collections 是一个 集合工具类 。它包含有各种有关集合操作的静态方法（对集合的查找、排序、反转、线程安全化等），大多数方法都是用来处理线性表的。此类不能实例化，就像一个工具类，服务于Java的Collection框架。

3、集合和数组的区别

• 数组是固定长度的；集合可变长度的。
• 数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。
• 数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。

二、List

1、ArrayList和LinkedList的区别？

2、ArrayList和Vector的区别

① ArrayList是基于数组的实现，是 非线程安全的 ，效率高，所有的方法都没有synchronized修饰。
② Vector是 线程安全的 ，效率低，实现线程安全是直接通过 synchroized 修饰方法来完成的。

3、Vector、ArrayList和LinkedList的区别

①Vector、ArrayList都是以类似 数组的形式 存储在内存中，LinkedList则以 链表的形式 进行存储。
②List中的元素有序、允许有重复的元素，Set中的元素无序、不允许有重复元素。
③Vector线程同步，线程安全，ArrayList、LinkedList线程不同步，线程不安全。
④LinkedList适合指定位置插入、删除操作，不适合查找；ArrayList、Vector适合查找，不适合指定位置的插入、删除操作。
⑤ArrayList在元素填满容器时会自动扩充容器大小的50%，而Vector则是100%，因此ArrayList更节省空间。

4、ArrayList 扩容机制

参见ArrayList扩容机制分析
ArrayList是基于数组的集合，数组的容量是在定义的时候确定的，如果数组满了，再插入，就会数组溢出。所以在插入时候，会先检查是否需要扩容，如果当前容量+1超过数组长度，就会进行扩容（先扩容再插入） 。
ArrayList的扩容是创建一个1.5倍的新数组，然后把原数组的值拷贝过去。

5、ArrayList序列化？为什么用transient修饰？

ArrayList的序列化不太一样，它使用 transient 修饰存储元素的 elementData 的数组， transient 关键字的作用是 让被修饰的成员属性不被序列化 。

为什么ArrayList不直接序列化元素数组呢？
出于效率的考虑，数组可能长度100，但实际只用了50，剩下的50不用其实不用序列化，这样可以提高序列化和反序列化的效率，还可以节省内存空间。

那ArrayList怎么序列化呢？
ArrayList通过两个方法readObject、writeObject自定义序列化和反序列化策略，实际直接使用两个流ObjectOutputStream和ObjectInputStream来进行序列化和反序列化。

6、快速失败（fail-fast）和安全失败（fail-safe）？

• 快速失败（fail—fast）： 快速失败是Java集合的 一种错误检测机制 。
  在用迭代器遍历一个集合对象时，如果线程A遍历过程中，线程B对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。
  原理： 迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个modCount变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
  注意： 这里异常的抛出条件是检测到modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。
  场景： java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如ArrayList 类。

• 安全失败（fail—safe）
  采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。
  原理： 由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发Concurrent Modification Exception。
  缺点： 基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。
  场景： java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改，比如CopyOnWriteArrayList类。

7、线程安全的ArrayList

保证ArrayList的线程安全可以通过这些方案：

• 使用Vector代替ArrayList。
• 使用Collections.synchronizedList包装 ArrayList，然后操作包装后的list。
• 使用CopyOnWriteArrayList代替ArrayList。
• 在使用ArrayList时，应用程序通过同步机制去控制ArrayList的读写。

8、CopyOnWriteArrayList

CopyOnWriteArrayList就是线程安全版本的ArrayList。
它的名字叫 CopyOnWrite——写时复制，已经明示了它的原理。
CopyOnWriteArrayList采用了一种 读写分离的并发策略 。
CopyOnWriteArrayList容器允许并发读，读操作是无锁的，性能较高。至于写操作，比如向容器中添加一个元素，则 首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器 。

三、Set集合

1、comparable和Comparator的区别

• comparable接口实际上是出自 java.lang 包，它有一个compareTo(Object obj)方法用来排序
• comparator接口实际上是出自 java.util 包，它有一个compare(Object obj1, Object obj2)方法用来排序。
  一般我们需要对一个集合使用自定义排序时，我们就要重写compareTo()方法或compare()方法，当我们需要对某一个集合实现两种排序方式，比如一个song对象中的歌名和歌手名分别采用一种排序方法的话，我们可以重写compareTo()方法和使用自制的comparator方法或者以两个Comparator来实现歌名排序和歌星名排序，第二种代表我们只能使用两个参数版的Collections.sort() 。

2、无序性和不可重复性的含义是什么？

• 无序性不等于随机性，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。
• 不可重复性是指添加的元素按照equals()判断时，返回false，需要同时重写equals()方法和hashCode()方法。

3、HashSet、LinkedHashSet和TreeSet异同

• HashSet , LinkedHashSet和TreeSet都是set接口的实现类，都能保证元素唯一， 并且都不是线程安全的 。
• HashSet , LinkedHashset和TreeSet的主要区别在于底层数据结构不同。HashSet的底层数据结构是 哈希表 (基于HashMap实现)。LinkedHashSet的底层数据结构是 链表和哈希表 ，元素的插入和取出顺序满足FIFO。TreeSet底层数据结构是 红黑树 ，元素是有序的，排序的方式有自然排序和定制排序。
• 底层数据结构不同又导致这三者的应用场景不同。 Hashset用于不需要保证元素插入和取出顺序的场景，LinkedHashSet用于保证元素的插入和取出顺序满足FIFO的场景，TreeSet用于支持对元素自定义排序规则的场景。★★★

三、Queue

1、Queue和Deque的区别？

2、ArrayDeque和LinkedList的区别？

3、PriorityQueue

五、Map

1、HashMap和HashTable的区别

2、HashMap和HashSet的区别

3、HashMap和TreeMap的区别

4、HashSet 如何检查重复？（★★★）

Q：equals 和 == 的区别？

所有类中的equals方法都是继承自Object类，Object类中原生的equals方法就是在通过 "" 进行判断。

public boolean equals (Object obj) {
	return (this == obj);
}
1
2
3

但是每个类都可以对equals方法进行重写，覆盖掉之前使用进行判断的逻辑，改用新的逻辑进行判断是否相等。
**：** 判断的是栈内存中的值。
引用类型 的数据，栈内存中存储的是地址，所以此时 == 判断的是引用地址。
基本数据类型，栈内存中存储的是具体的数据，判断的是值。

Q：什么是HashCode？

将对象的内部信息（内存地址、属性值等），通过某种特定规则转换成一个散列值，就是该对象的hashCode。
两个不同对象的hashCode值可能相等。
hashCode值不相等的两个对象一定不是一个对象。

集合在判断两个对象是否相等的时候，会①先比较他们的hashCode值，如果hashCode不相等，则认为不是同一个对象，可以添加。
如果②hashCode值相等，还不能认为两个对象是相等的，需要通过equals方法进行进一步的判断，equals相等，则两个对象相等，否则两个对象不相等。
hashCode相等，未必相等；hashCode不相等，则一定不相等。

Q：解决哈希冲突的方法有？

• 链地址法： 在冲突的位置拉一个链表，把冲突的元素放进去。
• 开放定址法： 开放定址法就是从冲突的位置再接着往下找，给冲突元素找个空位。
• 再哈希法： 换种哈希函数，重新计算冲突元素的地址。
• 建立公共溢出区： 再建一个数组，把冲突的元素放进去。

5、HashMap的底层实现（重要）

参见HashMap源码&底层数据结构分析

Q：HashMap的put流程？

1. 首先进行哈希值的扰动，获取一个新的哈希值。(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
2. 判断tab是否为空或者长度为0，如果是则进行扩容操作。if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;
3. 根据哈希值计算下标，如果对应下标正好没有存放数据，则直接插入即可否则需要覆盖。tab[i = (n - 1) & hash])
4. 判断tab[i]是否为树节点，否则向链表中插入数据，是则向树中插入节点。
5. 如果链表中插入节点的时候，链表长度大于等于8，则需要把链表转换为红黑树。treeifyBin(tab, hash);
6. 最后所有元素处理完成后，判断是否超过阈值；threshold，超过则扩容。

Q：HashMap怎么查找元素？

HashMap的查找：
1. 使用扰动函数，获取新的哈希值。
2. 计算数组下标，获取节点。
3. 当前节点和key匹配，直接返回。
4. 否则，当前节点是否为树节点，查找红黑树。
5. 否则，遍历链表查找。

Q：为什么HashMap链表转为红黑树的阈值是8？

链表转红黑树，是牺牲空间换时间。阈值为什么要选8呢？ 为了尽可能低的发生哈希碰撞，也为了避免资源浪费。

Q：扩容的时机？扩容因子为什么是0.75？

对 空间成本 和 时间成本 平衡的考虑。
假如我们设的比较大，元素比较多，空位比较少的时候才扩容，那么发生哈希冲突的概率就增加了，查找的时间成本就增加了。
我们设的比较小的话，元素比较少，空位比较多的时候就扩容了，发生哈希碰撞的概率就降低了，查找时间成本降低，但是就需要更多的空间去存储元素，空间成本就增加了。

Q：HashMap 1.8 发生的变化？

1. 数据结构： 数组+链表 ==> 数组+链表或红黑树
   原因：发生hash冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由O(n)降为O(logn)。
2. 链表插入方式： 头插法 ==> 尾插法
   原因：因为1.7头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环。
3. 扩容rehash： 扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。
   原因：提高扩容的效率，更快地扩容。
4. 扩容时机： 在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容。
5. 散列函数： 1.7做了4次移位和4次异或，1.8只做1次。
   原因：做4次的话，边际效用也不大，改为1次，提升效率。

Q：HashMap在多线程下会发生什么？

1. 多线程下扩容死循环。
2. 多线程的put操作可能导致元素丢失。
3. put和get并发时，可能导致get为null。

Q：HashMap为什么不安全？

在 hashMap1.7 中扩容的时候，因为采用的是 头插法 ，所以会可能会有循环链表产生，导致数据有问题，在 1.8 版本已修复，改为了尾插法。
在任意版本的 hashMap 中，如果在插入数据时多个线程命中了同一个位置，可能会有数据覆盖的情况发生，导致线程不安全。

Q：线程安全的HashMap？

Java中有HashTable、Collections.synchronizedMap、ConcurrentHashMap可以实现线程安全的Map。

1. HashTable是直接在操作方法上 加synchronized关键字 ，锁住整个table数组，粒度比较大；
2. Collections.synchronizedMap是使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现；
3. ConcurrentHashMap在jdk1.7中使用分段锁，在jdk1.8中使用CAS+synchronized。

6、HashMap的长度为什么是2的幂次方？

7、HashMap的常见遍历方式

参见HashMap 的 7 种遍历方式与性能分析！「修正篇」

8、ConcurrentHashMap和HashTable的区别

Q：红黑树了解么？为什么不用二叉树/平衡树呢？

红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：

• 每个节点要么是红色，要么是黑色。
• 根节点永远是黑色的。
• 所有的叶子节点都是黑色的（注意这里说叶子节点其实是图中的null节点）。
• 每个红色节点的两个子节点一定都是黑色。
• 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

为什么不用二叉树？
红黑树是一种平衡的二叉树，插入、删除、查找的 最坏时间复杂度都为O(logn) ，避免了二叉树最坏情况下的O(n)时间复杂度。

为什么不用平衡二叉树？
平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。

Q：红黑树怎么保持平衡？

红黑树有两种方式保持平衡：旋转（左旋和右旋）和染色。

9、ConcurrentHashMap线程安全的具体实现方式/底层具体实现

参见ConcurrentHashMap源码&底层数据结构分析

Q：JDK1.7 和 JDK1.8的ConcurrentHashMap实现的不同？

Q：Collections工具类常用方法

10、HashMap和LinkedHashMap的区别？

LinkedHashMap 继承自HashMap ，底层基于HashMap和双向链表来实现的。
HashMap无序，LinkedHashMap有序，可分为插入顺序和访问顺序两种。
如果是访问顺序，那put和get操作已经存在的Entry时都会把Entry移动到双向链表的标为（先删除再插入）。遍历时按照插入顺序排序，原因在于LinkedHashMap的内部类LinkedHashIterator，执行Iterator.next访问链表的下一个元素，所以可以按照插入顺序的输出。
LinkedHashMap存储数据，还是跟HashMap一样使用Entry的方式，双向链表只是为了保证顺序。
HashMap的遍历速度和他的容量有关，而LinkedHashMap只跟实际数量有关。
LinkedHashMap按照插入顺序排序，HashMap基于哈希表乱序。

11、TreeMap

• TreeMap是一个 有序的key-value集合 ，它是通过红黑树实现的。
• TreeMap基于 红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的Comparator进行排序，具体取决于使用的构造方法。
• TreeMap是 线程非同步的 。

六、集合使用注意事项

注意：
1、ArrayList的subList结果不可强转成ArrayList，否则会抛出ClassCastException异常。
2、不要在foreach循环里进行元素的remove/add操作。remove元素请使用Iterator方式,如果并发操作,需要对Iterator对象加锁。