Java JDK7源码-java.util.Vector<E>

源码

1
package java.util;
2
3
public class Vector<E>
4
    extends AbstractList<E>
5
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
6
{
7
8
    /**
9
     * vector用于存储元素的数组缓冲区
10
     * vector的容量(capacity)为该数组的长度
11
     * 其大小至少会满足能容纳vector的所有元素
12
     * 
13
     * 该数组中未存储元素的空间以null填充
14
     */
15
    protected Object[] elementData;
16
17
    /**
18
     * vector中实际存储元素的个数
19
     * 因此数组elementData中索引在
20
     * [0,elementCount-1]
21
     * 之间的元素为vector实际存储的元素
22
     */
23
    protected int elementCount;
24
25
    /**
26
     * 当vector容量不足时自动扩展的容量值
27
     * 若capacityIncrement<=0,则vector每次自动扩展时容量翻倍
28
     */
29
    protected int capacityIncrement;
30
31
    private static final long serialVersionUID = -2767605614048989439L;
32
33
    /**
34
     * @throws IllegalArgumentException initialCapacity<0
35
     */
36
    public Vector(int initialCapacity, int capacityIncrement) {
37
        super();
38
        if (initialCapacity < 0)
39
            throw new IllegalArgumentException("Illegal Capacity: "+
40
                                               initialCapacity);
41
        this.elementData = new Object[initialCapacity];
42
        this.capacityIncrement = capacityIncrement;
43
    }
44
45
    /**
46
     * @throws IllegalArgumentException initialCapacity<0
47
     */
48
    public Vector(int initialCapacity) {
49
        this(initialCapacity, 0);
50
    }
51
52
    public Vector() {
53
        this(10);
54
    }
55
56
    /**
57
     * 以c为基础构造vector,vector中元素的顺序为c迭代器返回的顺序
58
     * 
59
     * @throws NullPointerException c==null
60
     */
61
    public Vector(Collection<? extends E> c) {
62
        // c.toArray()可能不返回Object[](见6260652)
63
        // 说明:
64
        // 因为c可以是任意的Collection实现
65
        // 而Collection对toArray()的返回值仅仅是要求Object[]
66
        // 即实际的返回可以是任意Object的子类
67
        elementData = c.toArray();
68
        elementCount = elementData.length;
69
        if (elementData.getClass() != Object[].class)
70
            // 注1:Arrays.copyOf(r, i, newType)
71
            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
72
    }
73
74
    /**
75
     * 将vector中的元素copy至anArray中
76
     * vector中索引位置为k的元素会被copy至anArray的索引k处
77
     * 
78
     * @throws NullPointerException anArray==null
79
     * @throws IndexOutOfBoundsException anArray.length<vector.size()
80
     * @throws ArrayStoreException vector中至少有一个元素因类型不符无法被存入anArray
81
     */
82
    public synchronized void copyInto(Object[] anArray) {
83
        // 注2:System.arraycopy(r, 0, a, 0, i)
84
        System.arraycopy(elementData, 0, anArray, 0, elementCount);
85
    }
86
87
    /**
88
     * 裁剪vector的容量为list当前的实际长度
89
     * 应用可以使用本方法达到vector的存储空间占用最小化
90
     */
91
    public synchronized void trimToSize() {
92
        // 注3:modCount
93
        modCount++;
94
        int oldCapacity = elementData.length;
95
        if (elementCount < oldCapacity) {
96
            // 注4:Arrays.copyOf(r, i)
97
            elementData = Arrays.copyOf(elementData, elementCount);
98
        }
99
    }
100
101
    /**
102
     * 保证vector的容量足以容纳最少minCapacity个元素
103
     * 如果有必要(即vector的容量不足以容纳最少minCapacity个元素)
104
     * 则增大vector的容量
105
     * 
106
     * 若vector的当前容量不足以容纳minCapacity个元素
107
     * 则替换vector的内部数据数组elementData为一个更大的数组:
108
     * if (capacityIncrement<=0) 新数组的容量较之老数组翻倍
109
     * if (capacityIncrement>0) 新数组的容量为老数组的容量加上capacityIncrement
110
     * 若如此扩展后的新数组容量仍无法容纳minCapacity个元素,则新数组的长度将被设置为minCapacity
111
     */
112
    public synchronized void ensureCapacity(int minCapacity) {
113
        if (minCapacity > 0) {
114
            // 注3:modCount
115
            modCount++;
116
            ensureCapacityHelper(minCapacity);
117
        }
118
    }
119
120
    /**
121
     * 本方法不是线程安全的
122
     * 本类中线程安全的方法可以在内部调用本方法以确保vector的容量满足需求
123
     * 同时不会导致额外的并发开销
124
     */
125
    private void ensureCapacityHelper(int minCapacity) {
126
        if (minCapacity - elementData.length > 0)
127
            grow(minCapacity);
128
    }
129
130
    /**
131
     * 数组可申请的最大容量
132
     * 某些JVM会在数组中保存一些头信息
133
     * 试图申请一个大容量的数组可能会导致OutOfMemoryError:
134
     * 即需要的数组容量超出JVM的限制
135
     */
136
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
137
138
    private void grow(int minCapacity) {
139
        int oldCapacity = elementData.length;
140
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
141
                                         capacityIncrement : oldCapacity);
142
        if (newCapacity - minCapacity < 0)
143
            newCapacity = minCapacity;
144
        if (newCapacity - MAX_ARRAY_SIZE > 0)
145
            newCapacity = hugeCapacity(minCapacity);
146
        // 注4:Arrays.copyOf(r, i)
147
        elementData = Arrays.copyOf(elementData, newCapacity);
148
    }
149
150
    private static int hugeCapacity(int minCapacity) {
151
        if (minCapacity < 0)
152
            throw new OutOfMemoryError();
153
        return (minCapacity > MAX_ARRAY_SIZE) ?
154
            Integer.MAX_VALUE :
155
            MAX_ARRAY_SIZE;
156
    }
157
158
    /**
159
     * 设置vector的有效长度
160
     * 若newSize大于当前有效长度,则确保vector能容纳newSize个元素(不一定需要扩容)
161
     * 若newSize小于当前有效长度,所有索引大于等于newSize的元素都被置为null
162
     * 
163
     * @throws ArrayIndexOutOfBoundsException newSize<0
164
     */
165
    public synchronized void setSize(int newSize) {
166
        // 注3:modCount
167
        modCount++;
168
        if (newSize > elementCount) {
169
            ensureCapacityHelper(newSize);
170
        } else {
171
            for (int i = newSize ; i < elementCount ; i++) {
172
                elementData[i] = null;
173
            }
174
        }
175
        elementCount = newSize;
176
    }
177
178
    /**
179
     * 返回vector的容量
180
     * 即为vector内部存储数据的数组的长度
181
     * 不是vector的有效长度
182
     */
183
    public synchronized int capacity() {
184
        return elementData.length;
185
    }
186
187
    /**
188
     * 重写父类:java.util.AbstractList<E>
189
     * 实现接口:java.util.List<E>
190
     * 
191
     * 返回vector的有效长度
192
     */
193
    public synchronized int size() {
194
        return elementCount;
195
    }
196
197
    /**
198
     * 重写父类:java.util.AbstractList<E>
199
     * 实现接口:java.util.List<E>
200
     * 
201
     * 若vector的有效长度为0则返回true,反之返回false
202
     */
203
    public synchronized boolean isEmpty() {
204
        return elementCount == 0;
205
    }
206
207
    public Enumeration<E> elements() {
208
        return new Enumeration<E>() {
209
            int count = 0;
210
211
            public boolean hasMoreElements() {
212
                return count < elementCount;
213
            }
214
215
            public E nextElement() {
216
                synchronized (Vector.this) {
217
                    if (count < elementCount) {
218
                        return elementData(count++);
219
                    }
220
                }
221
                throw new NoSuchElementException("Vector Enumeration");
222
            }
223
        };
224
    }
225
226
    public boolean contains(Object o) {
227
        return indexOf(o, 0) >= 0;
228
    }
229
230
    public int indexOf(Object o) {
231
        return indexOf(o, 0);
232
    }
233
234
    public synchronized int indexOf(Object o, int index) {
235
        if (o == null) {
236
            for (int i = index ; i < elementCount ; i++)
237
                if (elementData[i]==null)
238
                    return i;
239
        } else {
240
            for (int i = index ; i < elementCount ; i++)
241
                if (o.equals(elementData[i]))
242
                    return i;
243
        }
244
        return -1;
245
    }
246
247
    public synchronized int lastIndexOf(Object o) {
248
        return lastIndexOf(o, elementCount-1);
249
    }
250
251
    public synchronized int lastIndexOf(Object o, int index) {
252
        if (index >= elementCount)
253
            throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
254
255
        if (o == null) {
256
            for (int i = index; i >= 0; i--)
257
                if (elementData[i]==null)
258
                    return i;
259
        } else {
260
            for (int i = index; i >= 0; i--)
261
                if (o.equals(elementData[i]))
262
                    return i;
263
        }
264
        return -1;
265
    }
266
267
    public synchronized E elementAt(int index) {
268
        if (index >= elementCount) {
269
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
270
        }
271
272
        return elementData(index);
273
    }
274
275
    public synchronized E firstElement() {
276
        if (elementCount == 0) {
277
            throw new NoSuchElementException();
278
        }
279
        return elementData(0);
280
    }
281
282
    public synchronized E lastElement() {
283
        if (elementCount == 0) {
284
            throw new NoSuchElementException();
285
        }
286
        return elementData(elementCount - 1);
287
    }
288
289
    public synchronized void setElementAt(E obj, int index) {
290
        if (index >= elementCount) {
291
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
292
                                                     elementCount);
293
        }
294
        elementData[index] = obj;
295
    }
296
297
    public synchronized void removeElementAt(int index) {
298
        modCount++;
299
        if (index >= elementCount) {
300
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
301
                                                     elementCount);
302
        }
303
        else if (index < 0) {
304
            throw new ArrayIndexOutOfBoundsException(index);
305
        }
306
        int j = elementCount - index - 1;
307
        if (j > 0) {
308
            System.arraycopy(elementData, index + 1, elementData, index, j);
309
        }
310
        elementCount--;
311
        elementData[elementCount] = null;
312
    }
313
314
    public synchronized void insertElementAt(E obj, int index) {
315
        modCount++;
316
        if (index > elementCount) {
317
            throw new ArrayIndexOutOfBoundsException(index
318
                                                     + " > " + elementCount);
319
        }
320
        ensureCapacityHelper(elementCount + 1);
321
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
322
        elementData[index] = obj;
323
        elementCount++;
324
    }
325
326
    public synchronized void addElement(E obj) {
327
        modCount++;
328
        ensureCapacityHelper(elementCount + 1);
329
        elementData[elementCount++] = obj;
330
    }
331
332
    public synchronized boolean removeElement(Object obj) {
333
        modCount++;
334
        int i = indexOf(obj);
335
        if (i >= 0) {
336
            removeElementAt(i);
337
            return true;
338
        }
339
        return false;
340
    }
341
342
    public synchronized void removeAllElements() {
343
        modCount++;
344
        for (int i = 0; i < elementCount; i++)
345
            elementData[i] = null;
346
347
        elementCount = 0;
348
    }
349
350
    public synchronized Object clone() {
351
        try {
352
            @SuppressWarnings("unchecked")
353
                Vector<E> v = (Vector<E>) super.clone();
354
            v.elementData = Arrays.copyOf(elementData, elementCount);
355
            v.modCount = 0;
356
            return v;
357
        } catch (CloneNotSupportedException e) {
358
            throw new InternalError();
359
        }
360
    }
361
362
    public synchronized Object[] toArray() {
363
        return Arrays.copyOf(elementData, elementCount);
364
    }
365
366
    @SuppressWarnings("unchecked")
367
    public synchronized <T> T[] toArray(T[] a) {
368
        if (a.length < elementCount)
369
            return (T[]) Arrays.copyOf(elementData, elementCount, a.getClass());
370
371
        System.arraycopy(elementData, 0, a, 0, elementCount);
372
373
        if (a.length > elementCount)
374
            a[elementCount] = null;
375
376
        return a;
377
    }
378
379
    @SuppressWarnings("unchecked")
380
    E elementData(int index) {
381
        return (E) elementData[index];
382
    }
383
384
    public synchronized E get(int index) {
385
        if (index >= elementCount)
386
            throw new ArrayIndexOutOfBoundsException(index);
387
388
        return elementData(index);
389
    }
390
391
    public synchronized E set(int index, E element) {
392
        if (index >= elementCount)
393
            throw new ArrayIndexOutOfBoundsException(index);
394
395
        E oldValue = elementData(index);
396
        elementData[index] = element;
397
        return oldValue;
398
    }
399
400
    public synchronized boolean add(E e) {
401
        modCount++;
402
        ensureCapacityHelper(elementCount + 1);
403
        elementData[elementCount++] = e;
404
        return true;
405
    }
406
407
    public boolean remove(Object o) {
408
        return removeElement(o);
409
    }
410
411
    public void add(int index, E element) {
412
        insertElementAt(element, index);
413
    }
414
415
    public synchronized E remove(int index) {
416
        modCount++;
417
        if (index >= elementCount)
418
            throw new ArrayIndexOutOfBoundsException(index);
419
        E oldValue = elementData(index);
420
421
        int numMoved = elementCount - index - 1;
422
        if (numMoved > 0)
423
            System.arraycopy(elementData, index+1, elementData, index,
424
                             numMoved);
425
        elementData[--elementCount] = null;
426
427
        return oldValue;
428
    }
429
430
    public void clear() {
431
        removeAllElements();
432
    }
433
434
    public synchronized boolean containsAll(Collection<?> c) {
435
        return super.containsAll(c);
436
    }
437
438
    public synchronized boolean addAll(Collection<? extends E> c) {
439
        modCount++;
440
        Object[] a = c.toArray();
441
        int numNew = a.length;
442
        ensureCapacityHelper(elementCount + numNew);
443
        System.arraycopy(a, 0, elementData, elementCount, numNew);
444
        elementCount += numNew;
445
        return numNew != 0;
446
    }
447
448
    public synchronized boolean removeAll(Collection<?> c) {
449
        return super.removeAll(c);
450
    }
451
452
    public synchronized boolean retainAll(Collection<?> c) {
453
        return super.retainAll(c);
454
    }
455
456
    public synchronized boolean addAll(int index, Collection<? extends E> c) {
457
        modCount++;
458
        if (index < 0 || index > elementCount)
459
            throw new ArrayIndexOutOfBoundsException(index);
460
461
        Object[] a = c.toArray();
462
        int numNew = a.length;
463
        ensureCapacityHelper(elementCount + numNew);
464
465
        int numMoved = elementCount - index;
466
        if (numMoved > 0)
467
            System.arraycopy(elementData, index, elementData, index + numNew,
468
                             numMoved);
469
470
        System.arraycopy(a, 0, elementData, index, numNew);
471
        elementCount += numNew;
472
        return numNew != 0;
473
    }
474
475
    public synchronized boolean equals(Object o) {
476
        return super.equals(o);
477
    }
478
479
    public synchronized int hashCode() {
480
        return super.hashCode();
481
    }
482
483
    public synchronized String toString() {
484
        return super.toString();
485
    }
486
487
    public synchronized List<E> subList(int fromIndex, int toIndex) {
488
        return Collections.synchronizedList(super.subList(fromIndex, toIndex),
489
                                            this);
490
    }
491
492
    protected synchronized void removeRange(int fromIndex, int toIndex) {
493
        modCount++;
494
        int numMoved = elementCount - toIndex;
495
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
496
                         numMoved);
497
498
        int newElementCount = elementCount - (toIndex-fromIndex);
499
        while (elementCount != newElementCount)
500
            elementData[--elementCount] = null;
501
    }
502
503
    private void writeObject(java.io.ObjectOutputStream s)
504
            throws java.io.IOException {
505
        final java.io.ObjectOutputStream.PutField fields = s.putFields();
506
        final Object[] data;
507
        synchronized (this) {
508
            fields.put("capacityIncrement", capacityIncrement);
509
            fields.put("elementCount", elementCount);
510
            data = elementData.clone();
511
        }
512
        fields.put("elementData", data);
513
        s.writeFields();
514
    }
515
516
    public synchronized ListIterator<E> listIterator(int index) {
517
        if (index < 0 || index > elementCount)
518
            throw new IndexOutOfBoundsException("Index: "+index);
519
        return new ListItr(index);
520
    }
521
522
    public synchronized ListIterator<E> listIterator() {
523
        return new ListItr(0);
524
    }
525
526
    public synchronized Iterator<E> iterator() {
527
        return new Itr();
528
    }
529
530
    private class Itr implements Iterator<E> {
531
        int cursor;
532
        int lastRet = -1;
533
        int expectedModCount = modCount;
534
535
        public boolean hasNext() {
536
            return cursor != elementCount;
537
        }
538
539
        public E next() {
540
            synchronized (Vector.this) {
541
                checkForComodification();
542
                int i = cursor;
543
                if (i >= elementCount)
544
                    throw new NoSuchElementException();
545
                cursor = i + 1;
546
                return elementData(lastRet = i);
547
            }
548
        }
549
550
        public void remove() {
551
            if (lastRet == -1)
552
                throw new IllegalStateException();
553
            synchronized (Vector.this) {
554
                checkForComodification();
555
                Vector.this.remove(lastRet);
556
                expectedModCount = modCount;
557
            }
558
            cursor = lastRet;
559
            lastRet = -1;
560
        }
561
562
        final void checkForComodification() {
563
            if (modCount != expectedModCount)
564
                throw new ConcurrentModificationException();
565
        }
566
    }
567
568
    final class ListItr extends Itr implements ListIterator<E> {
569
        ListItr(int index) {
570
            super();
571
            cursor = index;
572
        }
573
574
        public boolean hasPrevious() {
575
            return cursor != 0;
576
        }
577
578
        public int nextIndex() {
579
            return cursor;
580
        }
581
582
        public int previousIndex() {
583
            return cursor - 1;
584
        }
585
586
        public E previous() {
587
            synchronized (Vector.this) {
588
                checkForComodification();
589
                int i = cursor - 1;
590
                if (i < 0)
591
                    throw new NoSuchElementException();
592
                cursor = i;
593
                return elementData(lastRet = i);
594
            }
595
        }
596
597
        public void set(E e) {
598
            if (lastRet == -1)
599
                throw new IllegalStateException();
600
            synchronized (Vector.this) {
601
                checkForComodification();
602
                Vector.this.set(lastRet, e);
603
            }
604
        }
605
606
        public void add(E e) {
607
            int i = cursor;
608
            synchronized (Vector.this) {
609
                checkForComodification();
610
                Vector.this.add(i, e);
611
                expectedModCount = modCount;
612
            }
613
            cursor = i + 1;
614
            lastRet = -1;
615
        }
616
    }
617
}

已整理层级关系

本类直接继承的类

本类直接实现的接口

综述

Vector实现了一个可增长的数组对象。像数组一样,Vector可使用索引进行随机访问。但是Vector在创建后,其长度可随着添加或移除元素而增长或收缩。

vector试图通过维护capacity及capacityIncrement以达到存储管理的最优化。capacity总是至少和vector的长度一样大;capacity通常都会比vector的长度大一些,因为随着元素的添加vector是以capacityIncrement为基数成块增长。为减少空间重分配的次数,应用可以在添加大量元素前增大vector的capacity至一个合理的值。

vector返回的iterator:

1
iterator() : iterator
2
listIterator(int) : listIterator

遵循fail-fast原则:在iterator创建后,若vector因非该iterator的原因,即不是该iterator的以下方法:

1
ListIterator#remove() remove
2
ListIterator#add(Object) add

而发生了结构性变化,该iterator会抛出ConcurrentModificationException。因此,面对并发性修改,iterator放弃的快速而彻底,并不会去仔细考察该并发性修改是否真的会对自身即将进行的操作造成不利影响。vector的elements()返回的Enumeration对象不遵循fail-fast原则。

注意iterator遵循的fail-fast原则并不能从根本上解决并发问题,它仅仅只是尽力而为,若要避免并发问题,还需结构本身提供线程安全保护。因此因fail-fast原则抛出的ConcurrentModificationException仅应被用于检测bug,而非以其为依据进行并发保护。

在JDK1.2版本中,Vector被重写,重写后的Vector实现了List接口,因此其成为了Java集合框架中的一员。和新的集合实现类不同,Vector是线程安全的。若应用不需要线程安全的实现,推荐使用ArrayList替代本类。

注1:Arrays.copyOf(r, i, newType)

1
Arrays.copyOf(U[] r, int i, Class<? extends T[]> newType)

以r为基础返回一个长度为i的数组,返回数组的类型为newType。

  • 若i<r.length则r发生截断。实际返回的数组为r中索引为[0,i-1]的元素。

  • 若i==r.length,则返回的数组与r相等。

  • 若i>r.length,返回的数组中索引为[0, r.length-1]的元素为r中对应位置的元素,索引为[r.length, i-1]的元素以null填充。

无论如何,返回的数组都是新生成的,与r不存在引用关系。返回的数组中的元素是r中元素的浅拷贝。

注2:System.arraycopy(r, 0, a, 0, i)

参数含义依次为:

  1. r: 待复制的源数组。
  2. 0: 源数组中开始复制的索引。
  3. a: 复制目标数组。
  4. 0: 目标数组中接收元素的起始索引。
  5. i: 复制的元素个数。

目标数组中其他位置的元素不受影响。

注3:modCount

modCount字段继承自超类AbstractList:

list发生结构性变化的次数。结构性变化是指改变list的长度,或是其他会使迭代器结果混乱的变化。

本字段将被iterator()返回的iterator及listIterator()返回的listIterator使用。若本字段发生了 iterator/listIterator 所没有预期到的变化,则在调用 iterator/listIterator 的next(),remove(),previous(),set(E e),add(E e)出现fail-fast时抛出ConcurrentModificationException。

在迭代过程中,若检测到并发性变化,则直接判定为失败并抛出异常(fail-fast),而不会去进一步检测所发生的并发性变化是否真的会对迭代造成影响(non-deterministic)。

子类可自行选择是否使用本字段。若子类决定继承本类的fail-fast判定,则只需要在会引发结构性变化的方法中增加本字段的值。本类中已实现的引发结构性变化的方法有add(int index, E element)及remove(int index)。调用一次add(int index, E element)或remove(int index)只需将本字段自增1,表示发生了一次结构性变化,否则 iterator/listIterator 会抛出错误的ConcurrentModificationException。

若子类不想遵循fail-fast,忽略本字段即可。

注4:Arrays.copyOf(r, i)

以r为基础返回一个长度为i的数组。

  • 若i<r.length则r发生截断。实际返回的数组为r中索引为[0,i-1]的元素。

  • 若i==r.length,则返回的数组与r相等。

  • 若i>r.length,返回的数组中索引为[0, r.length-1]的元素为r中对应位置的元素,索引为[r.length, i-1]的元素以null填充。

无论如何,返回的数组都是新生成的,与r不存在引用关系。返回的数组中的元素是r中元素的浅拷贝。