Java ArrayList 笔记

作者: 天之見證 | 来源:发表于2020-08-06 19:36 被阅读0次

Java学习笔记之ArrayList基本用法
ArrayList 扩容 Android Java 真的不一
Java ArrayList操作英文书目录
Java ArrayList 笔记
Java学习笔记——LinkedList插入和删除真的比Arra
java 集合 1 - ArrayList
JAVA ArrayList学习笔记
Java ArrayList阅读笔记
java基础-泛型中的extends和super
ArrayList 源码分析

Java ArrayList 笔记

remove 操作是否会缩容
modCount 起什么作用
是否线程安全
如果不是线程安全的, 在多线程环境下,使用中会有什么问题
为什么元素的遍历操作都是通过迭代器来完成

1. 继承关系梳理

在Idea里面将ArrayList的源码打开,可以导出如下继承关系:

ArrayListArch.png

从上往下分析

1.1 `Iterable`

方法	含义	出现版本
`Iterator<T> iterator()`	返回一个迭代器	1.5
`forEach(Consumer<? super T> action)`	接口默认方法,对每个元素做处理	1.8
`Spliterator<T> spliterator()`	接口默认方法,返回一个可分割的迭代器	1.8

default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {
        action.accept(t);
    }
}

1.2 `Collection`

public interface Collection<E> extends Iterable<E>

方法	含义	出现版本
`int size()`	返回集合的大小	1.2
`boolean isEmpty()`	集合是否为空	1.2
`boolean contains(Object o)`	接口默认方法,返回一个可分割的迭代器	1.2
`Object[] toArray()`	将集合转为`Object[]`	1.2
`<T> T[] toArray(T[] a)`	将集合转为`T[]`, 上面的功能更强大	1.2
`boolean add(E e)`	添加元素到集合	1.2
`boolean remove(Object o)`	从集合中删除元素	1.2
`boolean containsAll(Collection<?> c)`	该集合是否包含所有`c`中的元素	1.2
`boolean addAll(Collection<? extends E> c)`	将`c`中的元素都加入该集合	1.2
`boolean removeAll(Collection<?> c)`	将`c`中的元素全部从该集合中移除	1.2
`default boolean removeIf(Predicate<? super E> filter)`	将满足条件的元素从该集合中移除	1.8
`boolean retainAll(Collection<?> c)`	该集合只保留出现在`c`中的元素	1.2
`void clear()`	清空该集合	1.2
`default Stream<E> stream()`	返回一个`Stream`	1.8
`default Stream<E> parallelStream()`	返回一个可并行的`Stream`	1.8

default boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    boolean removed = false;
    final Iterator<E> each = iterator();
    while (each.hasNext()) {
        if (filter.test(each.next())) {
            each.remove();
            removed = true;
        }
    }
    return removed;
}

集合类的API都提供了:

处理单个元素
处理多个元素
串行处理
并行处理

1.3 `List`

public interface List<E> extends Collection<E>

由于List 继承了Collection, 下面的API将只展示List独有的

方法	含义	出现版本
`boolean addAll(int index, Collection<? extends E> c)`	从某个位置开始插入一个集合	1.2
`default void replaceAll(UnaryOperator<E> operator)`	将集合中的元素通过一个函数替换掉	1.8
`default void sort(Comparator<? super E> c)`	对该集合进行`in-place`的排序	1.8
`E get(int index)`	获取某个位置的元素值	1.2
`E set(int index, E element)`	设置某个位置的元素值	1.2
`void add(int index, E element)`	在某个位置前添加某个元素, 其余元素后移	1.2
`E remove(int index)`	移除某个位置的元素, 其余元素前移	1.2
`int indexOf(Object o)`	某个元素在该集合第一次出现的位置	1.2
`int lastIndexOf(Object o)`	某个元素在该集合最后一次出现的位置	1.2
`ListIterator<E> listIterator()`	返回一个`ListIterator`	1.2
`ListIterator<E> listIterator(int index)`	返回一个从某个位置开始的`ListIterator`	1.2
`List<E> subList(int fromIndex, int toIndex)`	返回一个子序列	1.2

default void replaceAll(UnaryOperator<E> operator) {
    Objects.requireNonNull(operator);
    final ListIterator<E> li = this.listIterator();
    while (li.hasNext()) {
        li.set(operator.apply(li.next()));
    }
}

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

1.4 `AbstractCollection`

public abstract class AbstractCollection<E> implements Collection<E>

作为一个抽象类,提供了一个半成品的实现

// 由于需要对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;
}

// 可以看到,当我们允许迭代器并发修改的时候,会出现一些异常情况需要处理
public Object[] toArray() {
    // Estimate size of array; be prepared to see more or fewer elements
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    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 <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);
}

// 这里的重点是: 怎么利用反射生成一个特定类型的数组 
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;
}

1.5 `AbstractList`

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
        // 用来记录对集合大小有影响的操作的次数
    // 这个变量的使用都在内部迭代器里面
    protected transient int modCount = 0;
}

这里的AbstractList和上面的AbstractCollection都是给定了一些默认方法的实现

其中iterator的实现参考如下:

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

1.5.1 `ListIterator`

public interface ListIterator<E> extends Iterator<E>

ListIterator的存储示意图如下:

  Element(0)   Element(1)   Element(2)   ... Element(n-1)
^            ^            ^            ^                  ^

其中上箭头表示cursor的位置, 并且允许双向的遍历整个集合

方法	含义
`boolean hasPrevious()`	前面是否有元素
`E previous()`	返回前面的元素
`boolean hasNext()`	继承自`Iterator`
`E next()`	继承自`Iterator`
`int nextIndex()`	index of (next())
`int previousIndex()`	index of (previous())
`void set(E e)`	用来替换`next()`或`previous()` 返回的元素
`void add(E e)`	在`cursor`的位置添加一个元素

这里摘抄listIterator的实现:

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 {
            // 这里使用`lastRet` 来进行赋值
            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();
        }
    }
    
}

1.6 `RandomAccess`

用来标识该集合支持O(1)的随机查询, 一般来讲如果:

for (int i=0, n=list.size(); i &lt; n; i++)
    list.get(i);

// 比
for (Iterator i=list.iterator(); i.hasNext(); )
    i.next();
// 快

那么该类就可以实现这个接口

2. `ArrayList` 里面的一些具体实现

2.1 存储结构

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     * 这个主要是为了区分是不是从默认的初始化构造函数来的
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  
    /**
     * 1. 使用数组来存储
     * 2. 对象类型为Object[], 而不是 E[]
     */
    transient Object[] elementData;
}

2.2 添加元素

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

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

扩容细节:

新容量: newCapacity = oldCapacity + (oldCapacity >> 1)
修改modCount


private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

        // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

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

2.3 删除元素

删除元素并没对数组的容量进行减少, 只是进行了平移,并对空位进行了null化

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

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
}

2.4 `removeIf`

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

这里我们可以看到没有进行数组内存的再次申请, 也没有使用迭代器来remove数据, 只是需要多遍历一次数组

ref:

老司机的轻车熟路，闲庭信步是如何养成的？
java8 源码

Java学习笔记之ArrayList基本用法
申明：非原创，转载自 Java学习笔记之ArrayList基本用法 ArrayList简介 ArrayList是一...
ArrayList 扩容 Android Java 真的不一
以前学java基础的时候看过ArrayList的扩容机制实现原理是下面这样当时做的笔记ArrayList扩容...
Java ArrayList操作英文书目录
Java ArrayList ListIterator example Java ArrayList Iterat...
Java ArrayList 笔记
Java ArrayList 笔记 remove 操作是否会缩容 modCount 起什么作用是否线程安全如果...
Java学习笔记——LinkedList插入和删除真的比Arra
Java学习笔记——LinkedList插入和删除真的比ArrayList快吗[https://blog.csdn...
java 集合 1 - ArrayList
java 集合 1 - ArrayList 参考文章：图解集合1：ArrayList ArrayList使用的数据...
JAVA ArrayList学习笔记
ArrayList ArrayList类支持能够按需增长的动态数组，增长策略oldCapacity + (oldC...
Java ArrayList阅读笔记
ArrayList: 默认初始化容量为10；每次插入前先进行扩容检测及扩容，扩容大小为原容量的一半（例：10+5...
java基础-泛型中的extends和super
List numbers = new ArrayList (); java的ArrayList有一...
ArrayList 源码分析
ArrayList简介： ArrayList 属于 Java 中的高级数据的集合框架。项目包在 java.uti...

Java ArrayList 笔记

Java ArrayList 笔记

1. 继承关系梳理

1.1 `Iterable`

1.2 `Collection`

1.3 `List`

1.4 `AbstractCollection`

1.5 `AbstractList`

1.5.1 `ListIterator`

1.6 `RandomAccess`

2. `ArrayList` 里面的一些具体实现

2.1 存储结构

2.2 添加元素

2.3 删除元素

2.4 `removeIf`

相关文章

Java学习笔记之ArrayList基本用法

ArrayList 扩容 Android Java 真的不一

Java ArrayList操作英文书目录

Java ArrayList 笔记

Java学习笔记——LinkedList插入和删除真的比Arra

java 集合 1 - ArrayList

JAVA ArrayList学习笔记

Java ArrayList阅读笔记

java基础-泛型中的extends和super

ArrayList 源码分析

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Java ArrayList 笔记

Java ArrayList 笔记

1. 继承关系梳理

1.1 Iterable

1.2 Collection

1.3 List

1.4 AbstractCollection

1.5 AbstractList

1.5.1 ListIterator

1.6 RandomAccess

2. ArrayList 里面的一些具体实现

2.1 存储结构

2.2 添加元素

2.3 删除元素

2.4 removeIf

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

1.1 `Iterable`

1.2 `Collection`

1.3 `List`

1.4 `AbstractCollection`

1.5 `AbstractList`

1.5.1 `ListIterator`

1.6 `RandomAccess`

2. `ArrayList` 里面的一些具体实现

2.4 `removeIf`