今天有事吗?要不来学学ArrayList底层?

时间:2020-9-15 作者:admin

今天有事吗?可以抽半个小时时间从源码去学习ArrayList,从而彻底掌握它。

简介

ArrayList是一个数组集合。了解它的特性我们从源码看它继承以及实现的接口就可以。
首先它继承 AbstractList类,实现了List,RandomAccess、Cloneable、java.io.Serializable接口。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  1. List:提供List基本方法,同时让ArrayList有集合的方法以及行为属性。
  2. RandomAccess:该实现类支持随机访问,也就是下标访问 get(index)。
  3. Cloneable:该类是克隆的接口。不仅仅实现了浅拷贝,也可以重写该类去实现深拷贝。

浅拷贝:
基本数据类型的变量拷贝之后是独立的,不会随着源变量变动而变
String类型拷贝之后也是独立的
引用类型拷贝的是引用地址,拷贝前后的变量引用同一个堆中的对象。

深拷贝:
变量的所有引用类型变量(除了String)都需要实现Cloneable(数组可以直接调用clone方法),clone方法中,引用类型需要各

  1. java.io.Serializable:该类是序列化接口。

结合上面接口分析,所以ArrayList 是支持快速访问、复制、序列化的。

ArrayList类

基本属性

	//序列化版本号:类内容的改变会影响版本号变化,导致反序列化失败(自动生成或自己定义)
	private static final long serialVersionUID = 8683452581122892189L;
	
    //如果实例化时未指定容量,则在初次添加元素时会进行扩容使用此容量作为数组长度
    private static final int DEFAULT_CAPACITY = 10;
    
    //一个空由于某些操作导致数据变成空的数组
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    //利用无参构造器,无论创建多少个默认的ArrayList,只要不添加元素都会指向这个空数组节省空间
    //它和上面就是该数组再次添加元素会自动扩容10
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // ArrayList存储数据的地方  transient 是禁止序列化
    transient Object[] elementData; // non-private to simplify nested class access
    
    //ArrayList中的元素个数
    private int size;

ArrayList arr = new ArrayList();
arr.add(1);
size大小是10,而elementData大小是默认初始化大小10

构造方法

	/*
	把DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData
	第一次添加元素时容量扩大至 10 的。
	*/
	ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /*
	当 initialCapacity 为零时则是把 EMPTY_ELEMENTDATA 赋值给 elementData。 
	当 initialCapacity 大于零时初始化一个大小为 initialCapacity 
	的 object 数组并赋值给 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转换成数组,存储在elementData
	if c.toArray成object[]失败用Arrays.copyOf将elementData存储数据
	转换成object[]对象拷贝到elementData中
	*/
    //ArrayList(Collection<? extends E> c)
    public ArrayList(Collection<? extends E> c) {
        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;
        }
    }

基本操作

这部分的方法我就不介绍了,大家看看就行,ArrayList的很简单基础的操作。

public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

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

    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }

    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

修剪大小

//就是把ArrayList数组中的空位置给减掉了
public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

添加元素–默认尾部添加

	//在末尾添加元素
	public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    //如果elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA(创建的新数组)
    //按照取出来的最大值也就是10进行扩容elementData.
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    
    //操作数++,操作数用来多线程中一个线程正在操作ArrayList,而另一个也进行操作完成
    //导致该线程操作数变化从而引起报错,
    //if所需要的最小空间没有elementData数组长度大,就需要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    //ArrayList的elementData数组长度的最大值
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    //扩容操作  容量扩大原来容量的1.5倍,如果扩大1.5倍的数组长度还小于minCapacity
    //数组长度扩容到minCapacity,将新数组拷贝到elementData
    private void grow(int minCapacity) {
        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);
    }

想要提升ArrayList的大批量插入速度,我们可以减少扩容操作,给一个大的初始值进行创建ArrayList,这样做能够使得ArrayList的大批量插入元素速度变得非常快。

指定下标添加元素

public void add(int index, E element) {
		//检查下标是否越界,越界报错
        rangeCheckForAdd(index);
        
        //判断是否需要扩容,记录操作数
        ensureCapacityInternal(size + 1);
        //讲index位置之后的元素向后移动1个位置  
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //在index位置添加元素
        elementData[index] = element;
        size++;
    }

删除元素

//删除指定下标的元素
public E remove(int index) {
		//检查是否越界
        rangeCheck(index);
		//操作数++
        modCount++;
        //把下标是index的元素取出来
        E oldValue = elementData(index);

		//需要移动的长度,如果==0就不必拷贝移动了。ps:size = 1而index为0,那么删除一个元
		//素之后为空,就不必arraycopy
        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) {
    	//如果元素为null直接快速删除
        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
    }

迭代器 iterator

private class Itr implements Iterator<E> {
		//游标记录下一个元素的位置
        int cursor;       
        //上一个操作的元素位置,若为-1就是没有上一个操作的历史元素
        //个人理解就是返回上一步,如果-1就是无法返回上一步
        int lastRet = -1; 
		

        //期望操作数 快速失败判断条件,modCount是否发生变化。 
        int expectedModCount = modCount;
		//快速失败:modCound是一个全局变量。如果当用户A正在遍历arr,而这时候
		//B对arr进行add或者remove操作,导致modCount++,从而和expectedModCount不相同
		//直接进行报错。不然容易出现迭代器的越界,游标错位,遍历不全等各种问题。
        

        Itr() {}

		//是否还有下一个元素
        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        //后移
        public E next() {
        	//快速失败,检查modCount是否变化
            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;
            //把当前元素遍历出来,上一个操作元素位置lastRet可以赋值该位置
            return (E) elementData[lastRet = i];
        }

		//删除当前元素
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            //快速失败,检查modCount是否变化
            checkForComodification();

            try {
            	//移除当前元素
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

		//快速失败:判断modCount是否改变
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

iterator弊端:
1、只能进行remove操作,add、clear 等 Itr 中没有。
2、调用 remove 之前必须先调用 next。因为 remove 开始就对 lastRet 做了校验。而 lastRet 初始化时为 -1。
3、next 之后只可以调用一次 remove。因为 remove 会将 lastRet 重新初始化为 -1

总结

ArrayList是非常常用的一种数据结构,这里也只是对ArrayLitt类中常用的方法进行总结。另外大家从上面源码也可以看出
1.Arraylist并非线程安全的。
2.大批量元素创建并插入ArryList中,初始化它的容量进行创建,比默认容量为10创建之后扩容插入的速度提高非常大。

好了,这次分享就到这里了。希望我的博客对大家在学习java方面有些许帮助·······

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。