资讯专栏INFORMATION COLUMN

ArrayList源码阅读分析

番茄西红柿 / 863人阅读

摘要:实现接口通过源码可以看到继承自实现了接口接口接口接口。因此也说明类是线程不安全的类。插入指定位置插入元素,其逻辑如下校验是否有效范围,否则抛出数组越界异常扩容确保能有效插入。双指针的思路,一个读指针,一个写指针。

ArrayList是最常用的一种集合类型。今天通过阅读源码的方式来加深对它的学习和理解。 ##实现接口

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

通过源码可以看到ArrayList继承自AbstractList,实现了List接口、RandomAccess接口、Cloneable接口、Serializable接口。 说明它具备以下特点:

浅拷贝

序列化

常量
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

DEFAULT_CAPACITY 表示默认的容量是10个元素。

成员变量
transient Object[] elementData;
private int size;

elementData为实际存储元素的数组,这里可以看到ArrayList的底层实际是一个数组。因此它具有数组的特点,随机读写快,插入删除慢。 transient关键字说明底层数组不能被序列化。 ??

构造函数
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);
        }
    }

指定容量构造,构造一个指定初始容量大小的数组。

public ArrayList(Collection<); {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 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) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

这里可以看到add方法是线程不安全的,因为size++操作并非原子操作。因此也说明ArrayList类是线程不安全的类。 ensureCapacityInternal()方法保证数组容量可以容纳新增的这个元素,不会出现数组越界的情况。

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

指定index位置插入元素,其逻辑如下:

    校验index是否有效范围,否则抛出数组越界异常.

    扩容确保能有效插入。

    将原数组index位置之后的元素全部后移一个位置。

    将index位置设置为待插入元素。

添加集合方法 追加集合
public boolean addAll(Collection<); {
        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;
    }

和追加单个元素的原理类似,不同之处在于追加方式在于使用System.arraycopy方法。

插入集合
public boolean addAll(int index, Collection<); {
        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;
    }

和插入单个元素的原理类似,不同之处在于index之后的元素往后移的位置为插入集合的长度。

移除元素方法 根据索引移除
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;
    }

逻辑如下:

    校验index是否合法,否则抛出数组越界异常

    将index+1及以后的元素往前移一个位置

    将最后一个元素置为null,同时size减一

    返回删除的元素值。

删除元素
 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(index) 方法作用相同,只是去掉了边界校验和返回值。

查询 通过索引获取元素
public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

原理就是通过数组获取指定index的元素。

从前往后查找第一个出现的元素
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++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
从后往前查找第一个出现的元素
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--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
集合运算 并集

并集就是addAll方法

交集
 public boolean retainAll(Collection<); {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
差集
public boolean removeAll(Collection<); {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

交集和差集都调用了batchRemove方法,通过一个boolean标记来表示要留下的是相同的一部分还是不同的一部分。 batchRemove方法的写法还是值得学习。

batchRemove
private boolean batchRemove(Collection<);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;
    }

双指针的思路,一个读指针,一个写指针。读指针每次往前增加一个位置,写指针遇到要保留的元素时,再往前移动一个位置。 最后,如果读指针没走到最后就异常了,那把剩下读指针剩下的元素拷贝到写指针之后。 如果写指针没到最后,说明写指针后面的元素都需要剔除,手动置为null,否则会内存泄露。 如果写指针走到了最后,说明一个元素都没有移除掉,所以返回false。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/7160.html

相关文章

  • ArrayList源码阅读分析

    摘要:实现接口通过源码可以看到继承自实现了接口接口接口接口。因此也说明类是线程不安全的类。插入指定位置插入元素,其逻辑如下校验是否有效范围,否则抛出数组越界异常扩容确保能有效插入。双指针的思路,一个读指针,一个写指针。ArrayList是最常用的一种集合类型。今天通过阅读源码的方式来加深对它的学习和理解。 ##实现接口 public class ArrayList extends Abstract...

    番茄西红柿 评论0 收藏0
  • ArrayList源码阅读分析

    摘要:实现接口通过源码可以看到继承自实现了接口接口接口接口。因此也说明类是线程不安全的类。插入指定位置插入元素,其逻辑如下校验是否有效范围,否则抛出数组越界异常扩容确保能有效插入。双指针的思路,一个读指针,一个写指针。ArrayList是最常用的一种集合类型。今天通过阅读源码的方式来加深对它的学习和理解。 ##实现接口 public class ArrayList extends Abstract...

    xiyang 评论0 收藏0
  • 源码|jdk源码-ArrayList与Vector源码阅读

    摘要:毕业两个星期了,开始成为一名正式的码农了。将指定位置的数据移除。但是问题是,为时,并不是直接一个大小为的数组,而是使用静态变量来代替。此外,函数还做了越界检查。返回迭代器,与之有一个搭配的辅助类。 毕业两个星期了,开始成为一名正式的java码农了。一直对偏底层比较感兴趣,想着深入自己的java技能,看书、读源码、总结、造轮子实践都是付诸行动的方法。说到看源码,就应该由简入难,逐渐加深,...

    0x584a 评论0 收藏0
  • ArrayList 源码详细分析

    摘要:源码分析构造方法有两个构造方法,一个是无参,另一个需传入初始容量值。所以我们可以把上面的代码转换一下,等价于下面形式这个时候,我们再去分析一下的迭代器源码就能找出原因。原因是删除元素后,元素计数器,而迭代器中的也等于,从而导致返回。 1.概述 ArrayList 是一种变长的集合类,基于定长数组实现。ArrayList 允许空值和重复元素,当往 ArrayList 中添加的元素数量大于...

    W4n9Hu1 评论0 收藏0
  • TOMCAT源码阅读总结(1)-TOMCAT的类加载体系

    摘要:加载器之间父子关系不是通过类继承的方式,而是通过对象变量的方式,来实现的。调用的方法,将设置为所有的获取各个类加载器相应的资源配置文件这些是具体配置在配置文件中的。 摘要 一直以来想看一下tomcat的源码,可以从头到尾理解一遍在整个web请求的处理过程中,容器完成的功能,容器怎么把一个url的请求的处理递交给了servlet,容器的pipeline是怎么设计的,容器的filter怎么...

    ChanceWong 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<