之前看过一句话，说的特别好。有人问阅读源码有什么用？学习别人实现某个功能的设计思路，提高自己的编程水平。
是的，大家都实现一个功能，不同的人有不同的设计思路，有的人用一万行代码，有的人用五千行。有的人代码运行需要的几十秒，有的人只需要的几秒。。下面进入正题了。
本文的主要内容：
· 详细注释了ArrayList的实现，基于JDK 1.8 。
·迭代器SubList部分未详细解释，会放到其他源码解读里面。此处重点关注ArrayList本身实现。
·没有采用标准的注释，并适当调整了代码的缩进以方便介绍
|
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
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
|
import java.util.AbstractList;import java.util.Arrays;import java.util.BitSet;import java.util.Collection;import java.util.Comparator;import java.util.ConcurrentModificationException;import java.util.Iterator;import java.util.List;import java.util.ListIterator;import java.util.NoSuchElementException;import java.util.Objects;import java.util.RandomAccess;import java.util.Spliterator;import java.util.function.Consumer;import java.util.function.Predicate;import java.util.function.UnaryOperator;/** * 概述： * List接口可调整大小的数组实现。实现所有可选的List操作，并允许所有元素，包括null，元素可重复。 * 除了列表接口外，该类提供了一种方法来操作该数组的大小来存储该列表中的数组的大小。 * * 时间复杂度： * 方法size、isEmpty、get、set、iterator和listIterator的调用是常数时间的。 * 添加删除的时间复杂度为O(N)。其他所有操作也都是线性时间复杂度。 * * 容量： * 每个ArrayList都有容量，容量大小至少为List元素的长度，默认初始化为10。 * 容量可以自动增长。 * 如果提前知道数组元素较多，可以在添加元素前通过调用ensureCapacity()方法提前增加容量以减小后期容量自动增长的开销。 * 也可以通过带初始容量的构造器初始化这个容量。 * * 线程不安全： * ArrayList不是线程安全的。 * 如果需要应用到多线程中，需要在外部做同步 * * modCount： * 定义在AbstractList中：protected transient int modCount = 0; * 已从结构上修改此列表的次数。从结构上修改是指更改列表的大小，或者打乱列表，从而使正在进行的迭代产生错误的结果。 * 此字段由iterator和listiterator方法返回的迭代器和列表迭代器实现使用。 * 如果意外更改了此字段中的值，则迭代器（或列表迭代器）将抛出concurrentmodificationexception来响应next、remove、previous、set或add操作。 * 在迭代期间面临并发修改时，它提供了快速失败 行为，而不是非确定性行为。 * 子类是否使用此字段是可选的。 * 如果子类希望提供快速失败迭代器（和列表迭代器），则它只需在其 add(int,e)和remove(int)方法（以及它所重写的、导致列表结构上修改的任何其他方法）中增加此字段。 * 对add(int, e)或remove(int)的单个调用向此字段添加的数量不得超过 1，否则迭代器（和列表迭代器）将抛出虚假的 concurrentmodificationexceptions。 * 如果某个实现不希望提供快速失败迭代器，则可以忽略此字段。 * * transient： * 默认情况下,对象的所有成员变量都将被持久化.在某些情况下,如果你想避免持久化对象的一些成员变量,你可以使用transient关键字来标记他们,transient也是java中的保留字(JDK 1.8) */public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ private static final long serialVersionUID = 8683452581122892189L; //默认初始容量 private static final int DEFAULT_CAPACITY = 10; //用于空实例共享空数组实例。 private static final Object[] EMPTY_ELEMENTDATA = {}; //默认的空数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //对的，存放元素的数组，包访问权限 transient Object[] elementData; //大小，创建对象时Java会将int初始化为0 private int size; //用指定的数设置初始化容量的构造函数，负数会抛出异常 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); } } //默认构造函数，使用控数组初始化 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //以集合的迭代器返回顺序，构造一个含有集合中元素的列表 public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toarray可能（错误地）不返回对象[]（见JAVA BUG编号6260652） if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 使用空数组 this.elementData = EMPTY_ELEMENTDATA; } } //因为容量常常会大于实际元素的数量。内存紧张时，可以调用该方法删除预留的位置，调整容量为元素实际数量。 //如果确定不会再有元素添加进来时也可以调用该方法来节约空间 public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } //使用指定参数设置数组容量 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); } //数组的最大容量，可能会导致内存溢出(VM内存限制) private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //增加容量，以确保它可以至少持有由参数指定的元素的数目 private void grow(int minCapacity) { int oldCapacity = elementData.length; //预设容量增加一半 int newCapacity = oldCapacity + (oldCapacity >> 1); //取与参数中的较大值 if (newCapacity - minCapacity < 0)//即newCapacity<minCapacity newCapacity = minCapacity; //若预设值大于默认的最大值检查是否溢出 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); } //检查是否溢出，若没有溢出，返回最大整数值(java中的int为4字节，所以最大为0x7fffffff)或默认最大值 private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) //溢出 throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } //返回数组大小 public int size() { return size; } //是否为空 public boolean isEmpty() { return size == 0; } //是否包含一个数 返回bool public boolean contains(Object o) { return indexOf(o) >= 0; } //返回一个值在数组首次出现的位置，会根据是否为null使用不同方式判断。不存在就返回-1。时间复杂度为O(N) public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; } //返回一个值在数组最后一次出现的位置，不存在就返回-1。时间复杂度为O(N) public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; } //返回副本，元素本身没有被复制，复制过程数组发生改变会抛出异常 public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { throw new InternalError(e); } } //转换为Object数组，使用Arrays.copyOf()方法 public Object[] toArray() { return Arrays.copyOf(elementData, size); } //返回一个数组，使用运行时确定类型，该数组包含在这个列表中的所有元素（从第一到最后一个元素） //返回的数组容量由参数和本数组中较大值确定 @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { if (a.length < size) return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } //返回指定位置的值，因为是数组，所以速度特别快 @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; } //返回指定位置的值，但是会检查这个位置数否超出数组长度 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); //public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) //src:源数组； srcPos:源数组要复制的起始位置； dest:目的数组； destPos:目的数组放置的起始位置； length:复制的长度 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); elementData[--size] = null; //便于垃圾回收期回收 return oldValue; } //删除指定元素首次出现的位置 public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) 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); elementData[--size] = null; // clear to let GC do its work } //清空数组，把每一个值设为null,方便垃圾回收(不同于reset，数组默认大小有改变的话不会重置) public void clear() { modCount++; for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } //添加一个集合的元素到末端，若要添加的集合为空返回false public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } //功能同上，从指定位置开始添加 public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); //要添加的数组 int numNew = a.length; //要添加的数组长度 ensureCapacityInternal(size + numNew); //确保容量 int numMoved = size - index;//不会移动的长度(前段部分) if (numMoved > 0) //有不需要移动的，就通过自身复制，把数组后部分需要移动的移动到正确位置 System.arraycopy(elementData, index, elementData, index + numNew,numMoved); System.arraycopy(a, 0, elementData, index, numNew); //新的数组添加到改变后的原数组中间 size += numNew; return numNew != 0; } //删除指定范围元素。参数为开始删的位置和结束位置 protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; //后段保留的长度 System.arraycopy(elementData, toIndex, elementData, fromIndex,numMoved); int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; } //检查数否超出数组长度 用于添加元素时 private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //检查是否溢出 private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //抛出的异常的详情 private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } //删除指定集合的元素 public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c);//检查参数是否为null return batchRemove(c, false); } //仅保留指定集合的元素 public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); } /** * 源码解读 BY http://anxpp.com/ * @param complement true时从数组保留指定集合中元素的值，为false时从数组删除指定集合中元素的值。 * @return 数组中重复的元素都会被删除(而不是仅删除一次或几次)，有任何删除操作都会返回true */ private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { //遍历数组，并检查这个集合是否包含对应的值，移动要保留的值到数组前面，w最后值为要保留的元素的数量 //简单点：若保留，就将相同元素移动到前段；若删除，就将不同元素移动到前段 for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; }finally {//确保异常抛出前的部分可以完成期望的操作，而未被遍历的部分会被接到后面 //r!=size表示可能出错了：c.contains(elementData[r])抛出异常 if (r != size) { System.arraycopy(elementData, r,elementData, w,size - r); w += size - r; } //如果w==size：表示全部元素都保留了，所以也就没有删除操作发生，所以会返回false；反之，返回true，并更改数组 //而w!=size的时候，即使try块抛出异常，也能正确处理异常抛出前的操作，因为w始终为要保留的前段部分的长度，数组也不会因此乱序 if (w != size) { for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w;//改变的次数 size = w; //新的大小为保留的元素的个数 modified = true; } } return modified; } //保存数组实例的状态到一个流（即它序列化）。写入过程数组被更改会抛出异常 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(); if (size > 0) { ensureCapacityInternal(size); Object[] a = elementData; //读入所有元素 for (int i=0; i<size; i++) { a[i] = s.readObject(); } } } //返回ListIterator，开始位置为指定参数 public ListIterator<E> listIterator(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index); return new ListItr(index); } //返回ListIterator，开始位置为0 public ListIterator<E> listIterator() { return new ListItr(0); } //返回普通迭代器 public Iterator<E> iterator() { return new Itr(); } //通用的迭代器实现 private class Itr implements Iterator<E> { int cursor; //游标，下一个元素的索引，默认初始化为0 int lastRet = -1; //上次访问的元素的位置 int expectedModCount = modCount;//迭代过程不运行修改数组，否则就抛出异常 //是否还有下一个 public boolean hasNext() { return cursor != size; } //下一个元素 @SuppressWarnings("unchecked") public E next() { checkForComodification();//检查数组是否被修改 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]; //设置访问的位置并返回这个值 } //删除元素 public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification();//检查数组是否被修改 try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } @Override @SuppressWarnings("unchecked") public void forEachRemaining(Consumer<? super E> consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } cursor = i; lastRet = i - 1; checkForComodification(); } //检查数组是否被修改 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } //ListIterator迭代器实现 private class ListItr extends Itr implements ListIterator<E> { ListItr(int index) { super(); cursor = index; } public boolean hasPrevious() { return cursor != 0; } public int nextIndex() { return cursor; } public int previousIndex() { return cursor - 1; } @SuppressWarnings("unchecked") public E previous() { checkForComodification(); int i = cursor - 1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[lastRet = i]; } public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void add(E e) { checkForComodification(); try { int i = cursor; ArrayList.this.add(i, e); cursor = i + 1; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } } //返回指定范围的子数组 public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList(this, 0, fromIndex, toIndex); } //安全检查 static void subListRangeCheck(int fromIndex, int toIndex, int size) { if (fromIndex < 0) throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); if (toIndex > size) throw new IndexOutOfBoundsException("toIndex = " + toIndex); if (fromIndex > toIndex) throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); } //子数组 private class SubList extends AbstractList<E> implements RandomAccess { private final AbstractList<E> parent; private final int parentOffset; private final int offset; int size; SubList(AbstractList<E> parent,int offset, int fromIndex, int toIndex) { this.parent = parent; this.parentOffset = fromIndex; this.offset = offset + fromIndex; this.size = toIndex - fromIndex; this.modCount = ArrayList.this.modCount; } public E set(int index, E e) { rangeCheck(index); checkForComodification(); E oldValue = ArrayList.this.elementData(offset + index); ArrayList.this.elementData[offset + index] = e; return oldValue; } public E get(int index) { rangeCheck(index); checkForComodification(); return ArrayList.this.elementData(offset + index); } public int size() { checkForComodification(); return this.size; } public void add(int index, E e) { rangeCheckForAdd(index); checkForComodification(); parent.add(parentOffset + index, e); this.modCount = parent.modCount; this.size++; } public E remove(int index) { rangeCheck(index); checkForComodification(); E result = parent.remove(parentOffset + index); this.modCount = parent.modCount; this.size--; return result; } protected void removeRange(int fromIndex, int toIndex) { checkForComodification(); parent.removeRange(parentOffset + fromIndex,parentOffset + toIndex); this.modCount = parent.modCount; this.size -= toIndex - fromIndex; } public boolean addAll(Collection<? extends E> c) { return addAll(this.size, c); } public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); int cSize = c.size(); if (cSize==0) return false; checkForComodification(); parent.addAll(parentOffset + index, c); this.modCount = parent.modCount; this.size += cSize; return true; } public Iterator<E> iterator() { return listIterator(); } public ListIterator<E> listIterator(final int index) { checkForComodification(); rangeCheckForAdd(index); final int offset = this.offset; return new ListIterator<E>() { int cursor = index; int lastRet = -1; int expectedModCount = ArrayList.this.modCount; public boolean hasNext() { return cursor != SubList.this.size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= SubList.this.size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (offset + i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[offset + (lastRet = i)]; } public boolean hasPrevious() { return cursor != 0; } @SuppressWarnings("unchecked") public E previous() { checkForComodification(); int i = cursor - 1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (offset + i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[offset + (lastRet = i)]; } @SuppressWarnings("unchecked") public void forEachRemaining(Consumer<? super E> consumer) { Objects.requireNonNull(consumer); final int size = SubList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (offset + i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[offset + (i++)]); } // update once at end of iteration to reduce heap write traffic lastRet = cursor = i; checkForComodification(); } public int nextIndex() { return cursor; } public int previousIndex() { return cursor - 1; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { SubList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = ArrayList.this.modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(offset + lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void add(E e) { checkForComodification(); try { int i = cursor; SubList.this.add(i, e); cursor = i + 1; lastRet = -1; expectedModCount = ArrayList.this.modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (expectedModCount != ArrayList.this.modCount) throw new ConcurrentModificationException(); } }; } public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList(this, offset, fromIndex, toIndex); } private void rangeCheck(int index) { if (index < 0 || index >= this.size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private void rangeCheckForAdd(int index) { if (index < 0 || index > this.size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+this.size; } private void checkForComodification() { if (ArrayList.this.modCount != this.modCount) throw new ConcurrentModificationException(); } public Spliterator<E> spliterator() { checkForComodification(); return new ArrayListSpliterator<E>(ArrayList.this, offset,offset + this.size, this.modCount); } } @Override public void forEach(Consumer<? super E> action) { Objects.requireNonNull(action); final int expectedModCount = modCount; @SuppressWarnings("unchecked") final E[] elementData = (E[]) this.elementData; final int size = this.size; for (int i=0; modCount == expectedModCount && i < size; i++) { action.accept(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } /** * Creates a <em><a href="Spliterator.html#binding" rel="external nofollow" >late-binding</a></em> * and <em>fail-fast</em> {@link Spliterator} over the elements in this * list. * * <p>The {@code Spliterator} reports {@link Spliterator#SIZED}, * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}. * Overriding implementations should document the reporting of additional * characteristic values. * * @return a {@code Spliterator} over the elements in this list * @since 1.8 */ @Override public Spliterator<E> spliterator() { return new ArrayListSpliterator<>(this, 0, -1, 0); } /** Index-based split-by-two, lazily initialized Spliterator */ static final class ArrayListSpliterator<E> implements Spliterator<E> { /* * If ArrayLists were immutable, or structurally immutable (no * adds, removes, etc), we could implement their spliterators * with Arrays.spliterator. Instead we detect as much * interference during traversal as practical without * sacrificing much performance. We rely primarily on * modCounts. These are not guaranteed to detect concurrency * violations, and are sometimes overly conservative about * within-thread interference, but detect enough problems to * be worthwhile in practice. To carry this out, we (1) lazily * initialize fence and expectedModCount until the latest * point that we need to commit to the state we are checking * against; thus improving precision. (This doesn't apply to * SubLists, that create spliterators with current non-lazy * values). (2) We perform only a single * ConcurrentModificationException check at the end of forEach * (the most performance-sensitive method). When using forEach * (as opposed to iterators), we can normally only detect * interference after actions, not before. Further * CME-triggering checks apply to all other possible * violations of assumptions for example null or too-small * elementData array given its size(), that could only have * occurred due to interference. This allows the inner loop * of forEach to run without any further checks, and * simplifies lambda-resolution. While this does entail a * number of checks, note that in the common case of * list.stream().forEach(a), no checks or other computation * occur anywhere other than inside forEach itself. The other * less-often-used methods cannot take advantage of most of * these streamlinings. */ private final ArrayList<E> list; private int index; // current index, modified on advance/split private int fence; // -1 until used; then one past last index private int expectedModCount; // initialized when fence set /** Create new spliterator covering the given range */ ArrayListSpliterator(ArrayList<E> list, int origin, int fence, int expectedModCount) { this.list = list; // OK if null unless traversed this.index = origin; this.fence = fence; this.expectedModCount = expectedModCount; } private int getFence() { // initialize fence to size on first use int hi; // (a specialized variant appears in method forEach) ArrayList<E> lst; if ((hi = fence) < 0) { if ((lst = list) == null) hi = fence = 0; else { expectedModCount = lst.modCount; hi = fence = lst.size; } } return hi; } public ArrayListSpliterator<E> trySplit() { int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid) ? null : // divide range in half unless too small new ArrayListSpliterator<E>(list, lo, index = mid, expectedModCount); } public boolean tryAdvance(Consumer<? super E> action) { if (action == null) throw new NullPointerException(); int hi = getFence(), i = index; if (i < hi) { index = i + 1; @SuppressWarnings("unchecked") E e = (E)list.elementData[i]; action.accept(e); if (list.modCount != expectedModCount) throw new ConcurrentModificationException(); return true; } return false; } public void forEachRemaining(Consumer<? super E> action) { int i, hi, mc; // hoist accesses and checks from loop ArrayList<E> lst; Object[] a; if (action == null) throw new NullPointerException(); if ((lst = list) != null && (a = lst.elementData) != null) { if ((hi = fence) < 0) { mc = lst.modCount; hi = lst.size; } else mc = expectedModCount; if ((i = index) >= 0 && (index = hi) <= a.length) { for (; i < hi; ++i) { @SuppressWarnings("unchecked") E e = (E) a[i]; action.accept(e); } if (lst.modCount == mc) return; } } throw new ConcurrentModificationException(); } public long estimateSize() { return (long) (getFence() - index); } public int characteristics() { return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; } } @Override public boolean removeIf(Predicate<? super E> filter) { Objects.requireNonNull(filter); // figure out which elements are to be removed // any exception thrown from the filter predicate at this stage // will leave the collection unmodified int removeCount = 0; final BitSet removeSet = new BitSet(size); final int expectedModCount = modCount; final int size = this.size; for (int i=0; modCount == expectedModCount && i < size; i++) { @SuppressWarnings("unchecked") final E element = (E) elementData[i]; if (filter.test(element)) { removeSet.set(i); removeCount++; } } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } // shift surviving elements left over the spaces left by removed elements final boolean anyToRemove = removeCount > 0; if (anyToRemove) { final int newSize = size - removeCount; for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { i = removeSet.nextClearBit(i); elementData[j] = elementData[i]; } for (int k=newSize; k < size; k++) { elementData[k] = null; // Let gc do its work } this.size = newSize; if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; } return anyToRemove; } @Override @SuppressWarnings("unchecked") public void replaceAll(UnaryOperator<E> operator) { Objects.requireNonNull(operator); final int expectedModCount = modCount; final int size = this.size; for (int i=0; modCount == expectedModCount && i < size; i++) { elementData[i] = operator.apply((E) elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; } @Override @SuppressWarnings("unchecked") public void sort(Comparator<? super E> c) { final int expectedModCount = modCount; Arrays.sort((E[]) elementData, 0, size, c); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; }} |
总结
以上就是本文关于Java编程中ArrayList源码分析的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！
原文链接：http://blog.csdn.net/anxpp/article/details/51202290
