java源码解读--arrayList

发表于 | 分类于 |
字数统计: | 阅读时长 ≈

ArrayList源码解读

增加元素

add(E e)

首先检查容量是否满足要求，不满足扩容，满足则在后面的位置上添加元素

1
2
3
4
5
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

add(int index,E e)

首先检查索引，不能小于0，大于size，确保容量满足要求，使用System.arraycopy进行复制，插入数据，最后增加size

1
2
3
4
5
6
7
8
9
public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

addAll(Collection c)

与add方法类似，首先把c转化为数组，确保容量满足要求，然后用System.arraycopy进行复制，把数据插入到尾部，增加size

1
2
3
4
5
6
7
8
public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

addAll(int index, Collection<? extends E> c)

首先检查索引，确保容量，判断是否有数据需要右移，使用System.arraycopy移动、增加谁，增加size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean addAll(int index, Collection<? extends E> c) {
       rangeCheckForAdd(index);

       Object[] a = c.toArray();
       int numNew = a.length;
       ensureCapacityInternal(size + numNew);  // Increments modCount

       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;
   }

扩容

每次扩容1.5倍，如果容量还不够，则使用最小容量，最小容量=现在容量+插入容量

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

查找对象

indexof()

先判断是是否是null，然后从前往后依次查找，返回第一个目标元素的下标,如果没有匹配目标返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
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++)
		//用了equals，只判断值是否相等
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

lastIndexOf()

先判断是否是null，然后从后向前依次查找，返回第一个目标元素下标，如果没有匹配目标返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
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--)
	//用equals，只判断值是否相等
               if (o.equals(elementData[i]))
                   return i;
       }
       return -1;
   }

删除

remove(int index)

删除指定位置的元素，首先检查索引不能小于0大于size，计算是否有需要左移的数据，把删除位置的元素置null，该方法会返回旧值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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; // clear to let GC do its work

    return oldValue;
}

remove(Object o)

删除指定对象，首先检查对象是否是null，然后从前向后查找对象，并调用fastRemove删除

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

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;
}

fastRemove与remove类似，但是省掉了范围检查和返回旧值

1
2
3
4
5
6
7
8
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
}

remove(Collection<?> c)

删除集合

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
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

clear()

清空列表

1
2
3
4
5
6
7
8
9
public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

迭代器

ArrayList可以得到两种迭代器，iterator()和listIterator()。iterator()中返回的迭代器只能从前向后遍历，而listIterator()迭代器不仅能反向遍历，还能从指定位置开始遍历。
在操作迭代器时，中途调用了ArrayList的其他改变结构的方法，会抛出异常，即fast-fail机制。在初始化迭代器时，保存当前的modCount，然后在每个操作时，检查当前modCount是否与初始化时的一致，如果不一致，说明进行了改变结构的操作，那么会抛出异常。

iterator()

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
public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        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++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

listIterator()

返回的迭代器可指定迭代下标起始值

1
2
3
4
5
6
7
8
9
public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}

public ListIterator<E> listIterator() {
    return new ListItr(0);
}

listIterator迭代器实现，既可以实现前向遍历，也可以实现后项遍历，并且除了删除方法还能够添加、更改数据

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
   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();
           }
       }
}

需要注意remove()方法的重载

假设有这样的场景：遍历list，删除指定元素

首先想到的方式是下面的方式

1
2
3
4
5
6
7
8
9
List<Integer> list = new ArrayList<Integer>();
     for (int i = -3; i < 3; i++) {
         list.add(i);
     }
     for (int i = 0; i < 3; i++) {
     	//期望删除0，1，2
         list.remove(i);
     }
     System.out.println(list);

但是结果却如下：

1
[-2, 0, 2]

这段程序并没有按照预期移除偶数元素。出现这种情况的原因是arraylist重载了remove方法，此处程序调用了remove(int index)方法移除了对应下标元素，并没有按照预期调用remove(Object o)方法。remove重载的问题在《effective java》第41条慎用重载中也提及，并指明是由于Java添加范型和自动装箱后破坏了List接口导致。那么如何才能移除偶数元素呢？答案是转换为包装类。

1
2
3
4
5
6
7
8
List<Integer> list = new ArrayList<Integer>();
        for (int i = -3; i < 3; i++) {
            list.add(i);
        }
        for (int i = 0; i < 3; i++) {
            list.remove((Integer)i);
        }
        System.out.println(list);

对于add方法

我们通常使用Arrays.asList(T t)方法产生List，但是该方法产生的list不能使用add、remove方法

1
2
3
List<Integer> integers = Arrays.asList(1,2,3,4);
integers.add(5);
System.out.println(integers);

输出

1
2
3
4
5
Exception in thread "main" java.lang.UnsupportedOperationException
	at java.util.AbstractList.add(AbstractList.java:148)
	at java.util.AbstractList.add(AbstractList.java:108)
	at self.collection.ListTest.add(ListTest.java:67)
	at self.collection.ListTest.main(ListTest.java:36)

这是因为Arrays里实现了一个内部类，也叫做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
private static class ArrayList<E> extends AbstractList<E>
       implements RandomAccess, java.io.Serializable
   {
       private static final long serialVersionUID = -2764017481108945198L;
       private final E[] a;

       ArrayList(E[] array) {
           a = Objects.requireNonNull(array);
       }

       @Override
       public int size() {
           return a.length;
       }

       @Override
       public Object[] toArray() {
           return a.clone();
       }

       @Override
       @SuppressWarnings("unchecked")
       public <T> T[] toArray(T[] a) {
           int size = size();
           if (a.length < size)
               return Arrays.copyOf(this.a, size,
                                    (Class<? extends T[]>) a.getClass());
           System.arraycopy(this.a, 0, a, 0, size);
           if (a.length > size)
               a[size] = null;
           return a;
       }

       @Override
       public E get(int index) {
           return a[index];
       }

       @Override
       public E set(int index, E element) {
           E oldValue = a[index];
           a[index] = element;
           return oldValue;
       }

       @Override
       public int indexOf(Object o) {
           E[] a = this.a;
           if (o == null) {
               for (int i = 0; i < a.length; i++)
                   if (a[i] == null)
                       return i;
           } else {
               for (int i = 0; i < a.length; i++)
                   if (o.equals(a[i]))
                       return i;
           }
           return -1;
       }

       @Override
       public boolean contains(Object o) {
           return indexOf(o) != -1;
       }

       @Override
       public Spliterator<E> spliterator() {
           return Spliterators.spliterator(a, Spliterator.ORDERED);
       }

       @Override
       public void forEach(Consumer<? super E> action) {
           Objects.requireNonNull(action);
           for (E e : a) {
               action.accept(e);
           }
       }

       @Override
       public void replaceAll(UnaryOperator<E> operator) {
           Objects.requireNonNull(operator);
           E[] a = this.a;
           for (int i = 0; i < a.length; i++) {
               a[i] = operator.apply(a[i]);
           }
       }

       @Override
       public void sort(Comparator<? super E> c) {
           Arrays.sort(a, c);
       }
   }

该类继承了AbstractList，并实现了其中的部分方法，其中不包括add、remove方法，所以调用两者时实际上调用的是抽象类AbstractList的remove，add方法，而这两个方法在AbstractList的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void add(int index, E element) {
     throw new UnsupportedOperationException();
 }

 /**
  * {@inheritDoc}
  *
  * <p>This implementation always throws an
  * {@code UnsupportedOperationException}.
  *
  * @throws UnsupportedOperationException {@inheritDoc}
  * @throws IndexOutOfBoundsException     {@inheritDoc}
  */
 public E remove(int index) {
     throw new UnsupportedOperationException();
 }

所以会抛出UnsupportedOpreationExcetion异常，这个特性让Arrays.asList返回的结果是只读的，不能修改。

-------------本文结束感谢您的阅读-------------

本文标题:java源码解读--arrayList

文章作者:小建儿

发布时间:2018年05月28日 - 12:05

最后更新:2018年05月28日 - 13:05

原始链接:http://yajian.github.io/java源码解读-arrayList/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多