Java 集合框架02---Collection的源码分析

上篇我们分析了Java集合的总体类图，下面我们接着来具体探究一下相关的源码。

概要

Collection 简介

Collection 的定义
public interface Collection<E> extends Iterable<E>{}
Collection是一个接口，是高度抽象的集合，其包含了集合的基本操作，如添加，删除，遍历，是否为空，集合转为数组，集合大小，集合之间的合并。
其API如下：

// Collection的API
abstract boolean add(E object) //添加元素
abstract boolean addAll(Collection<? extends E> collection)  //添加集合
abstract void clear()  //删除元素
abstract boolean contains(Object object) //是否包含特定元素
abstract boolean containsAll(Collection<?> collection)  //是否包含某个集合
abstract boolean equals(Object object)  //
abstract int hashCode()  //获取集合的hashCode值
abstract boolean isEmpty()  //判断集合是否为空
abstract Iterator<E> iterator()  //获取集合的迭代器
abstract boolean remove(Object object)  //移除元素
abstract boolean removeAll(Collection<?> collection)
abstract boolean retainAll(Collection<?> collection)
abstract int size()  //获取集合的大小
abstract <T> T[] toArray(T[] array)   //集合转化成数组
abstract Object[] toArray()  //集合转化成数组
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

List 简介

List的定义
public interface List<E> extends Collection<E>{}
List 是一个继承于Collection的接口，即List是集合中的一种接口。所以，Collection 接口有的方法List中也有。
List 是一个有序队列，集合的初始索引是0，以后每增加一个元素索引+1。List中允许有重复元素。
其增加的API如下：(与Collection相同的API不重复列出)

abstract void add(int location, E object)  //在指定位置添加元素
abstract boolean addAll(int location, Collection<? extends E> collection) //在指定位置添加集合
abstract E get(int location)  //获取指定位置的元素
abstract int indexOf(Object object)//获取元素的索引值
abstract int lastIndexOf(Object object)  
abstract ListIterator<E> listIterator(int location)
abstract ListIterator<E> listIterator()
abstract E remove(int location)  //移除指定位置的元素
abstract E set(int location, E object) abstract List<E> subList(int start, int end)  //获取子集合
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

Set 简介

Set的定义
public interface Set<E> extends Collection<E>{}
Set是一个继承于Collection的接口，即List是集合中的一种接口。 不允许有重复元素。其API与Collection的API完全一样。再次不再赘述。

Queue 简介

AbstractCollection

AbstractCollection的定义是
public abstract class AbstractCollection<E> implements Collection<E>{}
AbstractCollection是一个实现了Collection的抽象类，其实现了Collection中除了iterator和size方法之外的方法。所以，继承与AbstractCollection的其他实现类，只需要实现AbstractCollection类没有实现的方法以及按照需求重写相关方法。

 public abstract Iterator<E> iterator(); public abstract int size();
  

 

  
1
  
2
 

具体分析下AbstractCollection类下的相关方法的实现。

public boolean isEmpty() { return size() == 0; } //检查集合是否包含特定元素 public boolean contains(Object o) { Iterator<E> it = iterator(); if (o==null) { //任何非空集合都包含null while (it.hasNext()) if (it.next()==null) return true; } else { while (it.hasNext()) if (o.equals(it.next())) return true; } return false; }
  //将集合转化成数组 public Object[] toArray() { // Estimate size of array; be prepared to see more or fewer elements Object[] r = new Object[size()];  //定义一个与集合等大的数组 Iterator<E> it = iterator(); //循环将集合中的元素copy到数组r中 for (int i = 0; i < r.length; i++) { if (! it.hasNext()) // fewer elements than expected return Arrays.copyOf(r, i); r[i] = it.next(); } return it.hasNext() ? finishToArray(r, it) : r; }
 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; private static <T> 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; // overflow-conscious code if (newCap - MAX_ARRAY_SIZE > 0) newCap = hugeCapacity(cap + 1); r = Arrays.copyOf(r, newCap); } r[i++] = (T)it.next(); } // trim if overallocated 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; } public <T> T[] toArray(T[] a) { // Estimate size of array; be prepared to see more or fewer elements int size = size(); T[] r = a.length >= size ? a : (T[])java.lang.reflect.Array .newInstance(a.getClass().getComponentType(), size); Iterator<E> it = iterator(); for (int i = 0; i < r.length; i++) { if (! it.hasNext()) { // fewer elements than expected if (a == r) { r[i] = null; // null-terminate } else if (a.length < i) { return Arrays.copyOf(r, i); } else { System.arraycopy(r, 0, a, 0, i); if (a.length > i) { a[i] = null; } } return a; } r[i] = (T)it.next(); } // more elements than expected return it.hasNext() ? finishToArray(r, it) : r; } // Modification Operations public boolean add(E e) { throw new UnsupportedOperationException(); } //删除元素o   public boolean remove(Object o) { Iterator<E> it = iterator(); if (o==null) { while (it.hasNext()) { if (it.next()==null) { it.remove(); return true; } } } else { while (it.hasNext()) { if (o.equals(it.next())) { it.remove(); return true; } } } return false; } // Bulk Operations public boolean containsAll(Collection<?> c) { for (Object e : c) if (!contains(e)) return false; return true; } public boolean addAll(Collection<? extends E> c) { boolean modified = false; for (E e : c) if (add(e)) modified = true; return modified; } //删除集合c中所有元素（如果存在的话）   public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); boolean modified = false; Iterator<?> it = iterator(); while (it.hasNext()) { if (c.contains(it.next())) { it.remove(); modified = true; } } return modified; } //删除不在集合c中的所有元素（如果存在的话）   public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); boolean modified = false; Iterator<E> it = iterator(); while (it.hasNext()) { if (!c.contains(it.next())) { it.remove(); modified = true; } } return modified; }

// 清空 public void clear() { Iterator<E> it = iterator(); while (it.hasNext()) { it.next(); it.remove(); } } //  String conversion
// 将List 转成[String] biao'shi public String toString() { Iterator<E> it = iterator(); if (! it.hasNext()) return "[]"; StringBuilder sb = new StringBuilder(); sb.append('['); for (;;) { E e = it.next(); sb.append(e == this ? "(this Collection)" : e); if (! it.hasNext()) return sb.append(']').toString(); sb.append(',').append(' '); } }

  

 

  
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
  
173
  
174
  
175
  
176
  
177
  
178
  
179
  
180
  
181
  
182
  
183
 

AbstractList

AbstractList的定义
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>{}
从定义看出AbstractList继承了AbstractCollection类。实现了List接口。与AbstractCollection类相比其实现了iterator方法。
AbstractList部分源码分析

   // Search Operations //如果找到则返回该元素的前一个索引值，没有就返回-1 public int indexOf(Object o) { ListIterator<E> 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(); } return -1; } //如果找到则返回该元素的后一个索引值，没有就返回-1 public int lastIndexOf(Object o) { ListIterator<E> it = listIterator(size()); if (o==null) { while (it.hasPrevious()) if (it.previous()==null) return it.nextIndex(); } else { while (it.hasPrevious()) if (o.equals(it.previous())) return it.nextIndex(); } return -1; } // Bulk Operations //清除集合中的元素 public void clear() { removeRange(0, size()); } public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index);  //检查索引值是否合法 boolean modified = false; for (E e : c) { add(index++, e); modified = true; } return modified; } private void rangeCheckForAdd(int index) { if (index < 0 || index > size()) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } protected void removeRange(int fromIndex, int toIndex) { ListIterator<E> it = listIterator(fromIndex); for (int i=0, n=toIndex-fromIndex; i<n; i++) { it.next(); it.remove(); } }
-------------------------------------------------------------------------------- public Iterator<E> iterator() { return new Itr(); } public ListIterator<E> listIterator() { return listIterator(0); } public ListIterator<E> listIterator(final int index) { rangeCheckForAdd(index); return new ListItr(index); } private class Itr implements Iterator<E> { /** * Index of element to be returned by subsequent call to next. */ int cursor = 0; /** * Index of element returned by most recent call to next or * previous.  Reset to -1 if this element is deleted by a call * to remove. */ int lastRet = -1; /** * The modCount value that the iterator believes that the backing * List should have.  If this expectation is violated, the iterator * has detected concurrent modification.（源代码的注释） *  译：iterator 每次遍历都会检测modCount的值是否与List应有的长度相等，如果不相等的话，则会抛出一个ConcurrentModificationException的异常 这种场景常见于多线程的情况下。当一个线程正在遍历集合list时，如果在其中另外一个线程删除了list中的某个元素，则会出现该异常 */ int expectedModCount = modCount; public boolean hasNext() { return cursor != size(); } public E next() { checkForComodification(); try { int i = cursor; E next = get(i); lastRet = i; cursor = i + 1; return next; } catch (IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); } } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { AbstractList.this.remove(lastRet); if (lastRet < cursor) cursor--; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException e) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } private class ListItr extends Itr implements ListIterator<E> { ListItr(int index) { cursor = index; } public boolean hasPrevious() { return cursor != 0; } 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 int nextIndex() { return cursor; } public int previousIndex() { return cursor-1; } 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; cursor = i + 1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } }
--------------------------------------------------------------------------------
// 获取List的子集subList，指定开始索引和结束索引
 public List<E> subList(int fromIndex, int toIndex) { return (this instanceof RandomAccess ? new RandomAccessSubList<>(this, fromIndex, toIndex) : new SubList<>(this, fromIndex, toIndex)); }

class SubList<E> extends AbstractList<E> { private final AbstractList<E> l; private final int offset; private int size; /** 从`SubList`的构造器我们可以看出，其并不是返回一个真正的子集，还是原有的集合List，只是偏移量改成了fromIndex，大小改成了toIndex - fromIndex，所以对子集增加，删除元素会直接作用域原有的List*/ SubList(AbstractList<E> 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; } public E set(int index, E element) { rangeCheck(index); checkForComodification(); return l.set(index+offset, element); } public E get(int index) { rangeCheck(index); checkForComodification(); return l.get(index+offset); } public int size() { checkForComodification(); return size; } public void add(int index, E element) { rangeCheckForAdd(index); checkForComodification(); l.add(index+offset, element); this.modCount = l.modCount; size++; } public E remove(int index) { rangeCheck(index); checkForComodification(); E result = l.remove(index+offset); this.modCount = l.modCount; size--; return result; } protected void removeRange(int fromIndex, int toIndex) { checkForComodification(); l.removeRange(fromIndex+offset, toIndex+offset); this.modCount = l.modCount; size -= (toIndex-fromIndex); } public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); int cSize = c.size(); if (cSize==0) return false; checkForComodification(); l.addAll(offset+index, c); this.modCount = l.modCount; size += cSize; return true; } public Iterator<E> iterator() { return listIterator(); } public ListIterator<E> listIterator(final int index) { checkForComodification(); rangeCheckForAdd(index); return new ListIterator<E>() { private final ListIterator<E> i = l.listIterator(index+offset); public boolean hasNext() { return nextIndex() < size; } public E next() { if (hasNext()) return i.next(); else throw new NoSuchElementException(); } public boolean hasPrevious() { return previousIndex() >= 0; } public E previous() { if (hasPrevious()) return i.previous(); else throw new NoSuchElementException(); } public int nextIndex() { return i.nextIndex() - offset; } public int previousIndex() { return i.previousIndex() - offset; } public void remove() { i.remove(); SubList.this.modCount = l.modCount; size--; } public void set(E e) { i.set(e); } public void add(E e) { i.add(e); SubList.this.modCount = l.modCount; size++; } }; } public List<E> subList(int fromIndex, int toIndex) { return new SubList<>(this, fromIndex, toIndex); } private void rangeCheck(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private void rangeCheckForAdd(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } private void checkForComodification() { if (this.modCount != l.modCount) throw new ConcurrentModificationException(); }
}

  

 

  
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
  
173
  
174
  
175
  
176
  
177
  
178
  
179
  
180
  
181
  
182
  
183
  
184
  
185
  
186
  
187
  
188
  
189
  
190
  
191
  
192
  
193
  
194
  
195
  
196
  
197
  
198
  
199
  
200
  
201
  
202
  
203
  
204
  
205
  
206
  
207
  
208
  
209
  
210
  
211
  
212
  
213
  
214
  
215
  
216
  
217
  
218
  
219
  
220
  
221
  
222
  
223
  
224
  
225
  
226
  
227
  
228
  
229
  
230
  
231
  
232
  
233
  
234
  
235
  
236
  
237
  
238
  
239
  
240
  
241
  
242
  
243
  
244
  
245
  
246
  
247
  
248
  
249
  
250
  
251
  
252
  
253
  
254
  
255
  
256
  
257
  
258
  
259
  
260
  
261
  
262
  
263
  
264
  
265
  
266
  
267
  
268
  
269
  
270
  
271
  
272
  
273
  
274
  
275
  
276
  
277
  
278
  
279
  
280
  
281
  
282
  
283
  
284
  
285
  
286
  
287
  
288
  
289
  
290
  
291
  
292
  
293
  
294
  
295
  
296
  
297
  
298
  
299
  
300
  
301
  
302
  
303
  
304
  
305
  
306
  
307
  
308
  
309
  
310
  
311
  
312
  
313
  
314
  
315
  
316
  
317
  
318
  
319
  
320
  
321
  
322
  
323
  
324
  
325
  
326
  
327
  
328
  
329
  
330
  
331
  
332
  
333
  
334
  
335
  
336
  
337
  
338
  
339
  
340
  
341
  
342
  
343
  
344
  
345
  
346
  
347
  
348
  
349
  
350
  
351
  
352
  
353
  
354
  
355
  
356
  
357
  
358
  
359
 

从上述源码中，我理解的两条重要信息是：
1. AbstractList是非线程安全的，当一个线程在遍历List时，另外一个线程对该List进行修改则会直接抛出ConcurrentModificationException的异常
2. 从SubList的构造器我们可以看出，其并不是返回一个真正的子集，还是原有的集合List，只是偏移量改成了fromIndex，大小改成了toIndex - fromIndex，所以对子集增加，删除元素会直接作用域原有的List

AbstractSet

AbstractSet的定义是
public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E>{}
AbstractSet的部分源码分析

 protected AbstractSet() { } // Comparison and hashing public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Set)) return false; Collection<?> c = (Collection<?>) o; if (c.size() != size()) return false; try { return containsAll(c); } catch (ClassCastException unused)   { return false; } catch (NullPointerException unused) { return false; } } public int hashCode() { int h = 0; Iterator<E> i = iterator(); while (i.hasNext()) { E obj = i.next(); if (obj != null) h += obj.hashCode(); } return h; } public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); boolean modified = false; if (size() > c.size()) { for (Iterator<?> i = c.iterator(); i.hasNext(); ) modified |= remove(i.next()); } else { for (Iterator<?> i = iterator(); i.hasNext(); ) { if (c.contains(i.next())) { i.remove(); modified = true; } } } return modified; }
  

 

  
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
 

从上述源码中可以看出AbstractSet 只是重写了AbstractCollection中的removeAll方法。

Iterator 简介

Iterator的定义

public interface Iterator<E>{}
  

 

  
1
 

Iterator是一个接口，Iterator 是Collection分支下的集合的最重要的遍历工具，所有的List和Set都需要依赖它。
从API中看出，其包含的方法有，是否有下一个元素，获取下一个元素，删除当前元素。
Iterator遍历集合时采取的是 fast-fail 机制，即，当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了，那么线程A访问集合时，就会抛出CurrentModificationException异常，产生fail-fast事件。
Iterator的API是

abstract boolean hasNext()  
abstract E next()  
abstract void remove() 
  

 

  
1
  
2
  
3
 

ListIterator 简介

ListIterator的定义

public interface ListIterator<E> extends Iterator<E> {}
  

 

  
1
 

ListIterator是一个继承Iterator的接口，它是队列迭代器。专门用于遍历List，能提供向前和向后遍历。相比于Iterator，它新增了添加、是否存在上一个元素、获取上一个元素等API接口：

// 继承于Iterator的接口  
abstract boolean hasNext()  
abstract E next()  
abstract void remove()  
// 新增API接口  
abstract void add(E object)  
abstract boolean hasPrevious()  
abstract int nextIndex()  
abstract E previous()  
abstract int previousIndex()  
abstract void set(E object)  
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

文章来源: feige.blog.csdn.net，作者：码农飞哥，版权归原作者所有，如需转载，请联系作者。

原文链接：feige.blog.csdn.net/article/details/79369651