java集合之 ArrayList

青旅半醒 2022-05-12 15:12 244阅读 0赞

通过本文你将了解到 ArrayList 的如下信息

**目录**

ArrayList 简介

ArrayList源码分析

重要成员变量

底层数据结构：数组

默认初始容量：10

当前元素个数

重要方法

add(E e): 添加一个元素

grow(int minCapacity)：扩容

batchRemove(Collection c, boolean complement)：保留或者删除 c 集合中所包含的元素

set(int index, E element)：修改指定位置的元素

get(int index) ：查找指定位置的元素

遍历

总结

--------------------

# ArrayList 简介 #

ArrayList 是一个可存储包括 null 值的任意类型数据、支持动态扩容、有序（输入顺序与输出顺序一致）、查找效率高（时间复杂度O(1)）的一个集合。

# ArrayList源码分析 #

## 重要成员变量 ##

### 底层数据结构：数组 ###

//存储元素
    transient Object[] elementData; // non-private to simplify nested class access

transient表示不允许被序列化

### 默认初始容量：10 ###

private static final int DEFAULT_CAPACITY = 10;

### 当前元素个数 ###

private int size;

# 重要方法 #

## add(E e): 添加一个元素 ##

public boolean add(E e) {
            //确保有足够的容量
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            //在 size 下标处添加一个元素
            elementData[size++] = e;
            return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                //当前所需要的最小容量大于等于 10
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // 当前存储空间（数组容量）不够了
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
    }

简单描述：空间是否足够存储--->如果不够就进行扩容--->存储数据到 size 处

## grow(int minCapacity)：扩容 ##

在没有达到边界值的情况下，扩容后的数组容量 = 旧数组容量+旧数组容量/2

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

## batchRemove(Collection<?> c, boolean complement)：保留或者删除 c 集合中所包含的元素 ##

根据 complement 来决定是保留还是移除指定集合中存在的元素

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++)
                    //complement为true：保留 elementData 和 c 中都存在的元素（相当于求交集）
                    //complement为false：保留只存在于 elementaData 中，但是不存在于c中的元素
                    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;
        }

#   set(int index, E element)：修改指定位置的元素 #

public E set(int index, E element) {
            rangeCheck(index);
            
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
    }

# get(int index) ：查找指定位置的元素 #

public E get(int index) {
            rangeCheck(index);
    
            return elementData(index);
    }

# 遍历 #

ArrayList 内部实现了两种迭代器（Itr、ListItr）来遍历元素。本质都是根据数组下标来操作的

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();
            }
        }
    
        /**
         * An optimized version of AbstractList.ListItr
         */
        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();
                }
            }
        }

# 总结 #

上面通过增删改查四个具有代表性的方法分析了ArrayList 源码，ArrayList中的其它方法其实也是类似的，所以没有罗列出来。想要表达的中心思想是：ArrayList 底层数据结构是采用的是数组，所以对于查询会很快（直接根据数组下标），删除会比较满（会涉及到元素的移动）。对于数组的遍历，建议直接使用 for 循环，根据数组下标直接获取。