【两万字】面试官：听说你很懂集合源码，接我二十道问题！

• 2020 年 6 月 28 日
• 筆記
• Java Grammar, 面试

### 问题一：看到这个图，你会想到什么？

（PS：截图自《编程思想》）

**答**：

这个图由`Map`指向`Collection`的`Produces`并不是说`Map`是`Collection`的一个子类（子接口），这里的意思是指`Map`的`KeySet`获取到的一个视图是`Collection`的子接口。

我们可以看到集合有两个基本接口：`Map`和`Collection`。但是我个人认为`Map`并不能说是一个集合，称之为映射或许更为合适，因为它的`KeySet`视图是一个`Set`类型的键集，所以我们姑且把它也当做集合。

`Collection`继承了`Iterator`接口，而`Iterator`的作用是给我们提供一个只能向后遍历集合元素的迭代器，也就是说所有实现`Collection`的类都可以使用`Iterator`遍历器去遍历。

每种接口都有一个`Abstract`开头的抽象子类，这个子类中包括了一些默认的实现，我们在自定义类的时候都需要去继承这个抽象类，然后根据我们不同的需求，对于其中的方法进行重写。

从容器角度上来说，只有四种容器：`Map`，`Queue`，`Set`，`List`。

### 问题二：列出常见的集合，并进行简单的介绍

**答：**

1. ArrayList: 一种可以动态增长和缩减的的索引序列
2. LinkedList：一种可以在任何位置进行高效地插入和删除操作的**有序序列**
3. ArrayDeque：一种用循环数组实现的双端队列
4. HashSet：一种没有重复元素的无序集合
5. TreeSet：一种有序集
6. EnumSet：一种包含枚举类型值的集
7. LinkedHashSet：一种可以记住元素插入次序的集
8. PriorityQueue：一种允许高效删除最小元素的集合
9. HashMap：一种存储键/值关联的数据结构
10. TreeMap：一种键值有序排列的映射表
11. EnumMap：一种键值属于枚举类型的映射表
12. LinkedHashMap：一种可以记住键/值项添加次序的映射表
13. WeakHashMap：一种其值无用武之地后可以被垃圾回收期回收的映射表
14. IdentityHashMap：一种用==而不是用equals比较键值的映射表
15. Vector：目前使用较少，因为设计理念的陈旧和性能的问题被ArrayList所取代
16. Hashtable：线程非同步可以使用HashMap来替代，同步的话可以使用ConcurrentHashMap来替代

### 问题三：关于Iterator，聊聊你的看法

从鸟瞰图中我们可以看到，所有实现`Collection`的子类都继承了`Iterable`接口。这个接口提供了一个`iterator()`方法可以构造一个`Iterator`接口对象。然后我们可以使用这个迭代器对象依次访问集合中的元素。

迭代器一般**使用方法**是这样的：

“`java
Collection c = …;
Iterator iter = c.iterator();
while (iter.hasNext()) {
String s = iter.next();
System.out.println(s);
}
“`

或者是这样的：

“`java
//适用于JDK1.8以后的版本
iter.forEachRemaining(element -> System.out.println(element));
“`

迭代器的`next()`**工作原理**是这样的：

迭代器是位于两个集合元素之间的位置，当我们调用`next()`方法的时候迭代器指针就会越过一个元素，并且返回刚刚越过的元素，所以，当我们迭代器的指针在最后一个元素的时候，就会抛出会抛出一个`NoSuchElementException`的异常。所以，在调用`next()`之前需要调用`hasNext()`去判断这个集合的迭代器是否走到了最后一个元素。

通过调用`next()`方法可以**逐个**的去访问集合中的每个元素，而访问元素的顺序跟该容器的**数据结构**有关，比如`ArrayList`就是按照索引值开始，每次迭代都会使索引值加1，而对于HashSet这种数据结构是散列表的集合，就会按照某种随机的次序出现。

`Iterator`的接口中还有一个`remove()`方法，这个方法实际上删除的是**上次调用next()方法返回的元素**，下面我来展示一下`remove()`方法的使用方法

“`java
Collection c = …;
Iterator iter = c.iterator();
iter.next();
iter.remove();
“`

这样就可以删除该集合中的第一个元素，但是需要注意一点，如果我们需要删除两个元素，**必须**这样做：

“`java
iter.remove();
iter.next();
iter.remove();
“`

而不能这么做：

“`java
iter.remove();
iter.remove();
“`

因为`next()`方法和`remove()`方法之间是有**依赖性**的，如果调用`remove`之前没有调用`next`就会抛出一个`IllegalStateException`的异常。

### 问题四：对于Collection，你了解多少？

可以看出，作为顶级的框架，`Collection`仅仅是继承了`Iterable`接口，接下来，我们来看一下`Iterable`的源码，看看有什么收获。

“`java
public interface Iterable {

Iterator iterator();

default void forEach(Consumer action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}

default Spliterator spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}

“`

可以看到这个接口中有三个方法，其中`iterator()`方法可以给我们提供一个迭代器，这个在之前的教程就已经说过了，而`forEach()`方法提供了一个函数式接口的参数，我们可以使用`lambda`表达式结合来使用：

“`java
Collection collection = …;
collection.forEach(String s -> System.out.println(s));
“`

这样就可以获取到每个值，它的底层实现是加强`for`循环，实际上也是迭代器去遍历，因为编译器会把加强`for`循环编译为迭代遍历。
`Spliterator()`是`1.8`新加的方法，字面意思可分割的迭代器，不同以往的`iterator()`需要顺序迭代，`Spliterator()`可以分割为若干个小的迭代器进行并行操作，既可以实现多线程操作提高效率，又可以避免普通迭代器的`fail-fast`(`fail-fast`机制是`java`集合中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生`fail-fast`事件)机制所带来的异常。`Spliterator()`可以配合`1.8`新加的`Stream()`进行并行流的实现，大大提高处理效率。


`Collection()`中提供了17个接口方法（除去了继承自`Object`的方法）。接下来，我们来了解一下这些方法的作用：

1. `size()`，返回当前存储在集合中的元素个数。
2. `isEmpty()`，如果集合中没有元素，返回true。
3. `contains(Object obj)`，如果集合中包含了一个与obj相等的对象，返回true。
4. `iterator()`，返回这个集合的迭代器。
5. `toArray()`，返回这个集合的对象数组
6. `toArray(T[] arrayToFill)`，返回这个集合的对象数组，如果arrayToFill足够大，就将集合中的元素填入这个数组中。剩余空间填补null；否则，分配一个新数组，其成员类型与arrayToFill的成员类型相同，其长度等于集合的大小，并填充集合元素。
7. `add(Object element)`，将一个元素添加到集合中，如果由于这个调用改变了集合，返回true。
8. `remove(Object obj)`，从集合中删除等于obj的对象，如果有匹配的对象被删除，返回true。
9. `containsAll(Collection other)`，如果这个集合包含other集合中的所有元素，返回true。
10. `addAll(Collection other)`，将other集合中的所有元素添加到这个集合，如果由于这个调用改变了集合，返回true。
11. `removeAll(Collection other)`，从这个集合中删除other集合中存在的所有元素。如果由于这个调用改变了集合，返回true。
12. `removeIf(Predicate filter)`，从这个集合删除filter返回true的所有元素，如果由于这个调用改变了集合，则返回true。
13. `retainAll(Collection other)`，从这个集合中删除所有与other集合中的元素不同的元素。如果由于这个调用改变了集合，返回true。
14. `clear()`，从这个集合中删除所有的元素。
15. `spliterator()`，返回分割后的若干个小的迭代器。
16. `stream()`，返回这个集合对于的流对象。
17. `parallelStream()`，返回这个集合的并行流对象。

作为第一级的集合接口，`Collection`提供了一些基础操作的借口，并且可以通过实现`Iterable`接口获取一个迭代器去遍历获取集合中的元素。

### 问题五：那么AbstractCollection呢？

作为`Collection`的抽象类实现，它的方法都是基于迭代器来完成的，这里只贴出了源码中几个需要特殊的注意的点，


**TAG 1** :

数组作为一个对象，需要一定的内存存储对象头信息，对象头信息最大占用内存不可超过8 byte。

**TAG 2** :

`finishToArray(T[] r, Iterator it)`方法用于数组扩容，当数组索引指向最后一个元素+1时，对数组进行扩容：即创建一个大小为（cap + cap/2 +1）的数组，然后将原数组的内容复制到新数组中。扩容前需要先判断是否数组长度是否溢出。这里的迭代器是从上层的方法（`toArray(T[] t)`）传过来的，并且这个迭代器已执行了一部分，而不是从头开始迭代的

**TAG 3** ：

`hugeCapacity(int minCapacity)`方法用来判断该容器是否已经超过了该集合类默认的最大值即（`Integer.MAX_VALUE -8`），一般我们用到这个方法的时候比较少，后面我们会在`ArrayList`类的学习中，看到`ArrayList`动态扩容用到了这个方法。

**TAG 4** ：

这里的`add(E)`方法默认抛出了一个异常，这是因为如果我们想修改一个不可变的集合时，抛出 `UnsupportedOperationException` 是正常的行为，比如当你用 `Collections.unmodifiableXXX()` 方法对某个集合进行处理后，再调用这个集合的修改方法（`add`,`remove`,`set…`），都会报这个错。因此 `AbstractCollection.add(E)` 抛出这个错误是准从标准。

### 问题六： 能否详细说一下toArray方法的实现？

**高能预警：废话不多说，直接上源码**

“`java

/**
* 分配了一个等大空间的数组，然后依次对数组元素进行赋值
*/
public Object[] toArray() {
//新建等大的数组
Object[] r = new Object[size()];
Iterator it = iterator();
for (int i = 0; i < r.length; i++) {
//判断是否遍历结束，以防多线程操作的时候集合变得更小
if (! it.hasNext())
return Arrays.copyOf(r, i);
r[i] = it.next();
}
//判断是否遍历未结束，以防多线程操作的时候集合变得更大，进行扩容
return it.hasNext() ? finishToArray(r, it) : r;
}

/**
* 泛型方法的`toArray(T[] a)`方法在处理里，会先判断参数数组的大小，
* 如果空间足够就使用参数作为元素存储，如果不够则新分配一个。
* 在循环中的判断也是一样，如果参数a能够存储则返回a,如果不能再新分配。
*/
@SuppressWarnings(“unchecked”)
public T[] toArray(T[] a) {
int size = size();
//当数组a的长度大于等于a，直接将a赋予给r，否则使用反射API获取一个长度为size的数组
T[] r = a.length >= size ? a :
(T[])java.lang.reflect.Array
.newInstance(a.getClass().getComponentType(), size);
Iterator it = iterator();
for (int i = 0; i < r.length; i++) {
//判断是否遍历结束
if (! it.hasNext()) {
//如果 a == r，将r的每项值赋空，并将a返回
if (a == r) {
r[i] = null;
} else if (a.length < i) {
//如果a的长度小于r，直接调用Arrays.copyOf进行复制获取一个新的数组
return Arrays.copyOf(r, i);
} else {
System.arraycopy(r, 0, a, 0, i);
if (a.length > i) {
a[i] = null;
}
}
return a;
}
//如果遍历结束，将迭代器获取的值赋给r
r[i] = (T)it.next();
}
//判断是否遍历未结束，以防多线程操作的时候集合变得更大，进行扩容
return it.hasNext() ? finishToArray(r, it) : r;
}

/**
* 设定该容器的最大值
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8;

/**
* 用于动态扩容
*/
@SuppressWarnings(“unchecked”)
private static T[] finishToArray(T[] r, Iterator it) {
int i = r.length;
while (it.hasNext()) {
int cap = r.length;
if (i == cap) {
int newCap = cap + (cap >> 1) + 1;

if (newCap – MAX_ARRAY_SIZE > 0)
newCap = hugeCapacity(cap + 1);
r = Arrays.copyOf(r, newCap);
}
r[i++] = (T)it.next();
}
return (i == r.length) ? r : Arrays.copyOf(r, i);
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError
(“Required array size too large”);
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
“`

为了帮助了解，我把`Arrays.copyOf(r.i)`的源码也贴出来：

“`java
//参数original代表你传入的需要复制的泛型数组，newLength复制得到数组的大小
public static T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}

public static T[] copyOf(U[] original, int newLength, Class newType) {
@SuppressWarnings(“unchecked”)
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
“`

我们可以观察到其中调用了`System.arraycopy`方法，为了保持刨根问底的态度，我们又去翻看了这个方法的源码：

“`java
//src数组里从索引为srcPos的元素开始, 复制到数组dest里的索引为destPos的位置, 复制的元素个数为length个.
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos,int length);
“`

可以看到这个方式是由关键字`native`修饰的方法，那么`native`修饰的方法有什么含义呢？
`native`关键字说明其修饰的方法是一个原生态方法，方法对应的实现不是在当前文件，而是在用其他语言（如C和C++）实现的文件中。Java语言本身不能对操作系统底层进行访问和操作，但是可以通过JNI接口调用其他语言来实现对底层的访问。

> JNI是Java本机接口（Java Native Interface），是一个本机编程接口，它是Java软件开发工具箱（java Software Development Kit，SDK）的一部分。JNI允许Java代码使用以其他语言编写的代码和代码库。Invocation API（JNI的一部分）可以用来将Java虚拟机（JVM）嵌入到本机应用程序中，从而允许程序员从本机代码内部调用Java代码。

然后我们来分析`toArray()`中需要注意的点，通过原源码中的英文注解，`toArray`得到的数组跟原`collection`没有任何关系，我们可以对数组的每个引用值做修改，而不会影响到原collection.这个看起来好像是多余说明的，但是考虑到ArrayList其实就是基于数组实现的，那这个限制保证了即使是将ArrayList转化为数组，那也应该是分配一个新数组，而不是返回原来的数组。

如果我们在单线程操作的情况下，collection集合大小不变，正常应该是执行到 `return it.hasNext() ? finishToArray(r, it) : r; `这条语句结束，但考虑到在复制的过程中，`collection`的集合可能会有变化，可能是变大也可能是变小，所以方法增加了对这种情况的处理，这就是为什么每次循环都要判断是collection是否遍历完，以及最后再判断`collection`是否变得更长，如果是的话，还需要重新再为array分配空间。

通常情况下，我们不会执行到`hugeCapacity`，但作为一个框架来说，这体现了设计时的严谨。

### 问题七：用的最多的集合之一——List，说说你对它的理解

`List`是继承自`Collection`的一个子接口，它提供了一个**有序**的集合，在这个集合中我们可以使用索引去获取集合中的值，同时，我们也可以通过**迭代器**去访问集合中的元素，第一种方法被称为随机访问，因为我们可以按照任意的顺序去访问元素，而使用迭代器就必须顺序的去访问元素。

相比于它的父接口`Collection`，并没有发生很大的改动，但是由于`List`是一个有序的集合，所以提供了一些基于索引进行的操作：

`get(int index)`：获取该集合中索引等于index的元素

`set(int index, E element)`：将该集合中索引等于index的元素赋值为element

`add(int index, E element)`：在集合中索引等于index的位置将element插入，并将当前处于该位置的元素及其后续元素的索引加1。

`remove(int index)`：删除指定索引（index）位置的元素，并将处于该位置后面的元素索引减1

`indexOf(Object o)`：获取对象o在集合中的索引

`lastIndexOf(Object o)`：获取对象o在集合中最后一次出现的索引值，如果集合中不存在这个对象，返回-1。

同时，提供了一个`Iterator`的子接口`ListIterator`，基于这个迭代器，我们实现了两个默认方法`replaceAll(UnaryOperator operator)`和`sort(Comparator c)`。

`replaceAll(UnaryOperator operator)`这里和`String`类中`replaceAll()`方法并不相同，这里的接收参数是一个函数式接口，我们来看一下这个函数式接口的源码：

“`java
package java.util.function;

@FunctionalInterface
public interface UnaryOperator extends Function {

static UnaryOperator identity() {
return t -> t;
}
}
“`

用法如下：

“`java
List strList = new ArrayList<>();
strList.add(“Hungary”);
strList.add(“Foolish”);

strList.replaceAll(t -> “Stay ” + t);
strList.forEach(s -> System.out.println(s));
“`

打印结果为

> Stay Hungary Stay Foolish

而`sort(Comparator c)`传入的同样是一个函数式接口，我们可以自定义排序规则后，调用这个方法进行排序：

“`java
List humans = Lists.newArrayList(new Human(“Sarah”, 10), new Human(“Jack”, 12));

humans.sort((Human h1, Human h2) -> h1.getName().compareTo(h2.getName()))
“`

这里是`Arrays.sort`的源码，可以看到使用了归并算法和`TimSort`算法来进行排序。

“`java
public static void sort(T[] a, Comparator c) {
if (c == null) {
sort(a);
} else {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
“`

### 问题八：刚刚你说到了ListIterator，可以详细说一下嘛

前面我们已经提过，`ListIterator`作为`Iterator`的子接口，给有序的集合`List`提供了一个链表结构下的迭代器，接下来，我们来看一下`ListIterator`的源码：

和`Iterator`不同的是，`ListIterator`新增了一些基于链表数据结构的操作以及可以用来反向遍历链表的方法：

`hasPrevious()`：当反向迭代列表时，还有可供访问的元素，返回**true**。

`previous()`：返回前一个对象，如果已经到达了列表的头部，抛出一个`NoSuchElementException`异常

`nextIndex()`：返回下一次调用next方法将返回的元素索引

`previousIndex()`：返回下一次调用previous方法将返回的元素索引

`add(E newElement)`：在当前位置前添加一个元素。

`set(E newElement)`：用新元素取代next或previous上次访问的元素。如果在next或previous上次调用之后列表结构被修改了，将抛出一个`IllegalStateException`异常。

### 问题九：说说AbstractList

`AbstractList`是实现`List`接口的一个抽象类，它的地位之与`List`类似于`AbstractCollection`之与`Collection`，同事，`AbstractList`继承了`AbstractCollection`，并针对`List`接口给出了一些默认的实现。而且它是针对**随机访问储存数据**的方式的，如果需要使用顺序访问储存数据方式，还有一个`AbstractSequentialList`是`AbstractList`的子类，顺序访问时应该优先使用它。

接下来，我们来看一下`AbstractList`的源码，看看他针对于`List`接口相较于`AbstractCollection`给出了哪些不同的实现方法。

`AbstractList`的源码在结构上分为了两种内部迭代器，两种内部类以及`AbstractList`本身的代码，它的一些实现都是基于内部类和内部的两种迭代器：`Itr`和`ListItr`来完成的，下面是部分源码的解析（由于篇幅原因，不能放上全部，只能抛砖引玉，写一部分）

“`java

//由于该集合是不可变的，所以一切可能会改变集合元素的操作都会抛出一个UnsupportedOperationException()
public E set(int index, E element) {
throw new UnsupportedOperationException();
}

//获取某个元素在集合中的索引
public int indexOf(Object o) {
//这里是由AbstractList内部已经提供了Iterator, ListIterator迭代器的实现类，分别为Itr，ListItr。这里是调用了一个实例化ListItr的方法
ListIterator it = listIterator();
if (o == null) {
while (it.hasNext())
if (it.next()==null)
return it.previousIndex();
} else {
while (it.hasNext())
if (o.equals(it.next()))
return it.previousIndex();
}
//如果集合中不存在该元素，返回-1
return -1;
}

/**
* 内部实现了Iterator接口的实现类Itr
*/
private class Itr implements Iterator {

//光标位置
int cursor = 0;

//上一次迭代到的元素的光标位置，如果是末尾会置为-1
int lastRet = -1;

//并发标志，如果两个值不一致，说明发生了并发操作，就会报错
int expectedModCount = modCount;

//删除上一次迭代器越过的元素
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
//调用需要子类去实现的remove方法
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor–;
//每次删除后，将lastRet置为-1，防止连续的删除
lastRet = -1;
//将修改次数赋给迭代器对对象的结构修改次数这个会在下面进行详解
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
//如果出现索引越界，说明发生了并发的操作导致，所以抛出一个并发操作异常。
throw new ConcurrentModificationException();
}
}

//判断是否发生了并发操作
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

//继承自Itr的ListIterator的实现类ListItr
private class ListItr extends Itr implements ListIterator {

//获取上一位的元素，这里在后面会有画图帮助理解
public E previous() {
checkForComodification();
try {
//这里和父类的写法略有不同，先将光标的位置进行减一
int i = cursor – 1;
E previous = get(i);
//因为需要返回的是前一位的元素，所以这里的光标值和上一次迭代到的光标的位置实际上是一样的
lastRet = cursor = i;
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}

//设置元素
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
//默认设置的位置是上一次迭代器越过的元素
AbstractList.this.set(lastRet, e);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

//添加元素
public void add(E e) {
checkForComodification();
try {
//设置添加的位置为当前光标所在的位置
int i = cursor;
AbstractList.this.add(i, e);
//这里讲lastRet设置为-1，即添加的元素不允许立即删除
lastRet = -1;
//添加后，将光标移到
cursor = i + 1;
//迭代器并发标志和集合并发标志统一
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
//如果出现了索引越界，说明发生了并发操作
throw new ConcurrentModificationException();
}
}
}

//切取子List
public List subList(int fromIndex, int toIndex) {
//是否支持随机访问
return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
}

//使用迭代器成段删除集合中的元素
protected void removeRange(int fromIndex, int toIndex) {
ListIterator it = listIterator(fromIndex);
for (int i=0, n=toIndex-fromIndex; i extends AbstractList {

private final AbstractList l;
private final int offset;
private int size;

//根据父类来构造一个SubList
SubList(AbstractList list, int fromIndex, int toIndex) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException(“fromIndex = ” + fromIndex);
if (toIndex > list.size())
throw new IndexOutOfBoundsException(“toIndex = ” + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException(“fromIndex(” + fromIndex +
“) > toIndex(” + toIndex + “)”);
l = list;
offset = fromIndex;
size = toIndex – fromIndex;
//修改次数（并发标志）和父类保持一致
this.modCount = l.modCount;
}

//实际上还是调用的父类的set方法和get方法
public E set(int index, E element) {
rangeCheck(index);
checkForComodification();
return l.set(index+offset, element);
}

public void add(int index, E element) {
rangeCheckForAdd(index);
checkForComodification();
//实际上还是在父类上进行添加
l.add(index+offset, element);
this.modCount = l.modCount;
//然后把size + 1
size++;
}
}

//相较于SubList内部类，多了一个是否可以随机访问的标志
class RandomAccessSubList extends SubList implements RandomAccess {
RandomAccessSubList(AbstractList list, int fromIndex, int toIndex) {
super(list, fromIndex, toIndex);
}

public List subList(int fromIndex, int toIndex) {
return new RandomAccessSubList<>(this, fromIndex, toIndex);
}
}

“`

### 问题十：索引和游标的关系

这里我画了一个图，然后对照着这个图，我们再来看一下`ListItr`中的一些代码：

“`java
//下一位的索引值等于光标值
public int nextIndex() {
return cursor;
}

//上一位的索引值等于光标值减一
public int previousIndex() {
//其实这里并不理解，为啥不去检查索引越界。。
return cursor-1;
}
“`

假定迭代器现在运行到`1`所在的位置，可以很容易的看出当迭代器处于这个位置的时候，去调用`nextIndex()`方法得到的是1，而调用`previousIndex`得到的就是0。这是完全符合我们的逻辑的，接下来，我们再来看`previous()`方法的源码：

“`java
//获取上一位的元素，这里在后面会有画图帮助理解
public E previous() {
checkForComodification();
try {
//这里和父类的写法略有不同，先将光标的位置进行减一
int i = cursor – 1;
E previous = get(i);
//因为需要返回的是前一位的元素，所以这里的光标值和上一次迭代到的光标的位置实际上是一样的
lastRet = cursor = i;
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
“`

其实这里我在分析的时候是存在疑问的（为什么这里的`lastRet`等于`cursor`，而`Itr`中的`next()`方法的实现中`cursor`实际上等于`lastRet – 1`），在画完图分析索引和游标的关系之后又来看一遍才恍然大悟，

这里的`lastRet`代表的是上一次迭代到的元素的光标位置，所以，我们来举个例子，当迭代器在`4`的位置的时候，使用了`previous()`方法，这时的迭代器的位置是在`3`，而上次迭代到的元素的游标位置也是`3`，而如果使用了`next()`方法，使用之后，迭代器的位置在`5`，而上一次迭代到的元素确是`4`。这也印证了`nextIndex()`和`previousIndex()`的逻辑。

### 问题十一：expectedModCount 和 modCount

**答：**

从源码中我们可以看到

“`java
//这个变量是transient的，也就说序列化的时候是不需要储存的
protected transient int modCount = 0;
“`

这个变量代表着当前集合对象的结构性修改的次数，每次进行修改都会进行加1的操作，而`expectedModCount`代表的是迭代器对对象进行结构性修改的次数，这样的话每次进行结构性修改的时候都会将`expectedModCount`和`modCount`进行对比，如果相等的话，说明没有别的迭代器对对对象进行修改。如果不相等，说明发生了并发的操作，就会抛出一个异常。而有时也会不这样进行判断：

“`java
//删除上一次迭代器越过的元素
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
//调用需要子类去实现的remove方法
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor–;
//每次删除后，将lastRet置为-1，防止连续的删除
lastRet = -1;
//将修改次数赋给迭代器对对象的结构修改次数这个会在下面进行详解
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
//如果出现索引越界，说明发生了并发的操作导致，所以抛出一个并发操作异常。
throw new ConcurrentModificationException();
}
}
“`

这里的设计在于，进行删除操作后，将修改次数和迭代器对象进行同步，虽然在方法的开始进行了`checkForComodification()`方法的判断，但是担心的是再进行删除操作的时候发生了并发的操作，所以在这里进行了`try…catch…`的处理，当发生了索引越界的异常的时候，说明一定是发生了并发的操作，所以抛出一个`ConcurrentModificationException()`。

###问题十二：关于SubList和RandomAccessSubList

**答：**

通过阅读源码我们可以知道，这个类实际上就是一个啃老族。基本上方法全是直接去加上`offset`后去调用的父类的方法，而`RandomAccessSubList`只是在此基础上实现了`RandomAccess`的接口，这个接口仅仅是一个标志性接口，用来标志是否可以随机访问的。

### 问题十三：说说远古时代的ArrayList——Vector

**答：**

`Vector`是一种实现了动态数组的集合，即长度可以自动增长的数组，它是**线程同步（安全）**的，也就是说同一时刻只有一个线程可以写`Vector`，可以避免多线程同时写引起的不一致性，但是比较消耗资源。

由于资源的耗费较为严重，它已经逐渐的消失在了历史的尘埃中，取而代之的是同样基于动态数组实现的`ArrayList`。

### 问题十四：简单说一下Stack

**答：**

栈(`Stack`)是`Vector`的一个子类，它实现了一个标准的**后进先出的栈**。

“`java
public class Stack extends Vector {

/**
* Stack的无参构造函数
*/
public Stack() {
}

/**
* 把项压入堆栈顶部
*/
public E push(E item) {
addElement(item);
return item;
}

/**
* 移除堆栈顶部的对象，并作为此函数的值返回该对象。
* @return 被移除的对象
*/
public synchronized E pop() {
E obj;
int len = size();

obj = peek();
removeElementAt(len – 1);

return obj;
}

/**
* 查看堆栈顶部的对象
* @return
*/
public synchronized E peek() {
int len = size();
if (len == 0) {
throw new EmptyStackException();
}
return elementAt(len – 1);
}

/**
* 测试堆栈是否为空
* @return
*/
public boolean empty() {
return size() == 0;
}

/**
* 返回对象在堆栈中的位置，以 1 为基数
* @param o 需要查找位置的对象
* @return
*/
public synchronized int search(Object o) {
int i = lastIndexOf(o);

if (i >= 0) {
return size() – i;
}
return -1;
}

/**
* 版本id
*/
private static final long serialVersionUID = 1224463164541339165L;

}
“`

`Stack`继承自`Vector`，说明它也是通过数组实现的**，**而非链表。而且`Vector`类具有的特性它都具有。

### 问题十五：说一下你对ArrayList源码的理解

**答：**

`ArrayList`与`Vector`非常相似，他们都是基于数组实现的集合，都可以动态扩容，只不过`Vector`是同步的，所需的资源较多，而且比较老，有一些缺点，所以我们现在更多的是去使用`ArrayList`，而不是`Vector`。下面，我们在阅读源码的过程中遇到的一些问题对`ArrayList`进行分析。

首先从构造函数说起：

“`java

/**
* 共享空数组对象
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 和上面的区别在于，
* 第一次添加元素时知道该 elementData 从空的构造函数还是有参构造函数被初始化的。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* 用于盛放集合元素的数组对象
*/
transient Object[] elementData;

/**
* 有参构造，参数为初始长度，如果参数为0，调用EMPTY_ELEMENTDATA来初始化
*
* @param initialCapacity 该集合的初始化长度
* @throws IllegalArgumentException 如果参数小于0，抛出该错误
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException(“Illegal Capacity: “+
initialCapacity);
}
}

/**
* 无参构造，调用了DEFAULTCAPACITY_EMPTY_ELEMENTDATA来初始化
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
“`

这里新建了两个空的常量数组，分别用来构造有参初始长度为0的`ArrayList`实例和无参的`ArrayList`实例，这里的无参构造函数实际上的默认长度是10，而有参的初始长度和参数有关。这两个常量空数组起到的更多的是一种标记的作用，用于在后面的动态扩容中分不同的情况。

“`java

/**
* 提升该ArrayList对象容器的容量，确保可以提供一个该容器存放数据最低所需的容量
*
* @param minCapacity 最低所需容量
*/
public void ensureCapacity(int minCapacity) {
//这里可以看出，如果是默认的无参构造，最低容量是10，如果不是，最小是0。这里体现了代码设计的严谨性！
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0: DEFAULT_CAPACITY;
//如果最低所需的容量大于容器初始的最小容量，去调用扩容的方法，这里就体现出了两个不同常量的作用
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}

/**
* 计算最小所需容量
* @param elementData 需要计算的数组
* @param minCapacity 期望的最小所需容量
* @return 最小所需容量
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//判断该容器是否是默认无参构造，如果不是，直接返回传入的minCapacity
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//如果是，返回默认容量和期望的最小所需容量中的最大值
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

/**
* 扩容到最小所需容量方法
* @param minCapacity 最小容量
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

/**
* 扩容到最小所需容量的方法，这里的参数是经过计算后的最小容量
* @param minCapacity 经过计算后的最小容量
*/
private void ensureExplicitCapacity(int minCapacity) {
//这里关于modCount的疑问可以去看前面AbstractList中的实现
modCount++;
//这里进行一个关于最小容量和数组的长度比较，如果最小容量大于数组的长度，才会进行扩容
if (minCapacity – elementData.length > 0) {
grow(minCapacity);
}
}

/**
* 数组的最大容量
* 因为数组作为一个对象，需要一定的内存存储对象头信息，对象头信息最大占用内存不可超过8 byte
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8;

/**
* 动态扩容，确保数组的容量可以装下所有的元素
*
* @param 最低容量
*/
private void grow(int minCapacity) {
//首先获取当前的数组的容量
int oldCapacity = elementData.length;
//将数组扩容50%，比如原容量是4，扩容后为 4 + 4 / 2 = 6
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩容后的容量小于最小所需的容量
if (newCapacity – minCapacity < 0) {
//直接将最小容量作为该容器的容量
newCapacity = minCapacity;
}
//如果扩容后的容量大于数组最大的容量
if (newCapacity – MAX_ARRAY_SIZE > 0) {
//将经过处理后的最小所需容量作为新的容量，最大不超过Integer的最大值
newCapacity = hugeCapacity(minCapacity);
}
//使用Arrays.copyOf将原数组复制到一个新容量的数组，并将拷贝的结果返回给原数组，完成动态扩容。
elementData = Arrays.copyOf(elementData, newCapacity);
}

/**
* 防止数组的容量过大导致内存溢出的方法，程序基本上不会走到这里，只是以防万一
* @param minCapacity
* @return
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) {
throw new OutOfMemoryError();
}
//如果最小所需容量大于数组最大容量，返回Integer的最大值，否则返回数组的最大容量值
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
“`

从上面的动态扩容部分的源码分析中，我们可以看到这两个空常量数组的作用所在，这里又会遇到一个问题，在`ArrayList`的扩容过程中，是按照50%的比例进行扩容的，这里就有一个问题，扩容后的数组的长度一定会大于数组的长度，就会造成空间和资源的浪费，这时候可以使用下列的方法。

“`java
/**
* 清除集合中的空元素所占的空间，一般在动态扩容后会产生空余的空间
*/
public void trimToSize() {
modCount++;
//如果数组中数据的个数小于数组所占的空间，说明产生了多余的空间
if (size < elementData.length) {
//如果没有数据，返回一个EMPTY_ELEMENTDATA对象，否则将数据拷贝一个新的size长度的数组，并赋给原数组
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
“`

接下来，我们来看一下如何去获取`ArrayList`中的元素，

“`java
/**
* 返回用于存储元素的数组位于某个索引上的元素
* @param index 需要返回元素的索引
* @return 返回该索引位置上的元素
*/
@SuppressWarnings(“unchecked”)
E elementData(int index) {
return (E) elementData[index];
}

/**
* 返回该集合指定位置的元素
*
* @param index 需要返回元素的索引
* @return 该集合指定位置的元素
* @throws IndexOutOfBoundsException 当索引超过集合的长度时，抛出该异常
*/
@Override
public E get(int index) {
//这一步调用的是检查索引越界的方法
rangeCheck(index);
//这一步调用的是上面的elementData()方法，本质上还是根据索引去用于存储数据的数组中取
return elementData(index);
}
“`

可以看出，本质上底层还是通过数组来实现的，说到对于数组的操作，就必须说到这个在源码中频繁出现的方法

`System.arraycopy(Object[] src, int srcPos, Object[] dest, int destPos, int length)`

这几个参数的意思分别是：

“`
src:源数组；
srcPos:源数组要复制的起始位置；
dest:目的数组；
destPos:目的数组放置的起始位置；
length:复制的长度。
“`

看着看着，我们会发现一个问题，`ArrayList`中包括了两个`remove`方法

“`java
/**
* 删除位于某个索引位置的元素
*
* @param index 即将被删除的元素的索引
* @return 返回的是被删除的元素
* @throws IndexOutOfBoundsException 当索引超过集合的长度时，抛出该异常
*/
@Override
public E remove(int index) {
//首先进行索引越界的检查
rangeCheck(index);
//由于这个操作会引起结构的变化，所以要将modCount+1
modCount++;
//获取原本位于该位置的元素，用于返回
E oldValue = elementData(index);
//获取位于被删除索引的前一位的索引
int numMoved = size – index – 1;
if (numMoved > 0) {
//这里的原理是 elementData = {1 ,2 ,3 ,4} ===>
// 删除索引为1 的元素，然后 0(numMoved)的元素{1}作为头，将{3, 4}(index+1)后的部分拼接到原本的index的位置 ==>
// {1, 3, 4}，
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
}
//将原本最后一位，置为null ==> {1,3,4,null},再将size-1，完成删除
elementData[–size] = null;
return oldValue;
}

/**
* 删除集合中的指定元素，如果集合中包含该元素，返回true
*
* @param o 被删除的元素
* @return 如果集合中包含该指定元素，返回true
*/
@Override
public boolean remove(Object o) {
//分为两种情况 为null和不为null
if (o == null) {
for (int index = 0; index < size; index++) {
//为null的时候使用 == 判断
if (elementData[index] == null) {
//这里调用的这个方法其实和上面的方法类似，只不过没有返回值，而且没有进行索引的判断
fastRemove(index);
return true;
}
}
} else {
for (int index = 0; index < size; index++) {
//不为null的时候使用 equals 判断
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
}
return false;
}

/**
* 这里没有进行索引的越界判断，也没有返回被删除的值，其他的原理和remove(int index)类似
* @param index 被删除元素的索引，这里之所以不用判断，是因为在调用这个方法的时候就已经进行了判断，不存在越界的可能
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size – index – 1;
if (numMoved > 0) {
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
}
elementData[–size] = null;
}
“`

可以看出两个删除方法的区别在于，一个是根据元素找到索引进行删除，返回的是否删除成功，而一个是根据直接索引进行删除，返回的是被删除的元素，说起删除，下面我们还会看到一个被`private`修饰的`batchRemove(Collection c, boolean complement)`方法，而调用这个私有方法的分别是`removeAll(Collection c)`和`retainAll(Collection c)`，而这两个方法的区别在于一个是取交集，一个是取交集之外的元素，是两个刚好对立的方法。

“`java
/**
* 删除指定集合与collection的交集
*
* @param c 需要与集合进行判断的collection
* @return 如果这次操作改变了集合的结构，返回true
* @throws ClassCastException 如果集合的元素类型和该集合的元素类型不一致，抛出该异常
* @throws NullPointerException 如果参数collection为空，抛出空指针异常
*/
@Override
public boolean removeAll(Collection c) {
//首先进行非空校验
Objects.requireNonNull(c);
//调用封装好的批量删除的方法，这里传入的参数为false的时候，删除的是交集
return batchRemove(c, false);
}

/**
* 删除collection元素和该集合交集之外的元素
*
* @param c 需要将元素保留在该集合中的collection对象
* @return 如果这次操作改变了集合，返回true
* @throws ClassCastException 如果该集合的元素类型和collection中的元素不一致，抛出该异常
* @throws NullPointerException 如果collection中的元素为空,抛出该异常
*/
@Override
public boolean retainAll(Collection c) {
Objects.requireNonNull(c);
//调用封装好的批量删除的方法，这里传入的参数为true的时候，保留的是交集
return batchRemove(c, true);
}

/**
* 批量删除的方法
* @param c 需要和原集合进行对比的collection对象
* @param complement 为false的时候，删除交集，为true的时候，取交集，删除其他
* @return
*/
private boolean batchRemove(Collection c, boolean complement) {
//下面我写了一个小例子帮助大家理解
//假设原集合数组为{1,2,3,4}，c为{2,3}
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
//size = 4
for (; r < size; r++) {
//a.当complement为false，r = 0 和 3 的时候会进入循环
//b.当complement为true，r = 1 和 2 的时候会进入循环
if (c.contains(elementData[r]) == complement) {
//r = 0 w = 0 elementData[0] = elementData[0] {1,2,3,4}
//r = 3 w = 1 elementData[1] = elementData[3] {1,4,3,4}
// r = 1 w = 0 elementData[0] = elementData[1] {2,2,3,4}
//r = 2 w = 1 elementData[1] = elementData[2] {2,3,3,4}
elementData[w++] = elementData[r];
}
}
} finally {
//如果contains方法使用过程报异常,将剩余的元素赋给该集合，如果不出现异常的话，是不会进入这个代码块的
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size – r);
w += size – r;
}
// w = 2
if (w != size) {
for (int i = w; i < size; i++) {
//a. elementData[2] = null, elementData[3] = null {1,4,null,null},null元素会被垃圾回收器回收么？
//b. elmentData[2] = null, elementData[3] = null {2,3,null,null}
elementData[i] = null;
}
//修改次数+2
modCount += size – w;
//当前的数组数量就是符合条件的元素数量
size = w;
//返回操作成功的标志
modified = true;
}
}
return modified;
}
“`

### 问题十六：简单介绍一下Map吧

**答：**

`Map`是一个接口，代表的是将键映射到值的对象。一个映射不能包含重复的键，每个键最多只能映射到一个值。

`Map` 接口提供了三种`collection`视图，允许以**键集、值集或键-值映射关系集**的形式查看某个映射的内容。映射*顺序* 定义为迭代器在映射的 `collection` 视图上返回其元素的顺序。某些映射实现可明确保证其顺序，如 `TreeMap` 类；另一些映射实现则不保证顺序，如 `HashMap` 类。

### 问题十七：Map和Lambda结合可以碰撞出什么样的火花

**答：**

#### 遍历：

“`java
/**
* 遍历集合，这里的参数是一个函数式接口，可以结合Lambda表达式去优雅的使用
* @param action 进行的操作，函数式接口
*/
default void forEach(BiConsumer action) {
Objects.requireNonNull(action);
//其实本质上还是用entrySet()获取键值对后进行遍历的
for (Entry entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}
“`
####排序

“`java
/**
* 根据映射的键进行排序
*/
public static , V> Comparator> comparingByKey() {
return (Comparator> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}

/**
* 通过指定的比较器根据映射的键进行排序
*/
public static Comparator> comparingByKey(Comparator cmp) {
Objects.requireNonNull(cmp);
return (Comparator> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
“`

首先来说的是`Map`的子接口`Entry`中的`comparingByKey()`方法，这个方法所起到的作用是按照映射的键进行排序，我们接下来来看一下怎么取用：

“`java
public class Test {
public static void main(String[] args) {
Map map = new HashMap();
map.put(“A”,”test1″);
map.put(“B”,”test2″);
map.put(“E”,”test5″);
map.put(“D”,”test4″);
map.put(“C”,”test3″);
Stream> sorted = map.entrySet().stream().sorted(Map.Entry.comparingByKey());
Stream> sorted2 = map.entrySet().stream().sorted(Map.Entry.comparingByKey(String::compareTo));
sorted.forEach(entry -> System.out.println(entry.getValue()));
System.out.println(“===============”);
sorted2.forEach(entry -> System.out.println(entry.getValue()));
}
}

“`

输出结果为：

“`
test1
test2
test3
test4
test5
===============
test1
test2
test3
test4
test5
“`

#### 替换：

“`java
/**
* 对映射中的所有键值对执行计算，并将返回结果作为value覆盖
* map.replaceAll((k,v)->((String)k).length());
* @param function 执行的操作，函数式接口
*/
default void replaceAll(BiFunction function) {
…
}

/**
* 当且仅当 key 存在，并且对应值与 oldValue 不相等，才用 newValue 作为 key 的新相关联值，返回值为是否进行了替换。
* @param key 与指定值相关联的键
* @param oldValue 预期与指定键相关联的值
* @param newValue 与指定键相关联的值
* @return 如果该值被替换，返回true
*/
default boolean replace(K key, V oldValue, V newValue) {
…
}

/**
* 只有当目标映射到某个值时，才能替换指定键的条目。
* @param key 与指定值相关联的键
* @param value 与指定键相关联的值
* @return 与指定键相关联的上一个值，如果没有键的映射，返回null
*/
default V replace(K key, V value) {
…
}
“`

demo：

“`java
public static void main(String[] args) {
Map map = new HashMap();
map.put(“A”,”test1″);
map.put(“B”,”test2″);
map.replaceAll((s, s2) -> {
return s + s2;
});
printMap(map);
map.replace(“A”,”test1″);
printMap(map);
map.replace(“A”,”test2″,”test1″);
printMap(map);
map.replace(“A”,”test1″,”test2″);
printMap(map);
}

public static void printMap(Map map){
map.forEach((key, value) -> System.out.print(key + “:” + value + ” “));
System.out.println();
}
“`

打印结果：

“`java
A:Atest1 B:Btest2
A:test1 B:Btest2
A:test1 B:Btest2
A:test2 B:Btest2
“`

#### compute：

“`java
/**
* 如果指定的键尚未与值相关联（或映射到null），则尝试使用给定的映射函数计算其值，并将其输入到此映射中，除非null 。
* @param key 指定值与之关联的键
* @param mappingFunction 计算值的函数
* @return 与指定键相关联的当前（现有或计算）值，如果计算值为空，则为null
*/
default V computeIfAbsent(K key, Function mappingFunction) {
…
}

/**
* 如果指定的key的值存在且非空，则尝试计算给定键及其当前映射值的新映射。
* @param key 指定值与之关联的键
* @param remappingFunction 计算值的函数
* @return 与指定键相关的新值，如果没有则为null
*/
default V computeIfPresent(K key, BiFunction remappingFunction) {
…
}

/**
* 尝试计算指定key及其当前映射值的映射（如果没有当前映射，则null ）。
* @param key 指定值与之关联的键
* @param remappingFunction 计算值的函数
* @return 与指定键相关的新值，如果没有则为null
*/
default V compute(K key, BiFunction remappingFunction) {
…
}

“`

现在，我们来看一下，这三个方法是怎么用的，以及他们的不同。

“`java
public static void main(String[] args) {
Map map = new HashMap();
map.put(“A”,”test1″);
map.put(“B”,”test2″);
map.compute(“A”, (key, value) -> { return key + value;});
printMap(map);
//因为，集合中存在“A”，所以这里没有进行相应的操作
map.computeIfAbsent(“A”, (key) -> { return key + 2;});
printMap(map);
//这里因为集合中不存在“C”，所以进行了赋值的操作
map.computeIfAbsent(“C”, (key) -> { return key + 2;});
printMap(map);
//这里由于集合存在“A”，根据方法定义，会计算后返回给原值
map.computeIfPresent(“A”, (key, value) -> { return key + value;});
printMap(map);
//这里由于不存在“D”，根据方法定义，不做任何操作
map.computeIfPresent(“D”, (key, value) -> { return key + value;});
printMap(map);
}

public static void printMap(Map map){
map.forEach((key, value) -> System.out.print(key + “:” + value + ” “));
System.out.println();
}
“`

输出结果：

“`java
A:Atest1 B:test2
A:Atest1 B:test2
A:Atest1 B:test2 C:C2
A:AAtest1 B:test2 C:C2
A:AAtest1 B:test2 C:C2
“`

#### Others

“`java
/**
* 如果key在集合中的value为空或则键值对不存在，则用参数value覆盖
* @param key 如果key存在且不为null，返回key对应的value，如果不存在，调用put(key,value)
* @param value 如果key对应的值不存在或者为null，将该value与key进行对应
* @return 返回的是被替代的值
*/
default V putIfAbsent(K key, V value) {
…
}

/**
* key 与 value 都匹配时才删除。
* @param key 被删除的映射关系的key
* @param value 被删除的映射关系的value
* @return 返回的是否删除成功
*/
default boolean remove(Object key, Object value) {
…
}

/**
* 如果指定的键尚未与值相关联或与null相关联，则将其与给定的非空值相关联。
* @param key 结合值与之关联的键
* @param value 要与与key相关联的现有值合并的非空值，或者如果没有现有值或空值与key相关联，则与该key相关联
* @param remappingFunction 重新计算值（如果存在）的功能
* @return 与指定键相关联的新值，如果没有值与该键相关联，则返回null
*/
default V merge(K key, V value,
BiFunction remappingFunction) {

}
“`

接下来，我们接着来看一个例子：

“`java
public static void main(String[] args) {
Map map = new HashMap();
map.put(“A”,”test1″);
map.put(“B”,”test2″);
map.putIfAbsent(“A”,”test2″);
map.putIfAbsent(“C”,”test3″);
printMap(map);
map.remove(“A”,”test1″);
printMap(map);
map.merge(“A”,”test1″,(oldValue, newValue) ->{
return oldValue + newValue;
} );
printMap(map);
map.merge(“A”,”test4″,(oldValue, newValue) ->{
return newValue;
} );
printMap(map);
}
“`

输出的是：

“`java
A:test1 B:test2 C:test3
B:test2 C:test3
A:test1 B:test2 C:test3
A:test4 B:test2 C:test3
“`

### 问题十八：Set 的源码你了解多少

**答：**

`Set`继承了`Collection`接口，它本身也是一个接口，代表一种不能拥有重复元素的容器类型，更确切的说，集合不包含一对元素`e1`和`e2` ，使得`e1.equals(e2)` 。

通过`Set`的一些实现，我们可以发现，`Set`是基于`Map`进行实现的，所以`Set`取值时不保证数据和存入的时候顺序一致，并且不允许空值，不允许重复值。下面我们来看一下`Set`都给我们提供了哪些方法。

首先，`Set`提供一些关于本身属性的接口：

“`java
/**
* 返回 set 中的元素个数
* @return set中元素个数
*/
int size();

/**
* 如果set中不包含任何元素，返回true
* @return 如果set中不包含任何元素，返回true
*/
boolean isEmpty();
“`

当然，也提供了去该集合中查询元素是否存在的接口：

“`java
/**
* 如果set包含指定的元素，则返回 true
* @param o 指定的元素
* @return 如果 set 包含指定的元素，则返回 true。
*/
boolean contains(Object o);

/**
* 如果此 set 包含指定 collection 的所有元素，则返回 true。
* 如果指定的 collection 也是一个 set，那么当该 collection 是此 set 的 子集 时返回 true。
* @param c 检查是否包含在此 set 中的 collection
* @return 如果此 set 包含指定 collection 中的所有元素，则返回 true
*/
boolean containsAll(Collection c);
“`

对于元素进行结构性操作的接口也有几个，这里需要注意的是，在添加元素的时候，如果该元素在集合中已经存在，会导致添加失败并返回一个false。

“`java
/**
* 如果 set 中尚未存在指定的元素，则添加此元素
* @param e 被添加的元素
* @return 如果set中存在该元素，添加失败并返回false
*/
boolean add(E e);

/**
* 如果 set 中没有指定 collection 中的所有元素，则将其添加到此 set 中
* 如果指定的 collection 也是一个 set，则 addAll 操作会实际修改此 set，
* 这样其值是两个 set 的一个 并集。如果操作正在进行的同时修改了指定的 collection，则此操作的行为是不确定的。
* @param c
* @return
*/
boolean addAll(Collection c);

/**
* 如果 set 中存在指定的元素，则将其移除（可选操作）。
* @param o 被删除的元素
* @return 如果此 set 包含指定的对象，则返回true
*/
boolean remove(Object o);

/**
* 仅保留 set 中那些包含在指定 collection 中的元素，换句话说，只取两者交集，其余的不管
* @param c 与set进行判断的集合
* @return 如果此 set 由于调用而发生更改，则返回 true
*/
boolean retainAll(Collection c);

/**
* 移除 set 中那些包含在指定 collection 中的元素，也就是说，取交集之外的所有元素
* @param c 与set进行判断的集合
* @return 如果此 set 由于调用而发生更改，则返回 true
*/
boolean removeAll(Collection c);

/**
* 移除此 set 中的所有元素，此调用返回后该 set 将是空的。
*/
void clear();
“`

`Set`中提供了一个默认的获取可切割迭代器的一个实例，是通过`Spliterators`方法进行获取

“`java
/**
* 可切割的迭代器，返回的是该set集合的可切割迭代器的一个实例
* @return
*/
@Override
default Spliterator spliterator() {
return Spliterators.spliterator(this, Spliterator.DISTINCT);
}
“`

### 问题十九：那么AbstractSet的源码呢，有没有什么了解

**答：**

通过源码我们可以看到，`AbstractSet`中提供了三个方法的重写，分别是`equals`，`hashCode` ，`removeAll`这三个方法，`equals`和`hashCode`是如何重写的这里就不再说明，下面看看`removeAll`

“`java
/**
* 从此 set 中移除包含在指定 collection 中的所有元素
* 如果指定 collection 也是一个 set，则此操作有效地修改此 set，从而其值成为两个 set 的 不对称差集。
*
* @param c 包含将从此 set 中移除的元素的 collection
* @return 如果此 set 由于调用而发生更改，则返回 true
*/
@Override
public boolean removeAll(Collection c) {
Objects.requireNonNull(c);
boolean modified = false;
//通过在此 set 和指定 collection 上调用 size 方法，此实现可以确定哪一个更小。
if (size() > c.size()) {
// 如果此 set 中的元素更少，则该实现将在此 set 上进行迭代，依次检查迭代器返回的每个元素，查看它是否包含在指定的 collection 中。
for (Iterator i = c.iterator(); i.hasNext(); ) {
//如果包含它，则使用迭代器的 remove 方法从此 set 中将其移除。
modified |= remove(i.next());
}
} else {
//如果指定 collection 中的元素更少，则该实现将在指定的 collection 上进行迭代，并使用此 set 的 remove 方法，从此 set 中移除迭代器返回的每个元素。
for (Iterator i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}
“`

### 问题二十：最后一个问题：说说HashMap

**答：**

说起`HashMap`，大家肯定都不会陌生，我们用的最多的大概就是这个容器类来存储k-v数据，正如它的名字所说的那样，它是基于散列表实现的，散列表的强大之处在于查找时的时间复杂度为O(1)，因为每个对象都有一个对应的索引，我们可以直接根据对象的索引去访问这个对象，而这个索引就是我们对象的hash值。

在Java中散列表是通过**链表 + 数组**进行实现的，每个链表可以称之为一个桶，而对象的位置就是通过计算该对象的哈希值，然后与桶的总数（也就是HashMap的长度）取余，所得到的结果就是保存这个元素的桶的索引，如果出现两个对象具有同样的哈希值，就会出现**Hash冲突**的现象，这个时候就需要用新的对象与链表（桶）中的对象进行比较，查看这个对象是否已经存在。如果不存在，就新增一个。


但是这里遇到了一个问题，如果说桶的数量很有限（比如只有三个桶），但是数据量却很大，比如有10000个数据，这样就会导致哈希冲突非常的严重，这时，JDK 8以后的版本为我们提供了一种新的思路，当链表的长度大于8的时候，就会将后续的元素存储到红黑树（也叫平衡二叉树）当中，这样可以大大的提高我们的查询效率。

“`java
static final int TREEIFY_THRESHOLD = 8;
“`

#### 构造

首先，我们来看一下源码的构造函数
可以看出，源码中给出了四种构造函数，第一个表示的给定初始化Map长度（桶数）和装填因子的构造函数，装填因子的作用是决定何时对散列表进行再散列，比如，初始化装填因子是0.75，当表中75%的位置已经填入了元素，这个表就会用双倍的桶数进行再散列。如果没有设置初始值，就会采用默认的值（长度为16，装填因子为0.75）

“`java
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

static final int MAXIMUM_CAPACITY = 1 << 30;

static final float DEFAULT_LOAD_FACTOR = 0.75f;
“`

第四个代表的是构造一个包含该Map的HashMap对象。

#### Node

通过观察源码，我们可以发现`HashMap`是基于一个叫`Node`的内部类作为骨干来实现的，而这个内部类`Node`是`Entry`的一个实现。

`Node`的`hashCode()`方法的实现：

“`java
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
“`

这里之所以进行了异或运算，是为了让散列的更均匀，以减少哈希冲突的次数。
关于`TreeNode`是一些有关于红黑树的实现，这里不再多做篇幅进行讲解，后面会在数据结构和算法中进行详细的学习。

#### 关于GET，PUT的实现

我们首先来看一些`get()`方法的实现：

“`java
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
“`

这里可以看到，首先通过key和计算出的hash值来找到对应的Node，然后获取到该Node的Value或者是null。

“`java
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
“`

这里的hash算法也是为了让散列的更均匀，减少散列冲突的次数


这里的实现可以分为以下几步：

1. 根据传入的hash值，可以直接计算出对应的索引（n – 1）& hash。
2. 判断第一个存在的节点的key是否和查询的key相等。如果相等，直接返回该节点。
3. 对该Node进行遍历
4. 判断该集合的结构是链表还是红黑树，如果是红黑树调用内部的方法找到key对应的value。
5. 如果结构是链表，遍历获取到对应key所对应的value。

然后，我们来看`put()`方法的实现：

“`java
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
“`


首先来解释一下方法中的参数：`boolean onlyIfAbsent`表示只有在该key对应原来的value为null的时候才插入，也就是说如果value之前存在了，就不会被新put的元素覆盖。其余的流程和`get()`方法的思路有很大层度上相似，这里需要注意的有圈住的地方，

**插入成功后，要判断是否需要转换为红黑树，因为插入后链表长度加1，而`binCount`并不包含新节点，所以判断时要将临界阈值减1。当新长度满足转换条件时，调用`treeifyBin`方法，将该链表转换为红黑树。**

### 尾声

关于集合的内容到这里就告一段落了，相信看到我呕心沥血写的这**二十个问题**，一定会有很多新的收获，如果你学到了，请给我一个**点赞+关注**，这是对一个**原创者**最大的支持和帮助。

千篇一律的皮囊，万里挑一的灵魂，这里是山禾，一个不太一样的写手。