Java源码研究_集合_ArrayList

一时失言乱红尘 2022-11-20 04:51 210阅读 0赞

## ArrayList概述 ##

*  ArrayList是**容量可以改变**的**非线程安全**的集合.内部**使用数组实现**,**数组扩容时会创建更大的数组空间(原空间的1.5倍),把原来的数据复制到新数组空间中**.
 *  **ArrayList支持对元素的快速随机访问O(1),但是随机插入和删除时速度通常非常慢O(n),(除非是发生在数组的尾部,并且没有触发扩容操作),因为这个过程如果不是发生在数组尾部,需要移动其他元素(因为数组的内存空间是连续的),或者进行扩容.**

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

## 日常使用注意的问题 ##

1.  注意指定合适大小的集合容量,避免扩容影响性能

//推荐使用
    		    ArrayList list3 = new ArrayList(n);		    
    			//不推荐使用
    		    ArrayList list = new ArrayList();

1.  ArrayList适合用在读多,顺序新增删除元素,基本没有随机新增和随机删除的场景中  
    读取元素O(1)  
    顺序新增和删除元素(也就是在末尾新增)O(1)  
    随机新增和删除O(n)
2.  Arrays.asList方法进行数组转集合的问题  
    Arrays.asList返回的是Arrays的内部类java.util.Arrays.ArrayList  
    而不是java.util.ArrayList,  
    内部类中没有实现集合的add,remove,clear方法,调用都会报错(错误信息在父类java.util.AbstractList中抛出).
    
    且内部类的数组是final修饰的,不允许修改指向的数组.

private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess, java.io.Serializable
    { 
        private static final long serialVersionUID = -2764017481108945198L;
        private final E[] a;
    	
    }

解决方案:创建一个新的java.util.ArrayList集合,入参就是Arrays.asList(strings)

List<String> list3 = new ArrayList<String>(Arrays.asList(strings));
    list3.add("33");

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

## 源码分析 ##

*  创建集合对象

一般而言.最好是在初始化集的时候,就指定好合适的大小,避免后续扩容带来的性能损耗

//全局默认的空数组
    	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
       //不带参数的构造器,默认分配一个指向全局空数组的集合,不推荐使用
        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 boolean add(E e) { 
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    	
        private void ensureCapacityInternal(int minCapacity) { 
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
    	
    	//查看是否是默认的空数组,是的话就返回10或者当前要添加的元素数量两者之间的最大值.
    	private static int calculateCapacity(Object[] elementData, int minCapacity) { 
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }
    	//当前需要添加的元素数量+原有的数组中已经存在的元素数量(size字段)>数组的长度时(elementData.length),进行扩容
        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;
    		/* oldCapacity >> 1,右移一位,等于除以2,也就是说每次在原来的基础上,扩容50%, 扩容后容量=原始容量*1.5(取整) */
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            //如果扩容1.5倍后的新的容量比所需容量还要小,就直接取所需容量
            //为什么要用减法呢?而不是>,减法比>还要快吗
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
    		/* private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 因为有些VM会在Array中放入一些头部信息,所以要用-8的方式来使得这些头部信息正常 如果扩容1.5倍之后,超过了int的最大值(变成了负数),则取int的最大值 */
            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);
        }
    
    	//判断需要的容量有没有超过最大值MAX_ARRAY_SIZE,超过就只扩容到Integer.MAX_VALUE
        private static int hugeCapacity(int minCapacity) { 
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

所以当集合初始化的时候,如果创建的是一个未指定初始容量大小的时候,第一次放入一个元素,就会触发一次扩容(从0变成10或者所需元素的大小,并复制默认的空数组到新的集合)  
所以为了避免这种多余的操作,可以默认初始化一个合适大小的集合长度  
当初始化了一个默认的空集合的时候,加入1000个元素,触发的扩容次数为13次(第一次从10开始,每次递增1.5倍),每次增长的空间如下.  
10,15,22,33,50,75,113,170,256,384,576,864,1296

*  元素在某个索引位置上新增,删除等操作带来的元素移动  
    平均移动公式:(n+1)\*(n/2)/n=(n+1)/2,时间复杂度为O(n)

public void add(int index, E element) { 
            rangeCheckForAdd(index);
    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
    		/* 将index下标以及之后的元素,整体向后移动一位,空出index的位置 平均移动公式:(n+1)*(n/2)/n=(n+1)/2,时间复杂度为O(n) */
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }
    	private void rangeCheckForAdd(int index) { 
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    	
    	public E remove(int index) { 
            rangeCheck(index);
    
            modCount++;
            E oldValue = elementData(index);
    		/* 判断删除的元素是不是在数组元素的最后一个,是的话就不需要移动元素. 不是的话,就要移动size - index - 1个元素 */
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
    							 
    		//加入放入的位置不连续,这里删除是不是就会有问题?
    		//答案:不会,因为是按索引位置删除的
    		//新增的时候,index新增的位置,也不允许超过size(也就是说,都只能按顺序一个个位置的新增,不能跳过)
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }
    	
    	private void rangeCheck(int index) { 
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

*  元素复制到新数组的操作  
    最终是调用了本地方法System.arraycopy

public static <T> T[] copyOf(T[] original, int newLength) { 
            return (T[]) copyOf(original, newLength, original.getClass());
        }
    
    	public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { 
            @SuppressWarnings("unchecked")
            T[] copy = ((Object)newType == (Object)Object[].class)
                ? (T[]) new Object[newLength]
                : (T[]) Array.newInstance(newType.getComponentType(), newLength);
            System.arraycopy(original, 0, copy, 0,
                             Math.min(original.length, newLength));
            return copy;
        }
    
    //最终是调用了本地方法System.arraycopy
    	public static native void arraycopy(Object src,  int  srcPos,
                                            Object dest, int destPos,
                                            int length);

*  判断是否包含元素  
    是用遍历所有元素,进行equals的判断来找到元素

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

*  数组中允许放置的最多的元素数量  
    Integer.MAX\_VALUE=2,147,483,647,最大值大约是二十一亿  
    假设放入的是最小的数据类型boolean,每个1个字节,(基本数据类型没有只占1位的那种数据)  
    2,147,483,647个boolean大约占空间数量为2GB

1024*1024*1024=1GB=1,073,741,824B

*  只能顺序新增,不能随机新增元素  
    意思就是说,所有入参的index都不能大于size字段  
    size代表数组中已经有多少个元素了(数组下标从0开始),  
    elementData.length表示数组总共可以存储多少个元素,elementData.length>=size

//检查当前要插入的位置是否超过size,超过就数组下标越界错误
        private void rangeCheckForAdd(int index) { 
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
        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++;
        }

*  为什么要用transient 修饰实际存储的元素Object\[\] elementData

transient 表示此字段在类的序列化的时候将忽略.因为集合序列化的时候,系统会调用writeObject写入流中,在网络客户端反序列化readObject时,会重新赋值到新的elementData中.为什么多此一举?

答案:  
因为在elementData容量经常会大于实际存储元素的数量,所以只需要发送真正有实际值的数组元素即可.

其他的集合,都有类似的问题,并且都采用了同样的解决方案(都是因为实际存储元素往往小于申请的容量,避免了序列化的浪费)  
源码如下

/** * Save the state of the <tt>ArrayList</tt> instance to a stream (that * is, serialize it). * * @serialData The length of the array backing the <tt>ArrayList</tt> * instance is emitted (int), followed by all of its elements * (each an <tt>Object</tt>) in the proper order. */
        private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException{ 
            // Write out element count, and any hidden stuff
            int expectedModCount = modCount;
            s.defaultWriteObject();
    
            // Write out size as capacity for behavioural compatibility with clone()
            s.writeInt(size);
    
            // Write out all elements in the proper order.
            for (int i=0; i<size; i++) { 
                s.writeObject(elementData[i]);
            }
    
            if (modCount != expectedModCount) { 
                throw new ConcurrentModificationException();
            }
        }
    
        /** * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is, * deserialize it). */
        private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException { 
            elementData = EMPTY_ELEMENTDATA;
    
            // Read in size, and any hidden stuff
            s.defaultReadObject();
    
            // Read in capacity
            s.readInt(); // ignored
    
            if (size > 0) { 
                // be like clone(), allocate array based upon size not capacity
                ensureCapacityInternal(size);
    
                Object[] a = elementData;
                // Read in all elements in the proper order.
                for (int i=0; i<size; i++) { 
                    a[i] = s.readObject();
                }
            }
        }

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