Java 集合源码 - AbstractCollection

  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

public abstract class AbstractCollection<E> implements Collection<E> {
    // 独有的构造方法，
    protected AbstractCollection() {
    }

    // 查询相关操作方法

    public abstract Iterator<E> iterator();
    public abstract int size();
    public boolean isEmpty() {
        return size() == 0;
    }
    /**
     * 判断对象是否在集合中，主要依据对象是否为null来做判断
     */
    public boolean contains(Object o) {
        Iterator<E> it = iterator();
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return true;
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return true;
        }
        return false;
    }
    /**
     * 返回一个包含该集合所有元素的数组，数组中元素的顺序和集合中的顺序一致。
     * 即使在迭代过程中，集合长度被改变，最终也会返回与迭代器长度一致的数组(当集合在迭代期间被其他线程并发修改)
     * 如果集合中元素比预期的要少，则调用Arrays.copyOf复制数组
     * 如果集合中元素比预期的要多，则调用finishToArray生成并返回新的数组
     */
    public Object[] toArray() {
        // 这里的数组长度只是调用size()做一个预估，并不代表最终数组长度一定是当前的长度
        Object[] r = new Object[size()];
        Iterator<E> it = iterator();
        for (int i = 0; i < r.length; i++) {
            // 集合长度少于预期(size())，调用Arrays.copyOf复制数组并返回
            if (! it.hasNext())
                return Arrays.copyOf(r, i);
            r[i] = it.next();
        }
        // 判断迭代器是否有剩余的元素没有遍历
        // 有的话说明集合长度被增加，调用finishToArray生成新数组并返回
        // 没有则说明长度一致，直接返回即可
        return it.hasNext() ? finishToArray(r, it) : r;
    }

    /**
     * 返回指定类型的数组
     */
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        // 这里的数组长度只是调用size()做一个预估，并不代表最终数组长度一定是当前的长度
        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) {
                // 如果数组是传入的数组，则将该数组的剩余部分置为null
                    r[i] = null; // null-terminate
                } else if (a.length < i) {
                // 如果当前遍历i的数值大于传入数组的长度，则集合元素数量虽然比预期小，但是依旧大于传入数组的长度。
                // 直接调用Arrays.copyOf复制并返回新的数组
                    return Arrays.copyOf(r, i);
                } else {
                // 数组是新创建的数组，且当前遍历的i小于等于传入数组的长度。
                // 则将新创建数组中的元素复制到传入数组中，若遍历的i小于传入数组长度，将传入数组下标为i的值置为null，返回传入的数组
                    System.arraycopy(r, 0, a, 0, i);
                    if (a.length > i) {
                        a[i] = null;
                    }
                }
                return a;
            }
            r[i] = (T)it.next();
        }
        // 集合长度被增加的情况与toArray()最终处理方式一致
        return it.hasNext() ? finishToArray(r, it) : r;
    }

    /**
     * 数组扩容的最大值，实际在Java中，数组最大长度限制为 Integer.MAX_VALUE - 2
     * 为了防止内存溢出，这里做了限制为 Integer.MAX_VALUE - 8
     * 关于为什么最大长度要减去 8: 对于有些虚拟机实现来说，数组对象的头部会占用这 8 个字节，具体细节可参考最后的资料
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 当在toArray方法中，迭代器返回了比预期要多的元素时，重新扩容数组并将多余预期的元素放入扩容后的数组中
     */
    @SuppressWarnings("unchecked")
    private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
        int i = r.length;
        while (it.hasNext()) {
            int cap = r.length;
            // 当索引指向最后一个元素，代表数组长度不够了，需要进行扩容
            // 扩容大小：cap + cap/2 + 1
            if (i == cap) {
                int newCap = cap + (cap >> 1) + 1;
                // 判断扩容后的数组长度是否溢出
                if (newCap - MAX_ARRAY_SIZE > 0)
                    newCap = hugeCapacity(cap + 1);
                r = Arrays.copyOf(r, newCap);
            }
            r[i++] = (T)it.next();
        }
        // 如果扩容的容量过多，则只返回实际长度的数组
        return (i == r.length) ? r : Arrays.copyOf(r, i);
    }
    /**
     * 判断数组长度是否溢出
     */
    private static int hugeCapacity(int minCapacity) {
        // 数组长度溢出，抛出异常
        if (minCapacity < 0)
            throw new OutOfMemoryError
                ("Required array size too large");
        // 判断是否大于数组扩容允许的最大值，若大于则只允许扩容到最大值
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

    // 修改相关操作方法

    /**
     * Collection默认不支持add操作
     */
    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }

    /**
     * 调用迭代器的remove方法删除元素
     * 当对应的迭代器没有实现remove方法时，同样会抛UnsupportedOperationException
     */
    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;
    }


    // 批量操作方法

    /**
     * 批量判断元素是否都存在
     */
    public boolean containsAll(Collection<?> c) {
        for (Object e : c)
            if (!contains(e))
                return false;
        return true;
    }

    /**
     * 将参数集合中的元素都add到当前集合中
     * (若集合未实现add方法，可能会抛UnsupportedOperationException)
     */
    public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
    }

    /**
     * 批量删除元素
     * 通过迭代器，迭代判断集合中是否存在元素，存在就调用remove方法删除元素
     */
    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;
    }

    /**
     * 删除所有不在传入集合中存在的元素
     */
    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

    /**
     * 返回集合的字符串表示形式
     */
    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(' ');
        }
    }
}