抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

集合

20.8k 字

91 分钟

次

条

摘要：本文学习了常见的集合类及相关工具类，以及如何遍历集合。

环境

Windows 10 企业版 LTSC 21H2
Java 1.8

1 概述

类图：
20250428150236-类图

所有集合类都位于java.util包下，集合类主要由Collection和Map这两个根接口派生而出：

  • 接口用蓝色表示，表示不同集合类型，是集合框架的基础。例如Collection，Map，List，Set，Iterator等。
  • 抽象类用绿色表示，对接口的部分实现。例如AbstractMap，AbstractCollection，AbstractList，AbstractSet等。
  • 实现类用黄色表示，对接口的具体实现。例如ArrayList，LinkedList，HashSet，HashMap等。

1.1 集合类

集合容器框架中主要有四大类别：List、Set、Queue、Map。

List、Set、Queue继承了Collection接口，Map是和Collection同级别的顶层接口。

1.1.1 List

List接口代表数组，允许插入重复的数据，是有序的集合，可以通过索引访问元素。

常用实现类有ArrayList和LinkedList，还有不常用的Vector。

另外，LinkedList还实现了Queue接口，因此也可以作为队列使用。

1.1.2 Set

Set接口代表集合，不允许插入重复的数据，是无序的集合。

常用实现类有HashSet、LinkedHashSet和TreeSet，HashSet是通过Map中的HashMap实现的，LinkedHashSet是HashSet的子类，TreeSet是通过Map中的TreeMap实现的。

另外，TreeSet还实现了SortedSet接口，是有序的集合。

1.1.3 Queue

Queue接口代表队列，遵循先入先出的原则，只允许在表的前端进行删除操作，而在表的后端进行插入操作。

常用实现类有LinkedList。

1.1.4 Map

Map接口代表键值对集合，是保存了key-value键值对的集合，属于双列集合，根据每个键值对的键访问值。

常用实现类有HashMap、LinkedHashMap和TreeMap，还有不常用的Hashtable。

1.2 工具类

在集合框架中，除了有集合类之外，还有两个工具类，分别是处理集合的Collections类和处理数组的Arrays类。

2 集合类

2.1 ArrayList

2.1.1 简介

最常用的集合，允许任何符合规则的元素插入，包括null和重复元素。

底层是数组结构，提供了索引机制，查找效率高，增删效率低。

线程不安全。

2.1.2 扩容

数组结构会有容量的概念，ArrayList的初始容量默认为10，负载因子是1，表示当插入元素后个数超出原有长度时会进行扩增，扩容增量是0.5，所以扩增后容量为1.5倍，可使用方法手动扩容和缩减。

最好指定初始容量值，避免过多的进行扩容操作而浪费时间和效率。

2.1.3 方法

构造方法：

java
1
2
3
4
5
6
// 空参构造器，返回默认容量为10的集合
public ArrayList();
// 指定长度的构造器，如果长度为0，则返回容量为0的集合
public ArrayList(int initialCapacity);
// 传入了一个集合的构造器，如果集合长度为0，返回容量为0的集合
public ArrayList(Collection<? extends E> c);

常用方法：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 获取个数
public int size();
// 判断是否为空
public boolean isEmpty();
// 判断是否包含指定数据
public boolean contains(Object o);
// 计算指定数据首次出现的下标
public int indexOf(Object o);
// 计算指定数据最后出现的下标
public int lastIndexOf(Object o);
// 获取指定下标的元素
public E get(int index);
// 设置指定下标的指定元素，并返回旧元素
public E set(int index, E element);
// 添加指定元素，并返回是否成功
public boolean add(E e);
// 在指定位置添加指定元素
public void add(int index, E element);
// 删除指定位置的元素，并返回删除的元素
public E remove(int index);
// 删除指定元素，并返回是否成功
public boolean remove(Object o);

2.1.4 源码

2.1.4.1 属性

属性源码：

java
1
2
3
4
5
6
7
8
9
10
// 默认的初始容量为10
private static final int DEFAULT_CAPACITY = 10;
// 空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认容量的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 数组
transient Object[] elementData;
// 元素个数
private int size;
2.1.4.2 构造方法

构造方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 空参构造器，返回默认容量为10的集合
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 指定长度的构造器，如果长度为0，则返回容量为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);
    }
}
// 传入了一个集合的构造器，如果集合长度为0，返回容量为0的集合
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // Object[]数组里的类型不一定都是Object类型的，有可能是Object的子类，所以要判断一下
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}
2.1.4.3 常用方法

常用方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
// 获取个数
public int size() {
    return size;
}
// 判断是否为空
public boolean isEmpty() {
    return size == 0;
}
// 判断是否包含指定数据
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
// 计算指定数据首次出现的下标
public int indexOf(Object o) {
    // 如果指定数据为null
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    // 如果指定数据不为null
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
// 计算指定数据最后出现的下标
public int lastIndexOf(Object o) {
    // 如果指定数据为null
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    // 如果指定数据不为null
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
// 获取指定下标的元素
public E get(int index) {
    // 检查指定下标是否越界
    rangeCheck(index);
    // 返回指定下标的元素
    return elementData(index);
}
// 设置指定下标的指定元素，并返回旧元素
public E set(int index, E element) {
    // 检查指定下标是否越界
    rangeCheck(index);
    // 设置指定元素并返回旧元素
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
// 添加指定元素，并返回是否成功
public boolean add(E e) {
    // 扩容并增加操作数
    ensureCapacityInternal(size + 1);
    // 元素个数增加并设置指定元素
    elementData[size++] = e;
    // 返回成功
    return true;
}
// 在指定位置添加指定元素
public void add(int index, E element) {
    // 检查指定下标是否越界
    rangeCheckForAdd(index);
    // 扩容并增加操作数
    ensureCapacityInternal(size + 1);
    // 拷贝数组并设置元素，增加元素个数
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}
// 删除指定位置的元素，并返回删除的元素
public E remove(int index) {
    // 检查指定下标是否越界
    rangeCheck(index);
    // 操作数自增
    modCount++;
    // 获取指定下标的元素
    E oldValue = elementData(index);
    // 需要移动的元素个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // 将最后一个元素设置为null并减少容量大小
    elementData[--size] = null;
    // 返回指定下标的元素
    return oldValue;
}
// 删除指定元素，并返回是否成功
public boolean remove(Object o) {
    // 删除null对象
    if (o == null) {
        for (int index = 0; index < size; index++)
            // 找到并删除null对象
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    // 删除非null对象
    } else {
        for (int index = 0; index < size; index++)
            // 找到并删除非null对象
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
// 快速删除指定位置元素，不检查下标，不返回数据
private void fastRemove(int index) {
    // 操作数自增
    modCount++;
    // 需要移动的元素个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // 将最后一个元素设置为null并减少容量大小
    elementData[--size] = null;
}
2.1.4.4 扩容方法

扩容方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 对集合进行扩容
public void ensureCapacity(int minCapacity) {
    // 如果集合不为空，则设置扩充值为0，如果为空，则设置扩充值为10
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
    // 如果指定容量大于扩充值，则进行扩容
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}
// 对集合进行扩容
private void ensureCapacityInternal(int minCapacity) {
    // 如果集合为空，则在默认大小和最小值之间取最大的
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 进行扩容
    ensureExplicitCapacity(minCapacity);
}
// 对集合进行扩容，实际操作
private void ensureExplicitCapacity(int minCapacity) {
    // 操作数自增
    modCount++;
    // 如果最小值大于数组长度，则进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
// 数组作为一个对象，需要一定的内存存储对象头信息，对象头信息最大占用内存不可超过8字节
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 扩容计算
private void grow(int minCapacity) {
    // 获取原容量大小
    int oldCapacity = elementData.length;
    // 右移一位，变为原来的0.5倍，然后加上原容量，扩容后变为1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果扩容后小于最小值，则设置容量为最小值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果扩容后大于最大值，则进一步设置容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 复制数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}
// 扩容后容量过大的处理方法
private static int hugeCapacity(int minCapacity) {
    // 如果最小值小于零，则表示溢出，抛出内存溢出异常
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    // 如果扩容后的值大于最大值，则使用Integer的最大值，否则就使用最大值
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
2.1.4.5 序列化方法

序列化方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 序列化
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    int expectedModCount = modCount;
    s.defaultWriteObject();
    s.writeInt(size);
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}
// 反序列化
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;
    s.defaultReadObject();
    s.readInt(); // ignored
    if (size > 0) {
        ensureCapacityInternal(size);
        Object[] a = elementData;
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}
2.1.4.6 遍历方法

ArrayList提供了两种迭代器，实现了Iterator接口的Itr类，以及实现了ListIterator接口并继承了Itr类的ListItr类。

ListItr类对Itr类的方法进行了扩展，提供了添加和修改的方法，这里只学习Itr类。

遍历方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// 获取Iterator迭代器
public Iterator<E> iterator() {
    return new Itr();
}
// Iterator内部类，实现了Iterator接口
private class Itr implements Iterator<E> {
    // 下一个元素的位置
    int cursor;
    // 最后一个元素的位置
    int lastRet = -1;
    // 预期的操作数
    int expectedModCount = modCount;
    // 是否存在下一个元素
    public boolean hasNext() {
        return cursor != size;
    }
    // 获取下一个元素
    public E next() {
        // 校验预期操作数和实际操作数
        checkForComodification();
        // 将下一个元素的位置赋值给i
        int i = cursor;
        // 如果i大于或等于集合大小，说明没有元素了，抛出异常
        if (i >= size)
            throw new NoSuchElementException();
        // 获取集合数组
        Object[] elementData = ArrayList.this.elementData;
        // 如果i大于或等于数组长度，说明有其他线程改过了，抛出异常
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        // 下一个元素位置加一
        cursor = i + 1;
        // 获取元素并返回，设置最后一个元素位置
        return (E) elementData[lastRet = i];
    }
    // 删除当前元素
    public void remove() {
        // 如果当前位置小于零，抛出异常
        if (lastRet < 0)
            throw new IllegalStateException();
        // 校验预期操作数和实际操作数
        checkForComodification();
        try {
            // 移除当前位置上的元素
            ArrayList.this.remove(lastRet);
            // 将当前位置赋值给下一个元素位置
            cursor = lastRet;
            // 将当前位置设置为-1，表示没有此位置
            lastRet = -1;
            // 同步预期操作数和操作数
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    // 循环遍历一次，JDK1.8新增方法
    @Override
    public void forEachRemaining(Consumer<? super E> consumer) {
        // 判断非空
        Objects.requireNonNull(consumer);
        // 集合容量大小
        final int size = ArrayList.this.size;
        // 将下一个元素的位置赋值给i
        int i = cursor;
        // 如果i大于或等于集合个数，则返回
        if (i >= size) {
            return;
        }
        // 获取集合数组
        final Object[] elementData = ArrayList.this.elementData;
        // 如果i大于或等于数组长度，说明有其他线程改过了，抛出异常
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        // 循环遍历，当下一个元素不为集合的大小，并且预期操作数和实际操作数相等
        while (i != size && modCount == expectedModCount) {
            // 执行方法，并且每次循环i加一
            consumer.accept((E) elementData[i++]);
        }
        // 将循环后的i赋值，导致下个元素的位置和集合长度相等，该迭代器不能再次遍历集合了
        cursor = i;
        // 设置最后一个元素位置
        lastRet = i - 1;
        // 校验预期操作数和实际操作数
        checkForComodification();
    }
    // 校验预期操作数和实际操作数
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

2.1.5 补充

2.1.5.1 数组没有private

查看ArrayList的源码，发现内部定义的elementData数组并没有像size属性一样被private修饰，表示访问权限是默认的包权限，这么做的原因被写在了声明后面的注释里，即非私有的访问权限是为了简化嵌套类的访问。

如果想知道如何简化嵌套类的访问，就需要写一个例子并反编译进一步查看。

示例：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class DemoTest {
    private int i = 1;
    public Inner inner = new Inner();
    class Inner {
        public void in() {
            i = 5;
        }
    }
    public static void main(String[] args) {
        DemoTest demoTest = new DemoTest();
        demoTest.inner.in();
        System.out.println(demoTest.i);
    }
}

反编译private修饰的代码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 在外部类的汇编代码中，多了静态方法
static int access$002(com.demo.mp.test.DemoTest, int);
  Code:
     0: aload_0
     1: iload_1
     2: dup_x1
     3: putfield      #1                  // Field i:I
     6: ireturn
  LineNumberTable:
    line 3: 0
  LocalVariableTable:
    Start  Length  Slot  Name   Signature
        0       7     0    x0   Lcom/demo/mp/test/DemoTest;
        0       7     1    x1   I
// 内部类的汇编代码中，在方法中引用外部类变量的时候，是通过静态方法设置的
public void in();
  Code:
     0: aload_0
     1: getfield      #1                  // Field this$0:Lcom/demo/mp/test/DemoTest;
     4: iconst_5
     // 通过静态方法设置
     5: invokestatic  #3                  // Method com/demo/mp/test/DemoTest.access$002:(Lcom/demo/mp/test/DemoTest;I)I
     8: pop
     9: return
  LineNumberTable:
    line 8: 0
    line 9: 9
  LocalVariableTable:
    Start  Length  Slot  Name   Signature
        0      10     0  this   Lcom/demo/mp/test/DemoTest$Inner;

反编译没有private修饰的代码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 内部类的汇编代码中，在方法中引用外部类变量的时候，是通过属性直接设置的
public void in();
  Code:
     0: aload_0
     1: getfield      #1                  // Field this$0:Lcom/demo/mp/test/DemoTest;
     4: iconst_5
     // 通过属性直接设置
     5: putfield      #3                  // Field com/demo/mp/test/DemoTest.i:I
     8: return
  LineNumberTable:
    line 8: 0
    line 9: 8
  LocalVariableTable:
    Start  Length  Slot  Name   Signature
        0       9     0  this   Lcom/demo/mp/test/DemoTest$Inner;

因此，去掉private修饰简化嵌套类的访问。

2.1.5.2 数组使用transient

查看ArrayList的源码，发现内部定义的elementData数组使用了transient修饰，transient表示该数组不参与序列化。

那ArrayList是如何实现序列化的呢？

这就涉及到了序列化的基础原理了，之前在学习输入输出流的时候，有一种对象流，主要的类是ObjectOutputStream和ObjectInputStream。

ObjectOutputStream类是用于序列化的输出流，ObjectInputStream类是用于反序列化的输入流。

在序列化和反序列化的时候，JVM会调用对象里的writeObject()方法和readObject()方法，进行用户自定义的序列化和反序列化。如果没有提供，那就调用ObjectOutputStream类的defaultWriteObject()方法和ObjectInputStream类的defaultReadObject()方法，进行默认的序列化和反序列化，这时就会忽略transient修饰的成员。

因此，在ArrayList内部自定义了writeObject()方法和readObject()方法，自定义序列化和反序列化，这么做是为了处理实际存储的元素，避免处理整个数组。

2.2 Vector

2.2.1 简介

不常用的集合，和ArrayList类似，允许任何符合规则的元素插入，包括null和重复元素。

底层是数组结构，提供了索引机制，查找效率高，增删效率低。

线程安全，使用了synchronized关键字。

2.2.2 扩容

扩容机制和ArrayList类似，初始容量默认为10，负载因子是1，表示当插入元素后个数超出原有长度时会进行扩增，扩容增量是默认为原容量，所以扩增后容量为2倍，可使用方法手动扩容和缩减。

最好指定初始容量值和增量，避免过多的进行扩容操作而浪费时间和效率。

2.2.3 方法

构造方法：

java
1
2
3
4
5
6
7
8
// 空参构造器，返回默认容量为10的集合
public Vector();
// 指定长度的构造器，默认增量为0
public Vector(int initialCapacity);
// 指定长度和增量的构造器，默认增量为0
public Vector(int initialCapacity, int capacityIncrement);
// 传入了一个集合的构造器，如果集合长度为0，返回容量为0的集合
public Vector(Collection<? extends E> c);

常用方法：

java
1
2
3
4
5
6
7
8
9
10
11
12
// 获取指定下标的元素
public synchronized E get(int index);
// 设置指定下标的指定元素，并返回旧元素
public synchronized E set(int index, E element);
// 添加元素，并返回是否成功
public synchronized boolean add(E e);
// 在指定位置添加指定元素
public void add(int index, E element);
// 删除指定位置的元素，并返回删除的元素
public synchronized E remove(int index);
// 删除元素，并返回是否成功
public boolean remove(Object o);

2.2.4 源码

2.2.4.1 属性

属性源码：

java
1
2
3
4
5
6
// 数组
protected Object[] elementData;
// 元素个数
protected int elementCount;
// 扩容增量
protected int capacityIncrement;
2.2.4.2 构造方法

构造方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 空参构造器，返回默认容量为10的集合
public Vector() {
    this(10);
}
// 指定长度的构造器，默认增量为0
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}
// 指定长度和增量的构造器，默认增量为0
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}
// 传入了一个集合的构造器，如果集合长度为0，返回容量为0的集合
public Vector(Collection<? extends E> c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    // Object[]数组里的类型不一定都是Object类型的，有可能是Object的子类，所以要判断一下
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}
2.2.4.3 常用方法

常用方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 获取指定下标的元素
public synchronized E get(int index) {
    // 检查指定下标是否越界
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    // 返回指定下标的元素
    return elementData(index);
}
// 设置指定下标的指定元素，并返回旧元素
public synchronized E set(int index, E element) {
    // 检查指定下标是否越界
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    // 设置指定元素并返回旧元素
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
// 添加元素，并返回是否成功
public synchronized boolean add(E e) {
    // 操作数自增
    modCount++;
    // 扩容
    ensureCapacityHelper(elementCount + 1);
    // 元素个数增加并设置指定元素
    elementData[elementCount++] = e;
    // 返回成功
    return true;
}
// 在指定位置添加指定元素
public void add(int index, E element) {
    insertElementAt(element, index);
}
// 删除指定位置的元素，并返回删除的元素
public synchronized E remove(int index) {
    // 操作数自增
    modCount++;
    // 检查指定下标是否越界
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    // 获取指定下标的元素
    E oldValue = elementData(index);
    // 需要移动的元素个数
    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // 将最后一个元素设置为null并减少容量大小
    elementData[--elementCount] = null;
    // 返回指定下标的元素
    return oldValue;
}
// 删除元素，并返回是否成功
public boolean remove(Object o) {
    return removeElement(o);
}
2.2.4.4 扩容方法

扩容方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 对集合进行扩容
public synchronized void ensureCapacity(int minCapacity) {
    // 如果指定容量大于扩充值，则进行扩容
    if (minCapacity > 0) {
        // 操作数自增
        modCount++;
        ensureCapacityHelper(minCapacity);
    }
}
// 对集合进行扩容
private void ensureCapacityHelper(int minCapacity) {
    // 如果最小值大于数组长度，则进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
// 数组作为一个对象，需要一定的内存存储对象头信息，对象头信息最大占用内存不可超过8字节
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 扩容计算
private void grow(int minCapacity) {
    // 获取原容量大小
    int oldCapacity = elementData.length;
    // 如果增量大于0，则使用增量，否则使用原容量作为增量，最后加上原容量作为新容量
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
    // 如果扩容后小于最小值，则设置容量为最小值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果扩容后大于最大值，则进一步设置容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 复制数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}
// 扩容后容量过大的处理方法
private static int hugeCapacity(int minCapacity) {
    // 如果最小值小于零，则表示溢出，抛出内存溢出异常
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    // 如果扩容后的值大于最大值，则使用Integer的最大值，否则就使用最大值
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

2.3 Stack

2.3.1 简介

不常用的集合，继承自Vector，允许任何符合规则的元素插入，包括null和重复元素。

同Vector类似，底层是数组结构，但通过对Vector的扩展，将数组结构倒置形成堆栈结构，使用典型的后进先出操作方式。

线程安全，使用了synchronized关键字。

2.3.2 扩容

扩容同Vector。

2.3.3 方法

构造方法：

java
1
public Stack();

常用方法：

java
1
2
3
4
5
6
7
8
9
10
// 判断是否为空
public boolean empty();
// 入栈，添加到栈顶
public E push(E item);
// 出栈，查看并删除栈顶元素
public synchronized E pop();
// 查看栈顶元素
public synchronized E peek();
// 查找元素，返回栈中首次出现下标
public synchronized int search(Object o);

2.3.4 源码

2.3.4.1 构造方法

构造方法源码：

java
1
2
public Stack() {
}
2.3.4.2 常用方法

常用方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 判断是否为空
public boolean empty() {
    // 通过Vector的size()方法判断
    return size() == 0;
}
// 入栈，添加到栈顶
public E push(E item) {
    // 实际添加到数组尾部
    addElement(item);
    return item;
}
// 出栈，查看并删除栈顶元素
public synchronized E pop() {
    E       obj;
    int     len = size();
    // 实际查看数组尾部元素
    obj = peek();
    // 实际删除数组尾部元素
    removeElementAt(len - 1);
    return obj;
}
// 查看栈顶元素
public synchronized E peek() {
    int     len = size();
    if (len == 0)
        throw new EmptyStackException();
    // 实际查看数组尾部元素
    return elementAt(len - 1);
}
// 查找元素，返回栈中首次出现下标
public synchronized int search(Object o) {
    // 实际查看元素在数组最后出现位置
    int i = lastIndexOf(o);
    if (i >= 0) {
        // 转换为栈中位置
        return size() - i;
    }
    return -1;
}

2.4 LinkedList

2.4.1 简介

允许任何符合规则的元素插入，包括null和重复元素。

底层是双向链表结构，使用双向链表代替索引，查找效率低，增删效率高。

线程不安全。

2.4.2 方法

构造方法：

java
1
2
3
4
// 空参构造器
public LinkedList();
// 传入了一个集合的构造器
public LinkedList(Collection<? extends E> c);

常用方法：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 获取个数
public int size();
// 判断是否包含指定数据
public boolean contains(Object o);
// 计算指定数据首次出现的下标
public int indexOf(Object o);
// 计算指定数据最后出现的下标
public int lastIndexOf(Object o);
// 获取指定下标的元素
public E get(int index);
// 获取首节点元素，节点不存在会抛异常
public E getFirst();
// 获取尾节点元素，节点不存在会抛异常
public E getLast();
// 设置指定下标的指定元素，并返回旧元素
public E set(int index, E element);
// 在指定位置添加指定元素
public void add(int index, E element);
// 删除指定位置的元素，并返回删除的元素
public E remove(int index);

队列方法：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 获取首节点元素，节点不存在会抛异常
public E element();
// 添加指定元素作为尾节点，并返回是否成功
public boolean add(E e);
// 添加指定元素作为首节点
public void addFirst(E e);
// 添加指定元素作为尾节点
public void addLast(E e);
// 删除同指定元素相同的第一个元素，并返回是否成功
public boolean remove(Object o);
// 删除首节点元素，并返回删除的元素，节点不存在会抛异常
public E removeFirst();
// 删除尾节点元素，并返回删除的元素，节点不存在会抛异常
public E removeLast();
// 获取首节点元素，节点不存在会返回null
public E peek();
// 获取首节点元素，节点不存在会返回null
public E peekFirst();
// 获取尾节点元素，节点不存在会返回null
public E peekLast();
// 添加指定元素作为尾节点
public boolean offer(E e);
// 添加指定元素作为首节点
public boolean offerFirst(E e);
// 添加指定元素作为尾节点
public boolean offerLast(E e);
// 删除首节点元素，并返回删除的元素，节点不存在会返回null
public E poll();
// 删除首节点元素，并返回删除的元素，节点不存在会返回null
public E pollFirst();
// 删除尾节点元素，并返回删除的元素，节点不存在会返回null
public E pollLast();

栈方法：

java
1
2
3
4
// 添加指定元素作为首节点
public void push(E e);
// 删除首节点元素，并返回删除的元素，节点不存在会抛异常
public E pop();

2.4.3 源码

2.4.3.1 属性

属性源码：

java
1
2
3
4
5
6
// 元素个数
transient int size = 0;
// 头节点
transient Node<E> first;
// 尾节点
transient Node<E> last;
2.4.3.2 构造方法

构造方法源码：

java
1
2
3
4
5
6
7
8
// 空参构造器
public LinkedList() {
}
// 传入了一个集合的构造器
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}
2.4.3.3 常用方法

常用方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// 获取个数
public int size() {
    return size;
}
// 判断是否包含指定数据
public boolean contains(Object o) {
    return indexOf(o) != -1;
}
// 计算指定数据首次出现的下标
public int indexOf(Object o) {
    int index = 0;
    // 如果指定数据为null
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    // 如果指定数据不为null
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}
// 计算指定数据最后出现的下标
public int lastIndexOf(Object o) {
    int index = size;
    // 如果指定数据为null
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    // 如果指定数据不为null
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}
// 获取指定下标的元素
public E get(int index) {
    // 检查指定下标是否越界
    checkElementIndex(index);
    // 遍历链表并获取指定下标对应的元素
    return node(index).item;
}
// 获取首节点元素，节点不存在会抛异常
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
// 获取尾节点元素，节点不存在会抛异常
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}
// 设置指定下标的指定元素，并返回旧元素
public E set(int index, E element) {
    // 检查指定下标是否越界
    checkElementIndex(index);
    // 遍历链表并获取指定下标对应的元素
    Node<E> x = node(index);
    // 获取旧元素
    E oldVal = x.item;
    // 替换元素
    x.item = element;
    // 返回旧元素
    return oldVal;
}
// 在指定位置添加指定元素
public void add(int index, E element) {
    // 检查指定下标是否越界
    checkPositionIndex(index);
    // 如果指定位置为末尾，则直接末尾插入
    if (index == size)
        linkLast(element);
    // 如果指定位置不为末尾，则插入到该位置所在的元素前面
    else
        linkBefore(element, node(index));
}
// 删除指定位置的元素，并返回删除的元素
public E remove(int index) {
    // 检查指定下标是否越界
    checkElementIndex(index);
    // 找到指定位置的元素并删除
    return unlink(node(index));
}
2.4.3.4 队列方法

队列方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// 获取首节点元素，节点不存在会抛异常
public E element() {
    return getFirst();
}
// 添加指定元素作为尾节点，并返回是否成功
public boolean add(E e) {
    linkLast(e);
    return true;
}
// 添加指定元素作为首节点
public void addFirst(E e) {
    linkFirst(e);
}
// 添加指定元素作为尾节点
public void addLast(E e) {
    linkLast(e);
}
// 删除同指定元素相同的第一个元素，并返回是否成功
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
// 删除首节点元素，并返回删除的元素，节点不存在会抛异常
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
// 删除尾节点元素，并返回删除的元素，节点不存在会抛异常
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
// 获取首节点元素，节点不存在会返回null
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
// 获取首节点元素，节点不存在会返回null
public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
// 获取尾节点元素，节点不存在会返回null
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}
// 添加指定元素作为尾节点
public boolean offer(E e) {
    return add(e);
}
// 添加指定元素作为首节点
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}
// 添加指定元素作为尾节点
public boolean offerLast(E e) {
    addLast(e);
    return true;
}
// 删除首节点元素，并返回删除的元素，节点不存在会返回null
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
// 删除首节点元素，并返回删除的元素，节点不存在会返回null
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
// 删除尾节点元素，并返回删除的元素，节点不存在会返回null
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}
2.4.3.5 栈方法

栈方法源码：

java
1
2
3
4
5
6
7
8
// 入栈，添加指定元素作为首节点
public void push(E e) {
    addFirst(e);
}
// 出栈，删除首节点元素，并返回删除的元素，节点不存在会抛异常
public E pop() {
    return removeFirst();
}

2.5 HashSet

2.5.1 简介

不允许重复的元素插入，可以插入null。

底层是HashMap，不能保证插入和输出的顺序一致。

线程不安全。

2.5.2 扩容

扩容同HashMap。

2.5.3 方法

构造方法：

java
1
2
3
4
5
6
7
8
9
10
// 空参构造器，调用HashMap的构造器
public HashSet();
// 指定长度的构造器，调用HashMap的构造器
public HashSet(int initialCapacity);
// 指定长度和负载因子的构造器，调用HashMap的构造器
public HashSet(int initialCapacity, float loadFactor);
// 传入了一个集合的构造器，调用HashMap的构造器，添加指定集合
public HashSet(Collection<? extends E> c);
// 指定长度和负载因子的构造器，调用LinkedHashMap的构造器
HashSet(int initialCapacity, float loadFactor, boolean dummy);

常用方法：

java
1
2
3
4
5
6
7
8
9
10
11
12
// 获取个数
public int size();
// 判断是否为空
public boolean isEmpty();
// 判断是否包含指定数据
public boolean contains(Object o);
// 添加元素，并返回是否成功
public boolean add(E e);
// 删除元素，并返回是否成功
public boolean remove(Object o);
// 清除所有元素
public void clear();

2.5.4 源码

2.5.4.1 属性

属性源码：

java
1
2
3
4
// 使用HashMap存储数据
private transient HashMap<E,Object> map;
// 定义Object对象作为HashMap的value
private static final Object PRESENT = new Object();
2.5.4.2 构造方法

构造方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 空参构造器，调用HashMap的构造器
public HashSet() {
    map = new HashMap<>();
}
// 指定长度的构造器，调用HashMap的构造器
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}
// 指定长度和负载因子的构造器，调用HashMap的构造器
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
// 传入了一个集合的构造器，调用HashMap的构造器，添加指定集合
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}
// 指定长度和负载因子的构造器，调用LinkedHashMap的构造器
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
2.5.4.3 常用方法

常用方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 获取个数
public int size() {
    return map.size();
}
// 判断是否为空
public boolean isEmpty() {
    return map.isEmpty();
}
// 判断是否包含指定数据
public boolean contains(Object o) {
    return map.containsKey(o);
}
// 添加元素，并返回是否成功
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
// 删除元素，并返回是否成功
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
// 清除所有元素
public void clear() {
    map.clear();
}

2.6 LinkedHashSet

2.6.1 简介

不允许重复的元素插入，可以插入null。

继承自HashSet，底层是LinkedHashMap，维护了数据的插入顺序。

线程不安全。

2.6.2 扩容

扩容同LinkedHashMap。

2.6.3 方法

构造方法：

java
1
2
3
4
5
6
7
8
// 指定长度和负载因子的构造器，调用HashSet的构造器
public LinkedHashSet(int initialCapacity, float loadFactor);
// 指定长度的构造器，调用HashSet的构造器
public LinkedHashSet(int initialCapacity);
// 空参构造器，调用HashSet的构造器
public LinkedHashSet();
// 传入了一个集合的构造器，调用HashSet的构造器，添加指定集合
public LinkedHashSet(Collection<? extends E> c);

常用方法同HashSet。

2.6.4 源码

2.6.4.1 属性

属性同HashSet。

2.6.4.2 构造方法

构造方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 指定长度和负载因子的构造器，调用HashSet的构造器
public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}
// 指定长度的构造器，调用HashSet的构造器
public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}
// 空参构造器，调用HashSet的构造器
public LinkedHashSet() {
    super(16, .75f, true);
}
// 传入了一个集合的构造器，调用HashSet的构造器，添加指定集合
public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}
2.6.4.3 常用方法

常用方法同HashSet。

2.7 TreeSet

2.7.1 简介

不允许重复的元素插入，不可以插入null。

底层TreeMap，使用二叉树结构存储数据，支持自然排序和定制排序。

线程不安全。

2.7.2 扩容

扩容同TreeMap。

2.7.3 方法

构造方法：

java
1
2
3
4
5
6
7
8
9
10
// 指定NavigableMap的构造器
TreeSet(NavigableMap<E,Object> m);
// 空参构造器，调用TreeMap的构造器
public TreeSet();
// 指定比较器的构造器，调用TreeMap的构造器
public TreeSet(Comparator<? super E> comparator);
// 传入了一个集合的构造器，调用空参的构造器，添加指定集合
public TreeSet(Collection<? extends E> c);
// 传入了一个有序集合的构造器，调用指定比较器的构造器，添加指定集合
public TreeSet(SortedSet<E> s);

常用方法：

java
1
2
3
4
5
6
7
8
9
10
11
12
// 获取个数
public int size();
// 判断是否为空
public boolean isEmpty();
// 判断是否包含指定数据
public boolean contains(Object o);
// 添加元素，并返回是否成功
public boolean add(E e);
// 删除元素，并返回是否成功
public boolean remove(Object o);
// 清除所有元素
public void clear();

2.7.4 源码

2.7.4.1 属性

属性源码：

java
1
2
3
4
// 使用NavigableMap存储数据
private transient NavigableMap<E,Object> m;
// 定义Object对象作为NavigableMap的value
private static final Object PRESENT = new Object();
2.7.4.2 构造方法

构造方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 指定NavigableMap的构造器
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
// 空参构造器，调用TreeMap的构造器
public TreeSet() {
    this(new TreeMap<E,Object>());
}
// 指定比较器的构造器，调用TreeMap的构造器
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
// 传入了一个集合的构造器，调用空参的构造器，添加指定集合
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}
// 传入了一个有序集合的构造器，调用指定比较器的构造器，添加指定集合
public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}
2.7.4.3 常用方法

常用方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 获取个数
public int size() {
    return m.size();
}
// 判断是否为空
public boolean isEmpty() {
    return m.isEmpty();
}
// 判断是否包含指定数据
public boolean contains(Object o) {
    return m.containsKey(o);
}
// 添加元素，并返回是否成功
public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}
// 删除元素，并返回是否成功
public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}
// 清除所有元素
public void clear() {
    m.clear();
}

2.8 HashMap

2.8.1 简介

不允许插入key值相同的元素，允许插入null的key值。

底层由数组、链表、红黑树组成，数组中存储链表或红黑树，将一个key到value的映射作为一个元素，不能保证插入顺序和输出顺序一致。

线程不安全。

2.8.2 扩容

数组结构会有容量的概念，HashMap的默认容量为16，默认负载因子是0.75，表示当插入元素后个数超出长度的0.75倍时会进行扩增，默认扩容增量是1，所以扩增后容量为2倍。

最好指定初始容量值，避免过多的进行扩容操作而浪费时间和效率。

2.8.3 方法

构造方法：

java
1
2
3
4
5
6
7
8
// 指定长度和负载因子的构造器
public HashMap(int initialCapacity, float loadFactor);
// 指定长度的构造器，使用默认负载因子
public HashMap(int initialCapacity);
// 空参构造器，使用默认负载因子
public HashMap();
// 传入了一个集合的构造器，使用默认负载因子，添加指定集合
public HashMap(Map<? extends K, ? extends V> m);

常用方法：

java
1
2
3
4
5
6
7
8
9
10
11
12
// 获取个数
public int size();
// 判断是否为空
public boolean isEmpty();
// 根据key获取value，不存在会返回null
public V get(Object key);
// 设置key和value键值对，返回原value，不存在会返回null
public V put(K key, V value);
// 根据key删除键值对，返回原value，不存在会返回null
public V remove(Object key);
// 清除所有元素
public void clear();

2.8.4 源码

2.8.4.1 属性

静态属性源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
// 默认容量为16，是2的整数次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量是2的30次方，传入容量过大将被这个值替换
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 树化阈值为8，链表中元素的个数超过8时会转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 反树化阈值为6，红黑树中元素的个数小于6时会转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 树化时哈希表最小的容量为64，为了避免冲突，该值至少为树化阈值和4的乘积
static final int MIN_TREEIFY_CAPACITY = 64;

普通属性源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
// 数组，用于存储链表和红黑树
transient Node<K,V>[] table;
// 存储key和value键值对的集合
transient Set<Map.Entry<K,V>> entrySet;
// 键值对的个数
transient int size;
// 修改次数，用于快速失败机制
transient int modCount;
// 扩容阈值
int threshold;
// 负载因子
final float loadFactor;
2.8.4.2 工具方法

工具方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 根据key的hashCode重新计算hash值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 根据长度计算阈值
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
2.8.4.3 构造方法

构造方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 指定长度和负载因子的构造器
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    this.loadFactor = loadFactor;
    // 根据长度设置阈值
    this.threshold = tableSizeFor(initialCapacity);
}
// 指定长度的构造器，使用默认负载因子
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 空参构造器，使用默认负载因子
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}
// 传入了一个集合的构造器，使用默认负载因子，添加指定集合
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
2.8.4.4 常用方法

常用方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
// 获取个数
public int size() {
    return size;
}
// 判断是否为空
public boolean isEmpty() {
    return size == 0;
}
// 根据key获取value，不存在会返回null
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 根据key获取节点
final Node<K,V> getNode(int hash, Object key) {
    // 节点数组tab，数组首节点first，目标节点e，数组长度n，目标节点key值k
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 赋值并判断，如果数组已初始化，并且数组首节点不为空，才获取元素
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        // 判断数组首节点的key和value是否满足，满足则返回数组首节点
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 数组首节点不满足，赋值并遍历链表和红黑树
        if ((e = first.next) != null) {
            // 如果是红黑树节点，则通过红黑树节点方式查询
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 如果是链表节点，则遍历链表节点查询
            do {
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
// 设置key和value键值对，返回原value，不存在会返回null
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
// 设置key和value键值对，返回原value，不存在会返回null
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 节点数组tab，指针节点p，数组长度n，数组位置i
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 赋值并判断，如果数组未初始化，则初始化数组
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length
    // 如果数组已初始化，并且指针节点不存在，则创建新节点存储key和value
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 如果数组已初始化，并且指针节点存在，则查找key值相同节点并替换value
    else {
        // 目标节点e，目标节点key值k
        Node<K,V> e; K k;
        // 判断指针节点的key和value是否满足，满足则将指针节点作为目标节点
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 指针节点不满足，并且是红黑树节点，遍历红黑树并返回目标节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 指针节点不满足，并且是链表节点，遍历链表并返回目标节点
        else {
            // 记录链表节点个数并遍历链表
            for (int binCount = 0; ; ++binCount) {
                // 将下一节点作为目标节点，不存在则表示遍历完成且不存在目标节点
                if ((e = p.next) == null) {
                    // 创建新节点存储key和value
                    p.next = newNode(hash, key, value, null);
                    // 如果新增后链表节点个数超过树化阈值，则尝试进行树化操作
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 此时目标节点不存在，跳出循环
                    break;
                }
                // 遍历过程中，找到满足的目标节点
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    // 此时目标节点存在，跳出循环
                    break;
                // 将目标节点作为新的指针节点进入循环
                p = e;
            }
        }
        // 如果目标节点存在，不需要个数自增和扩容，替换value并返回原值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 执行到这里，说明增加了新节点，操作数自增
    ++modCount;
    // 个数自增，如果自增后的个数超过了阈值则进行扩容
    if (++size > threshold)
        resize();
    // 添加新节点之后的后置处理
    afterNodeInsertion(evict);
    // 返回null
    return null;
}
// 根据key删除键值对，返回原value，不存在会返回null
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
// 根据key删除键值对，并返回原节点
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    // 节点数组tab，指针节点p，数组长度n，数组位置index
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 赋值并判断，如果数组已初始化，并且数组首节点不为空，才删除元素
    if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
        // 原节点node，目标节点e，目标节点key值k，目标节点value值v
        Node<K,V> node = null, e; K k; V v;
        // 判断指针节点的key和value是否满足，满足则将指针节点作为原节点
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 将指针节点下一节点作为目标节点，如果目标节点存在则继续遍历节点
        else if ((e = p.next) != null) {
            // 如果指针节点是红黑树节点，则通过红黑树节点方式查询原节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // 如果指针节点是链表节点，则通过链表节点方式查询原节点
            else {
                do {
                    // 遍历过程中，找到满足的目标节点
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        // 将目标节点作为原节点
                        node = e;
                        // 此时原节点存在，跳出循环
                        break;
                    }
                    // 用指针节点保存目标节点，跳出循环时，指针节点保存的是目标节点的上一节点
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 原节点存在，并且满足value值的判断规则，那就继续执行
        if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
            // 如果原节点是红黑树节点，则通过红黑树节点方式删除原节点
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 如果原节点是链表节点，并且原节点和指针节点相同，则将原节点的下一节点作为数组首节点
            else if (node == p)
                tab[index] = node.next;
            // 如果原节点是链表节点，并且原节点和指针节点不同，则将原节点的下一节点作为指针节点的下一节点
            else
                p.next = node.next;
            // 执行到这里，说明删除了原节点，操作数自增
            ++modCount;
            // 个数自减
            --size;
            afterNodeRemoval(node);
            // 返回原节点
            return node;
        }
    }
    return null;
}
// 清除所有元素
public void clear() {
    // 定义节点数组tab
    Node<K,V>[] tab;
    // 操作数自增
    modCount++;
    // 如果数组已初始化，则设置个数为0，并且将每个节点置空
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}
2.8.4.5 扩容方法

扩容方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
final Node<K,V>[] resize() {
    // 记录原节点数组
    Node<K,V>[] oldTab = table;
    // 记录原数组容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 记录原阈值
    int oldThr = threshold;
    // 定义新数组容量，定义新数组阈值
    int newCap, newThr = 0;
    // 如果原容量大于0，则进行扩容
    if (oldCap > 0) {
        // 如果原容量大于等于容量最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 将原阈值设为整数最大值，并返回原数组
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 原容量扩容一倍并赋值给新容量，如果新容量小于容量最大值，并且原容量大于等于默认容量
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 将原阈值扩容一倍并赋值给新阈值
            newThr = oldThr << 1;
    }
    // 原容量为0，判断原阈值是否大于0
    else if (oldThr > 0)
        // 首次初始化，将原阈值赋值给新容量
        newCap = oldThr;
    // 原容量为0，并且原阈值也是0
    else {
        // 设置默认容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 设置默认阈值
        newThr = (int)(DEFAULT_LOAD_FACTOR *DEFAULT_INITIAL_CAPACITY);
    }
    // 判断新阈值是否为0
    if (newThr == 0) {
        // 计算新阈值
        float ft = (float)newCap* loadFactor;
        // 新容量小于容量最大值并且阈值小于容量最大值，则使用新阈值，否则使用最大值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    // 确定新阀值
    threshold = newThr;
    // 开始构造新的节点数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 如果原节点数组已初始化，则将原节点放置到新节点数组
    if (oldTab != null) {
        // 遍历原节点数组
        for (int j = 0; j < oldCap; ++j) {
            // 定义原节点
            Node<K,V> e;
            // 如果原节点不为空，记录原节点并移动
            if ((e = oldTab[j]) != null) {
                // 将原节点置空
                oldTab[j] = null;
                // 如果原节点没有子节点，表示数组中只有一个节点，直接放置到新节点数组
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果原节点是红黑树节点，则在红黑树中将原节点存储到新节点数组
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 如果原节点是链表节点，则进行链表节点的移动
                else {
                    // 定义低位链表的头节点和尾节点
                    Node<K,V> loHead = null, loTail = null;
                    // 定义高位链表的头节点和尾节点
                    Node<K,V> hiHead = null, hiTail = null;
                    // 定义下一节点
                    Node<K,V> next;
                    // 循环遍历节点链表
                    do {
                        // 给下一节点赋值
                        next = e.next;
                        // 确定原节点在新节点数组中的位置，为0则放在低位链表
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 为1则放在高位链表
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 如果低位链表不为空，则将整个低位链表放到原位置
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 如果高位链表不为空，则将整个高位链表放到新增的空间中
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    // 返回新的节点数组
    return newTab;
}

2.8.5 补充

2.8.5.1 为什么数组长度是2的倍数

长度减一后的二进制位全为1，可以用来计算节点在数组中的位置，不会造成浪费。

如果指定长度不是2的倍数，在构造方法中的最后一步会根据指定长度计算容量，会通过移位运算得到大于等于指定长度的，并且为2的倍数的最小正整数。

2.8.5.2 为什么不直接使用equals方法比较

在Object类中有一个hashCode()方法，用来获取对象的哈希值，也被称作为散列值。

使用native修饰hashCode()方法，意味着这个方法和平台有关。大多数情况下hashCode()方法返回的是与对象信息（存储地址和字段等）有关的数值。

当向集合中插入对象时，如果调用equals()逐个进行比较，虽然可行但是这样做的效率很低。因此，先调用hashCode()进行判断，如果相同再调用equals()判断，就会提高效率。

2.8.5.3 为什么要使用hash方法处理hashCode

在计算节点在数组中的下标时，一般是通过与节点有关的数值除以数组长度取余得到的。当数组长度为2的倍数时，取余操作相当于数值同数组长度减一进行与运算。

根据数组长度减一得到的结果，将二进制位分为高位和低位，将左边全为0的部分作为高位，将右边全为1的部分作为低位。在与运算时，任何数字与0相与只能得到0，所以高位无效，只用到了低位。

如果使用hashCode进行与运算，两个hashCode不同但是低位相同的节点会被分到一个数组中，哈希碰撞发生的可能性较大。因此，需要对hashCode进行处理，使两个高位不同低位相同的节点得到的结果也不同。

可以将hash()方法称为扰动函数，是用来对hashCode进行处理的方法。在hash()方法处理后，hashCode高位的变化也会影响低位，这时再使用低位计算下标就能使元素的分布更加合理，哈希碰撞的可能性也会降低。

在JDK1.8版本中，只使用了hashCode进行了一次与运算：

java
1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
2.8.5.4 什么时候进行扩容

扩容有两个触发时机：

  • 插入第一个节点时，初始化数组时进行扩容。
  • 插入节点后，长度超过阈值时进行扩容。
2.8.5.5 如何对链表扩容

使用高低位链表，将节点的hash值同原数组长度进行与运算，根据结果0和1放到低位链表和高位链表。

将低位链表放置到新数组的低位，将高位链表放置到新数组的高位，低位的位置加上原数组长度就是高位的位置。

2.8.5.6 为什么要同时重写equals方法和hashCode方法

一般在重写equals()方法的时候，也会尽量重写hashCode()方法，就是为了在equals()方法判断相等的时候保证让hashCode()方法判断相等。

2.9 Hashtable

2.9.1 简介

不允许插入key值相同的元素，不允许插入null的key值，不允许插入null的value值。

底层由数组、链表组成，数组中存储链表，通过单链表解决哈希冲突。

线程安全，使用了synchronized关键字。

2.9.2 扩容

默认容量为11，默认负载因子是0.75，扩增后容量为2倍加1。

2.9.3 方法

构造方法：

java
1
2
3
4
5
6
7
8
// 指定长度和负载因子的构造器
public Hashtable(int initialCapacity, float loadFactor);
// 指定长度的构造器，使用默认负载因子
public Hashtable(int initialCapacity);
// 空参构造器，使用默认长度和默认负载因子
public Hashtable();
// 传入了一个集合的构造器，使用默认负载因子，添加指定集合
public Hashtable(Map<? extends K, ? extends V> t);

常用方法：

java
1
2
3
4
5
6
7
8
9
10
// 获取个数
public synchronized int size();
// 判断是否为空
public synchronized boolean isEmpty();
// 根据key获取value，不存在会返回null
public synchronized V get(Object key);
// 设置key和value键值对，返回原value，不存在会返回null
public synchronized V put(K key, V value);
// 根据key删除键值对，返回原value，不存在会返回null
public synchronized V remove(Object key);

2.9.4 源码

2.9.4.1 属性

属性源码：

java
1
2
3
4
5
6
7
8
9
10
// 数组
private transient Entry<?,?>[] table;
// 键值对的个数
private transient int count;
// 扩容阈值
private int threshold;
// 负载因子
private float loadFactor;
// 修改次数，用于快速失败机制
private transient int modCount = 0;
2.9.4.2 构造方法

构造方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 指定长度和负载因子的构造器
public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: "+loadFactor);
    if (initialCapacity==0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new Entry<?,?>[initialCapacity];
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
// 指定长度的构造器，使用默认负载因子
public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}
// 空参构造器，使用默认长度和默认负载因子
public Hashtable() {
    this(11, 0.75f);
}
// 传入了一个集合的构造器，使用默认负载因子，添加指定集合
public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}
2.9.4.3 常用方法

常用方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// 获取个数
public synchronized int size() {
    return count;
}
// 判断是否为空
public synchronized boolean isEmpty() {
    return count == 0;
}
// 根据key获取value，不存在会返回null
public synchronized V get(Object key) {
    // 定义数组
    Entry<?,?> tab[] = table;
    // 计算key的hashCode
    int hash = key.hashCode();
    // 通过key值计算元素在数组中的位置
    int index = (hash & 0x7FFFFFFF) % tab.length;
    // 如果数组中对应位置上存在元素，表示发生了哈希碰撞
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        // 如果链表中存在key值对应的元素，返回value值
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}
// 设置key和value键值对，返回原value，不存在会返回null
public synchronized V put(K key, V value) {
    // 不支持value为null的键值对，否则会抛出异常
    if (value == null) {
        throw new NullPointerException();
    }
    // 保存原数组
    Entry<?,?> tab[] = table;
    // 计算key的hashCode
    int hash = key.hashCode();
    // 通过key值计算元素在数组中的位置
    int index = (hash & 0x7FFFFFFF) % tab.length;
    // 获取数组中对应位置上的元素
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // 如果位置元素存在，表示发生了哈希碰撞
    for(; entry != null ; entry = entry.next) {
        // 如果链表中存在key值对应的元素，替换value值，返回原value值
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    // 如果没有发生了哈希碰撞，将键值对添加到数组
    addEntry(hash, key, value, index);
    return null;
}
// 添加key和value键值对
private void addEntry(int hash, K key, V value, int index) {
    // 增加操作数
    modCount++;
    // 保存原数组
    Entry<?,?> tab[] = table;
    // 如果插入前的元素个数大于等于阈值
    if (count >= threshold) {
        // 进行扩容操作
        rehash();
        // 重新保存扩容后的原数组
        tab = table;
        // 计算key的hashCode
        hash = key.hashCode();
        // 通过key值计算元素在扩容后数组中的位置
        index = (hash & 0x7FFFFFFF) % tab.length;
    }
    // 初始化数组位置
    Entry<K,V> e = (Entry<K,V>) tab[index];
    // 将键值对设置到数组位置
    tab[index] = new Entry<>(hash, key, value, e);
    // 元素个数自增
    count++;
}
// 根据key删除键值对，返回原value，不存在会返回null
public synchronized V remove(Object key) {
    // 保存原数组
    Entry<?,?> tab[] = table;
    // 计算key的hashCode
    int hash = key.hashCode();
    // 通过key值计算元素在数组中的位置
    int index = (hash & 0x7FFFFFFF) % tab.length;
    // 获取数组中对应位置上的元素
    Entry<K,V> e = (Entry<K,V>)tab[index];
    // 如果位置元素存在，尝试删除元素
    for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
        // 如果链表中存在key值对应的元素，则删除元素
        if ((e.hash == hash) && e.key.equals(key)) {
            // 操作数自增
            modCount++;
            // 上一节点存在，表示要删除的元素不是头节点
            if (prev != null) {
                prev.next = e.next;
            // 上一节点不存在，表示要删除的元素是头节点
            } else {
                tab[index] = e.next;
            }
            // 元素个数自减
            count--;
            // 保存原value值
            V oldValue = e.value;
            // 置空原value值
            e.value = null;
            // 返回原value值
            return oldValue;
        }
    }
    return null;
}
2.9.4.4 扩容方法

扩容方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 数组作为一个对象，需要一定的内存存储对象头信息，对象头信息最大占用内存不可超过8字节
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 扩容操作
protected void rehash() {
    // 保存原数组长度
    int oldCapacity = table.length;
    // 保存原数组
    Entry<?,?>[] oldMap = table;
    // 将旧容量的2倍加1作为新容量
    int newCapacity = (oldCapacity << 1) + 1;
    // 如果新容量大于最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        // 如果旧容量等于最大容量，则仍使用旧容量
        if (oldCapacity == MAX_ARRAY_SIZE)
            return;
        // 否则使用最大值作为新容量
        newCapacity = MAX_ARRAY_SIZE;
    }
    // 创建新数组
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    // 操作数自增
    modCount++;
    // 计算阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    // 使用新数组
    table = newMap;
    // 遍历原数组
    for (int i = oldCapacity ; i-- > 0 ;) {
        // 遍历原数组中的链表，计算每个元素在新数组中的位置并插入到新数组
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            // 遍历原链表
            Entry<K,V> e = old;
            old = old.next;
            // 计算元素在新数组的位置，使用头插法插入到新数组
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

2.10 LinkedHashMap

2.10.1 简介

不允许插入key值相同的元素，允许插入null的key值。

继承自HashMap，底层由数组、链表、红黑树组成。在此基础上，新增了双向链表，连接了集合中的所有节点，维护了节点的插入顺序。

线程不安全。

2.10.2 扩容

扩容同HashMap。

2.10.3 方法

构造方法：

java
1
2
3
4
5
6
7
8
9
10
// 指定长度和负载因子的构造器，调用HashMap的构造器
public LinkedHashMap(int initialCapacity, float loadFactor);
// 指定长度的构造器，调用HashMap的构造器
public LinkedHashMap(int initialCapacity);
// 空参构造器，调用HashMap的构造器
public LinkedHashMap();
// 传入了一个集合的构造器，调用HashMap的构造器，添加指定集合
public LinkedHashMap(Map<? extends K, ? extends V> m);
// 指定长度和负载因子以及遍历顺序标志位的构造器，调用HashMap的构造器
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder);

常用方法同HashMap。

2.10.4 源码

2.10.4.1 扩展节点

在LinkedHashMap中，对HashMap的节点进行了扩展，在节点中维护了插入顺序：

java
1
2
3
4
5
6
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

可以看到，仍使用next节点维护节点间的访问顺序，但新增了before节点和after节点维护节点间的插入顺序。

2.10.4.2 扩展属性

扩展属性源码：

java
1
2
3
4
5
6
// 双向链表的头节点
transient LinkedHashMap.Entry<K,V> head;
// 双向链表的尾节点
transient LinkedHashMap.Entry<K,V> tail;
// 双向链表访问顺序标志位，默认为false，true表示双向链表按访问顺序排列，false表示双向链表按插入顺序排列
final boolean accessOrder;

accessOrder用于支持LRU算法，即最近最少使用算法，是一种数据删除方法，表示删除最近一段时间内最少使用的数据。

双向链表是按时间顺序排列的，插入的数据永远在尾部，访问的数据是否要移动到尾部是通过accessOrder判断的：

当accessOrder为true时，访问的数据会被放置到双向链表尾部，表示双向链表是按照访问顺序排列的。

当accessOrder为false时，访问的数据不会被处理，表示双向链表是按照插入顺序排列的。

2.10.4.3 扩展方法

扩展方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// 重写newNode()方法，添加双向链表的处理
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    // 创建节点
    LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    // 将节点放在双向链表尾部
    linkNodeLast(p);
    // 返回节点
    return p;
}
// 将节点放在双向链表尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}
// 重写get()方法，添加双向链表的处理
public V get(Object key) {
    Node<K,V> e;
    // 根据key获取节点
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果按照访问顺序排列
    if (accessOrder)
        // 处理访问节点
        afterNodeAccess(e);
    return e.value;
}
// 处理访问节点，将访问节点移动到双向链表尾部
void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}
// 处理插入节点，尝试删除双向链表的首节点
void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
// 处理删除节点，在双向链表中删除节点
void afterNodeRemoval(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}
2.10.4.4 构造方法

构造方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 指定长度和负载因子的构造器，调用HashMap的构造器
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
// 指定长度的构造器，调用HashMap的构造器
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
// 空参构造器，调用HashMap的构造器
public LinkedHashMap() {
    super();
    accessOrder = false;
}
// 传入了一个集合的构造器，调用HashMap的构造器，添加指定集合
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}
// 指定长度和负载因子以及遍历顺序标志位的构造器，调用HashMap的构造器
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}
2.10.4.5 常用方法

常用方法同HashMap。

2.11 TreeMap

2.11.1 简介

不允许插入key值相同的元素，定制排序允许插入null的key值，自然排序不允许插入null的key值。

底层是红黑树，支持自然排序和定制排序。自然排序要求key值实现Comparable接口，定制排序要求创建TreeMap时传入Comparator对象。

线程不安全。

2.11.2 方法

构造方法：

java
1
2
3
4
5
6
7
8
// 空参构造器
public TreeMap();
// 指定比较器的构造器
public TreeMap(Comparator<? super K> comparator);
// 传入了一个集合的构造器，集合没有比较器，添加指定集合
public TreeMap(Map<? extends K, ? extends V> m);
// 传入了一个集合的构造器，集合提供比较器，添加指定集合
public TreeMap(SortedMap<K, ? extends V> m);

常用方法：

java
1
2
3
4
5
6
// 根据key获取value，不存在会返回null
public V get(Object key);
// 设置key和value键值对，返回原value，不存在会返回null
public V put(K key, V value);
// 根据key删除键值对，返回原value，不存在会返回null
public V remove(Object key);

2.11.3 源码

2.11.3.1 属性

属性源码：

java
1
2
3
4
5
6
7
8
// 自定义的比较器，用于排序
private final Comparator<? super K> comparator;
// 红黑树的根节点
private transient Entry<K,V> root;
// 节点个数
private transient int size = 0;
// 修改次数，用于快速失败机制
private transient int modCount = 0;
2.11.3.2 构造方法

构造方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 空参构造器
public TreeMap() {
    comparator = null;
}
// 指定比较器的构造器
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}
// 传入了一个集合的构造器，集合没有比较器，添加指定集合
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}
// 传入了一个集合的构造器，集合提供比较器，添加指定集合
public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}
2.11.3.3 常用方法

常用方法源码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
// 根据key获取value，不存在会返回null
public V get(Object key) {
    // 根据key查询节点
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}
// 根据key查询节点
final Entry<K,V> getEntry(Object key) {
    // 比较器存在，则使用比较器获取节点
    if (comparator != null)
        return getEntryUsingComparator(key);
    // 比较器不存在，并且key值为null，则抛异常
    if (key == null)
        throw new NullPointerException();
    // 比较器不存在，则使用key值比较
    Comparable<? super K> k = (Comparable<? super K>) key;
    // 保存红黑树的根节点
    Entry<K,V> p = root;
    // 根节点不为空，则查询红黑树并比较
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}
// 使用比较器查询key值对应的节点
final Entry<K,V> getEntryUsingComparator(Object key) {
    // 保存key值
    K k = (K) key;
    // 保存比较器
    Comparator<? super K> cpr = comparator;
    // 比较器存在，使用比较器查询
    if (cpr != null) {
        // 保存红黑树的根节点
        Entry<K,V> p = root;
        // 根节点不为空，则查询红黑树并比较
        while (p != null) {
            // 使用比较器的比较方法
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}
// 设置key和value键值对，返回原value，不存在会返回null
public V put(K key, V value) {
    // 保存红黑树的根节点
    Entry<K,V> t = root;
    // 根节点为空，则设置根节点
    if (t == null) {
        // 类型检查
        compare(key, key);
        // 创建根节点
        root = new Entry<>(key, value, null);
        // 节点大小设置为1
        size = 1;
        // 操作数自增
        modCount++;
        // 返回null
        return null;
    }
    // 定义比较的结果
    int cmp;
    // 定义父节点
    Entry<K,V> parent;
    // 保存比较器
    Comparator<? super K> cpr = comparator;
    // 比较器存在，使用比较器查询并设置键值对
    if (cpr != null) {
        // 使用比较器逐个比较节点
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 比较器不存在，使用key值比较查询并设置键值对
    else {
        // 如果key值为null，则抛异常
        if (key == null)
            throw new NullPointerException();
        // 使用key值比较
        Comparable<? super K> k = (Comparable<? super K>) key;
        // 使用key值逐个比较节点
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 创建节点
    Entry<K,V> e = new Entry<>(key, value, parent);
    // 比较的结果小于0，新节点作为父节点的左节点
    if (cmp < 0)
        parent.left = e;
    // 比较的结果大于0，新节点作为父节点的右节点
    else
        parent.right = e;
    // 节点插入后，调整红黑树的高度和颜色
    fixAfterInsertion(e);
    // 个数自增
    size++;
    // 操作数自增
    modCount++;
    // 返回null
    return null;
}
// 根据key删除键值对，返回原value，不存在会返回null
public V remove(Object key) {
    // 根据key查询节点
    Entry<K,V> p = getEntry(key);
    // 节点为null，返回null
    if (p == null)
        return null;
    // 节点不为null，删除节点
    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

3 工具类

3.1 Arrays

3.1.1 简介

Arrays工具类主要用来操作数组。

3.1.2 方法

3.1.2.1 打印

打印数组。

示例：

java
1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
    Integer[] ints = new Integer[5];
    ints[0] = 1;
    ints[1] = 6;
    ints[2] = 4;
    ints[3] = 9;
    ints[4] = 3;
    System.out.println(ints);// [Ljava.lang.Integer;@12edcd21
    System.out.println(Arrays.toString(ints));// [1, 6, 4, 9, 3]
}
3.1.2.2 排序

将数组里的元素进行排序。

示例：

java
1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {
    Integer[] ints = new Integer[5];
    ints[0] = 1;
    ints[1] = 6;
    ints[2] = 4;
    ints[3] = 9;
    ints[4] = 3;
    System.out.println(Arrays.toString(ints));// [1, 6, 4, 9, 3]
    Arrays.sort(ints);
    System.out.println(Arrays.toString(ints));// [1, 3, 4, 6, 9]
}
3.1.2.3 比较

判断两个数组是否相等。

示例：

java
1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
    Integer[] ints1 = new Integer[2];
    ints1[0] = 1;
    ints1[1] = 6;
    Integer[] ints2 = new Integer[2];
    ints2[0] = 4;
    ints2[1] = 3;
    System.out.println(Arrays.equals(ints1, ints2));// false
}
3.1.2.4 复制

复制数组。

示例：

java
1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
    Integer[] ints1 = new Integer[5];
    ints1[0] = 1;
    ints1[1] = 6;
    ints1[2] = 4;
    ints1[3] = 9;
    ints1[4] = 3;
    Integer[] ints2 = Arrays.copyOf(ints1, 3);
    System.out.println(Arrays.toString(ints2));// [1, 6, 4]
}
3.1.2.5 数组转集合

将数组转为集合。

示例：

java
1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
    Integer[] ints = new Integer[5];
    ints[0] = 1;
    ints[1] = 6;
    ints[2] = 4;
    ints[3] = 9;
    ints[4] = 3;
    List<Integer> list = Arrays.asList(ints);
    System.out.println(list);// [1, 6, 4, 9, 3]
}

3.2 Collections

3.2.1 简介

Collections工具类主要用来操作集合类，比如List和Set。

3.2.2 方法

3.2.2.1 排序

使用Collections工具类里的sort()方法进行排序，必须满足下列任意一个条件：

  • 第一种是List中的存储的元素实现Comparable接口，重写compareTo()方法。
  • 第二种是在使用sort方法时，传入一个Comparator的实现类，重写compareTo()方法。

示例：

java
1
2
3
4
5
6
7
8
List<Integer> list = new ArrayList<Integer>();
list.add(3);
list.add(5);
list.add(1);

System.out.println(list);// 
Collections.sort(list);
System.out.println(list);// [1, 3, 5]
3.2.2.2 反转

将集合里元素的顺序进行反转。

示例：

java
1
2
3
4
5
6
7
List<Integer> list = new ArrayList<Integer>();
list.add(3);
list.add(5);
list.add(1);
System.out.println(list);// [3, 5, 1]
Collections.reverse(list);
System.out.println(list);// [1, 5, 3]
3.2.2.3 混排

对集合里的元素进行随机排序。

示例：

java
1
2
3
4
5
6
7
List<Integer> list = new ArrayList<Integer>();
list.add(3);
list.add(5);
list.add(1);
System.out.println(list);// [3, 5, 1]
Collections.shuffle(list);
System.out.println(list);// [3, 1, 5]
3.2.2.4 最大

查找集合中最大的一个元素。

示例：

java
1
2
3
4
5
6
List<Integer> list = new ArrayList<Integer>();
list.add(3);
list.add(5);
list.add(1);
Integer max = Collections.max(list);
System.out.println(max);// 5
3.2.2.5 最小

查找集合中最小的一个元素。

示例：

java
1
2
3
4
5
6
List<Integer> list = new ArrayList<Integer>();
list.add(3);
list.add(5);
list.add(1);
Integer min = Collections.min(list);
System.out.println(min);// 1

3.2.3 获取线程安全的容器

创建线程安全的List：

java
1
List<Integer> list = Collections.synchronizedList(new ArrayList<Integer>());

创建线程安全的Set：

java
1
Set<Integer> set = Collections.synchronizedSet(new HashSet<Integer>());

创建线程安全的Map：

java
1
Map<String, Integer> map = Collections.synchronizedMap(new HashMap<String, Integer>());

4 遍历

4.1 遍历Collection

对List和Set的遍历，有四种方式，下面以ArrayList为例进行说明。

4.1.1 普通for循环

使用普通for循环的遍历方式效率最高，尽量将循环无关的代码放置在集合外执行。

示例：

java
1
2
3
for (int i = 0; i < list.size(); i++) {
    System.out.println(i);
}

如果要在普通for循环里对集合元素进行删除操作，可能会出现问题：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void main(String[] args) {
    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(2);
    list.add(2);
    list.add(4);
    list.add(5);
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i) == 2) {
            list.remove(i);
        }
    }
    System.out.println(list);// [1, 2, 4, 5]
}

集合中有两个值为2的元素，但是在代码执行之后，值为2的元素并没有完全移除。

在第一次删除后，集合发生了改变，删除位置之后的所有元素都向前挪动了一个位置，删除位置上的元素由下一位置上的元素替代。

在下次遍历时，从删除位置后开始判断，跳过了删除位置上的元素，从而导致最后打印的结果和预期的不一致。

改进的办法是在删除之后设置索引减1，重新判断删除位置上的元素。

4.1.2 增强for循环

进一步精简了遍历的代码，底层使用迭代器。

示例：

java
1
2
3
for (Integer i : list) {
    System.out.println(i);
}

如果在增强for循环里删除或者添加集合元素，那么一定会报异常：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void main(String[] args) {
    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(2);
    list.add(2);
    list.add(4);
    list.add(5);
    for (Integer i : list) {
        if (i == 2) {
            list.remove(i);
        }
    }
    System.out.println(list);
}

运行后会抛出java.util.ConcurrentModificationException异常。

抛出异常是由快速失败（fail-fast）机制引起的，该机制是为了避免在遍历集合时，对集合的结构进行修改。

快速失败机制使用modCount记录集合的修改次数，在删除时除了删除对应元素外，还会更新modCount。

增强for循环使用迭代器进行遍历，迭代器在初始化时会使用expectedModCount记录当时的modCount，遍历时会检查expectedModCount是否和modCount相同，如果不同就会抛出异常。

4.1.3 使用迭代器

示例：

java
1
2
3
4
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

如果在迭代器中使用集合提供的删除或添加方法，同样会报错：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) {
    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(2);
    list.add(2);
    list.add(4);
    list.add(5);
    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()) {
        if (iterator.next() == 2) {
            list.add(6);
        }
    }
    System.out.println(list);
}

运行后会抛出java.util.ConcurrentModificationException异常。

这里抛出异常的原因和增强for循环一样，同样是因为快速失败机制。

解决办法是在迭代器中删除或添加元素时，使用迭代器提供的删除或添加方法，不要使用集合提供的删除或添加方法。

需要注意的是，普通迭代器中只提供了删除方法，在集合迭代器中还提供了添加和修改方法。

4.1.4 使用集合迭代器

示例：

java
1
2
3
4
ListIterator<Integer> iterator = list.listIterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

在迭代器中使用迭代器提供的删除或添加方法：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) {
    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(2);
    list.add(2);
    list.add(4);
    list.add(5);
    ListIterator<Integer> iterator = list.listIterator();
    while (iterator.hasNext()) {
        if (iterator.next() == 2) {
            iterator.remove();
        }
    }
    System.out.println(list);// [1, 4, 5]
}

迭代器提供的方法同时维护了modCount和expectedModCount，所以不会产生快速失败。

4.1.5 使用forEach方法

forEach方法是JDK1.8新增的方法，需要配合Lambda表达式使用。

示例：

java
1
list.forEach(i -> System.out.println(i));

使用forEach方法遍历：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void main(String[] args) {
    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(2);
    list.add(2);
    list.add(4);
    list.add(5);
    list.forEach(i -> {
        if (i == 2) {
            list.remove(i);
        }
    });
    System.out.println(list);
}

运行后会抛出java.util.ConcurrentModificationException异常。

这里抛出异常的原因也是因为快速失败机制。

4.2 遍历Map

对Map的遍历，有四种方式，下面以HashMap为例进行说明。

4.2.1 通过keySet()方法遍历key和value

通过keySet()方法获取到map的所有key值，遍历key值的集合，获取对应的value值。

示例：

java
1
2
3
for (Integer i : map.keySet()) {
    System.out.println(i + " >>> " + map.get(i));
}

结果：

java
1
2
3
4
5
0 >>> 000
1 >>> 111
2 >>> 222
3 >>> 333
4 >>> 444

在遍历的时候是可以修改的，但是不能添加和删除，否则会抛出ConcurrentModificationException异常。

示例：

java
1
2
3
4
5
6
for (Integer i : map.keySet()) {
    System.out.println(i + " >>> " + map.get(i));
    if (map.get(i) == "222") {
        map.put(i, "999");
    }
}

结果：

java
1
2
3
4
5
0 >>> 000
1 >>> 111
2 >>> 999
3 >>> 333
4 >>> 444

4.2.2 通过entrySet()方法遍历key和value

这种方式同样支持修改，但不支持添加和删除，这种方式的效率最高。

示例：

java
1
2
3
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " >>> " + entry.getValue());
}

4.2.3 通过entrySet()方法获取迭代器遍历key和value

这种方式同样支持修改，但不支持添加和删除。

示例：

java
1
2
3
4
5
Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<Integer, String> entry = iterator.next();
    System.out.println(entry.getKey() + " >>> " + entry.getValue());
}

4.2.4 通过values()方法遍历所有的value

这种方式只能遍历value，不能遍历key。

示例：

java
1
2
3
for (String value : map.values()) {
    System.out.println(value);
}

5 失败机制

5.1 快速失败机制

快速失败机制，即fail-fast机制，直接在容器上进行遍历，在遍历过程中一旦发现集合的结构发生改变，就会抛出ConcurrentModificationException异常导致遍历失败。

在java.util包下的集合类都是快速失败机制的，常见的的使用fail-fast方式遍历的容器有ArrayList和HashMap等。

fail-fast机制不能保证在不同步的修改下一定会抛出异常，它只是尽最大努力抛出，因此这种机制一般用于检测BUG。

5.1.1 复现

触发fail-fast机制的案例：

java
1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("00");
    list.add("11");
    list.add("22");
    for (String s : list) {
        if ("00".equals(s)) {
            list.add("99");
        }
    }
}

此处只是列举了一个普通案例，实际上在List、Set、Map中都会发生，并且在单线程和多线程环境下都会发生。

5.1.2 原因

fail-fast机制在单线程和多线程环境中均可发生，倘若在迭代遍历过程中检测到集合结构有变化，就有可能触发并抛出异常。

想要理解fail-fast机制，就需要查看底层源码的逻辑，因为引发fail-fast机制的原理是一样的，本文以ArrayList为例进行分析。

查看ArrayList的迭代器方法：

java
1
2
3
public Iterator<E> iterator() {
    return new Itr();
}

继续查看ArrayList维护的内部类Itr，需要重点关注三个属性：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
private class Itr implements Iterator<E> {
    int cursor;       // 遍历集合时即将遍历的索引
    int lastRet = -1; // 记录刚刚遍历的索引，-1不是不存在上一个元素
    int expectedModCount = modCount;// 初始值为modCount，用于记录集合的修改次数

    public boolean hasNext() {
        return cursor != size;// 判断遍历是否结束
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();// 检查是否触发fail-fast机制
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
    ...
    final void checkForComodification() {
        if (modCount != expectedModCount)
            // expectedModCount在初始化后并未发生改变，那么如果modCount发生改变，就会抛出异常
            throw new ConcurrentModificationException();
    }
}

通过分析迭代器源码可以发现，迭代器的checkForComodification方法是判断是否要触发fail-fast机制的关键。

在checkForComodification方法中可以看到，是否要抛出异常在于modCount是否发生改变。

查看ArrayList源码，发现modCount的改变发生在对集合修改中，比如add操作。

所以当在使用迭代器遍历集合时，如果同时对集合进行了修改，导致modCount发生改变，就会触发fail-fast机制，抛出异常。

5.1.3 解决

有两种解决方式：

  • 使用迭代器提供的方法：为了避免触发fail-fast机制，在迭代集合时，需要使用迭代器提供的修改方法修改集合。
  • 使用线程安全的集合类：也可以使用线程安全的集合类，使用CopyOnWriteArrayList代替ArrayList，使用ConcerrentHashMap代替HashMap。

5.2 安全失败机制

安全失败机制，即fail-safe机制，在集合的克隆对象上进行遍历，对集合的修改不会影响遍历操作。

在java.util.concurrent包下的集合类都是安全失败的，可以在多线程下并发使用并发修改，常见的的使用fail-safe方式遍历的容器有CopyOnWriteArrayList和ConcerrentHashMap等。

基于克隆对象的遍历避免了在修改集合时抛出ConcurrentModificationException异常，但同样导致遍历时不能访问修改后的内容。

集合
https://momashanhe.com/posts/20250428/145309/
本文作者
墨码山河
发布于
2025年4月28日
更新于
2025年5月12日
许可协议
CC BY-NC-SA 4.0
博文难免存在纰漏，如有错误之处，无论大小，恳请读者指正，博主不胜感激。
大后端

Java

评论