新手学源码__ArrayList源码

秒速五厘米 2022-05-27 10:08 211阅读 0赞

## 前景 ##

今天看了些集合的知识，感觉都是比较熟悉的那些，但是总觉得只知道怎么用，具体的细节部分我还是想去了解一下，根据别人前几年的博客，沿着这个思路去熟悉熟悉～一天一个或者两个把，又到看源码的时候咯～

## ArrayList ##

### 简介 ###

数组列表，是数组的一个升级版把，能够动态的去增加数组的大小，扩容还是厉害啊～不过扩容也是要付出代价的，意味着数据的全部复制，重新创建新数组，它实现了List的接口。ArrayList是非同步的，当两个线程同时进行读的时候没毛病，但是如果一个在读一个在写，就会出现问题了。

### 直接源码 ###

#### 底层实现 ####

都知道，说ArrayList是动态的数组，那么它也是数组把？实际上确实是的，它的最底层也是用数组实现的

transient Object[] elementData;

关于这个关键字transient，这里有一段关于它的介绍:

> 我们都知道一个对象只要实现了Serilizable接口，这个对象就可以被序列化，java的这种序列化模式为开发者提供了很多便利，我们可以不必关系具体序列化的过程，只要这个类实现了Serilizable接口，这个类的所有属性和方法都会自动序列化。
> 
> 然而在实际开发过程中，我们常常会遇到这样的问题，这个类的有些属性需要序列化，而其他属性不需要被序列化，打个比方，如果一个用户有一些敏感信息（如密码，银行卡号等），为了安全起见，不希望在网络操作（主要涉及到序列化操作，本地序列化缓存也适用）中被传输，这些信息对应的变量就可以加上transient关键字。换句话说，这个字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。
> 
> 总之，java 的transient关键字为我们提供了便利，你只需要实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。

from : [http://www.cnblogs.com/lanxuezaipiao/p/3369962.html][http_www.cnblogs.com_lanxuezaipiao_p_3369962.html]  
总的来说，为了防止反序列化把，这不是我们的重点，所以一带而过,我们可以看到，动态数组的底层是一个简单的数组容器

#### 构造函数 ####

构造一个初始容量为10的数组

public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }

构建一个制定容量的数组，并对传入的值进行检测

public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }

构建一个数组，这个数组包含了另外一个collection，并且按照这个collection的迭代器返回它们的顺序排列，意思就是说，还按照原来的顺序

public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                // defend against c.toArray (incorrectly) not returning Object[]
                // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

#### 增加新元素 ####

增加制定类型的一个元素

public boolean add(E e) {
            modCount++;
            add(e, elementData, size);
            return true;
        }

看一下它的方法调用，先进行数组满的判断，然后再在尾部插入，时间复杂度为O(1)

private void add(E e, Object[] elementData, int s) {
            if (s == elementData.length)
                elementData = grow();
            elementData[s] = e;
            size = s + 1;
        }

grow方法

private Object[] grow() {
            return grow(size + 1);
        }

private Object[] grow(int minCapacity) {
            return elementData = Arrays.copyOf(elementData,
                                               newCapacity(minCapacity));
        }

重点部分，扩容的内部逻辑

// 这个最小值为长度+1
        private int newCapacity(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            // 扩容默认的大小，1.5倍！右移了一位
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 如果新容量小于最小容量大小
            if (newCapacity - minCapacity <= 0) {
                // ArrayList为空的时候，取10和min中较大的
                if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                    return Math.max(DEFAULT_CAPACITY, minCapacity);
                // 最小小于0报错
                if (minCapacity < 0) // overflow
                    throw new OutOfMemoryError();
                return minCapacity;
            }
            // 对于超过数组大小最大值的，进行额外处理，不可能让它超过最大值的
            return (newCapacity - MAX_ARRAY_SIZE <= 0)
                ? newCapacity
                : hugeCapacity(minCapacity);
        }

**分析：**  
实际实现扩容的操作,我们可以看到是进行了数组的拷贝复制的，但是并没有new- -，而是用原来的数组重新引用了，所以看上去好像就是在原来的数组上动的，其实就是引用没变，变了空间和python的扩容一样，不过它这里的扩容，1.5倍，所以它的扩容要么是原来的1.5倍，要么是10,要么是原来的+1

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

在指定位置插入，单个元素

public void add(int index, E element) {
            // 防止 索引溢出
            rangeCheckForAdd(index);
            modCount++;
            final int s;
            Object[] elementData;
            // 已满，扩容
            if ((s = size) == (elementData = this.elementData).length)
                elementData = grow();
             // 将index+1位置全部后移1个，空出这个位置供插入，可以发现移位的操作还是比较繁琐的
            System.arraycopy(elementData, index,
                             elementData, index + 1,
                             s - index);
            elementData[index] = element;
            size = s + 1;
        }

尾插入一个集合

public boolean addAll(Collection<? extends E> c) {
            Object[] a = c.toArray();
            modCount++;
            int numNew = a.length;
            if (numNew == 0)
                return false;
            Object[] elementData;
            final int s;
            if (numNew > (elementData = this.elementData).length - (s = size))
                elementData = grow(s + numNew);
            System.arraycopy(a, 0, elementData, s, numNew);
            size = s + numNew;
            return true;
        }

也是一种判断扩容处理，相应的还有在指定位置插入集合，差不多就不看了

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

#### 删除 ####

**删除单个元素并返回**

public E remove(int index) {
            Objects.checkIndex(index, size);
    
            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;
        }

删除的同时，还会返回被删除的值，同时移动数组，进行空间回收，modCount是计数器，每执行这里面的方法，修改了原来的ArrayList就会+1，怪不得一直有这玩意儿- -

**删除不返回**

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
        }

关于接下来的高效删除算法，感觉看了意义不大，就跳过了。比如removeIf(Predicate

#### 改 ####

**set**更改元素  
不会修改modCount

public E set(int index, E element) {
            Objects.checkIndex(index, size);
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }

更改这个元素，同时返回老的元素

#### 查 ####

public E get(int index) {
            Objects.checkIndex(index, size);
            return elementData(index);
        }

#### ModCount ####

哈哈，到处都是它的身影，终于让我逮住它了！它到底是干嘛用的呢？原来是跟同步有关的，任何线程不安全的都会维护这个值，这个值是在AabstractList中维护的

protected transient int modCount = 0;

保护类型，当前包及其子类可见。用在了实现Iterator迭代器中，具体怎么实现我们暂时不看，只看这个值的作用

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;
    
            // prevent creating a synthetic constructor
            Itr() {}
    
            public boolean hasNext() {
                return cursor != size;
            }
        //每次next之前先检查这个值
            @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
            public void forEachRemaining(Consumer<? super E> action) {
                Objects.requireNonNull(action);
                final int size = ArrayList.this.size;
                int i = cursor;
                if (i < size) {
                    final Object[] es = elementData;
                    if (i >= es.length)
                        throw new ConcurrentModificationException();
                    for (; i < size && modCount == expectedModCount; i++)
                        action.accept(elementAt(es, i));
                    // update once at end to reduce heap write traffic
                    cursor = i;
                    lastRet = i - 1;
                    checkForComodification();
                }
            }
           // 检查这个值是否变化，意思就是，不能在它进行迭代的时候，被别的人进行add，delete等
            final void checkForComodification() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
        }

现在我们就明白了，这个值相当于一个证明的信号，证明我的这个没被人动过，但是set方法替换值却不会影响modCount值，就像数据库的幻读一样

#### trimToSize() ####

public void trimToSize() {
            modCount++;
            if (size < elementData.length) {
                elementData = (size == 0)
                  ? EMPTY_ELEMENTDATA
                  : Arrays.copyOf(elementData, size);
            }
        }

将数组列表容量削减到当前尺寸

#### ensureCapacity(int) ####

public void ensureCapacity(int minCapacity) {
            if (minCapacity > elementData.length
                && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
                     && minCapacity <= DEFAULT_CAPACITY)) {
                modCount++;
                grow(minCapacity);
            }
        }

确保不需要再分配容量的情况下固定容量的大小

## 总结 ##

1、今天呢，主要是好好看了扩容和线程机制，扩容的策略正常是1.5倍，或10,或最小min，有保护机制，不会超出最大值，  
2、线程安全，基础是用一个modCount来维护的，实现在迭代器里面，set，get并不会修改这个值，意味幻读是允许的  
3、效率：查，改效率高，增操作效率不高  
4、遗留问题：vector和Arraylist对比，目前知道的，线程安全和扩容不一样，但是具体的还要等到学到并发，线程什么的再回过头来看看。  
5、阅读源码，耗时！收获很大！

[http_www.cnblogs.com_lanxuezaipiao_p_3369962.html]: http://www.cnblogs.com/lanxuezaipiao/p/3369962.html