java数据结构与集合之ArrayList

前言：最近对Java的集合结合源码重新看了一遍，如有错误请立即指正

ArraryList

初始化 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; private static final Object[] 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); } }

如果初始化为无参数ArrayList,容量为0。初始化为有参ArrayList且参数为0，初始化为空，小于零抛出异常

扩容 private static final int DEFAULT_CAPACITY = 10; public boolean add(E e) { modCount++; add(e, elementData, size); return true; } private void add(E e, Object[] elementData, int s) { //s=size,判断list长度是否与容量大小相等，如果相等则需要扩容 if (s == elementData.length) elementData = grow(); //如果不需要扩容则直接对list进行赋值 elementData[s] = e; size = s + 1; } public void add(int index, E element) { //检测是否越界 rangeCheckForAdd(index); modCount++; final int s; Object[] elementData; //如果size刚好等于arraylist的容量大小，扩容 if ((s = size) == (elementData = this.elementData).length) elementData = grow(); System.arraycopy(elementData, index, elementData, index + 1, s - index); elementData[index] = element; size = s + 1; } private Object[] grow() { //如果进行无参扩容，默认参数为size+1,size+1为扩容最小容量 return grow(size + 1); } private Object[] grow(int minCapacity) { //复制 return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity)); } private int newCapacity(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //扩容按照原容量1.5倍进行 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity <= 0) { //用于无参构造方法的初始化默认为10的容量 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) return Math.max(DEFAULT_CAPACITY, minCapacity); //minCapacity超出int最大限度，溢出，抛出异常 if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return minCapacity; } //如果newCapacity大于MAX_ARRAY_size,则扩容为Integer.MAX_VAlUE return (newCapacity - MAX_ARRAY_SIZE <= 0) ? newCapacity : hugeCapacity(minCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

在调用add方法时，需要对list的容器大小进行一个判断 ，如果size大小正好等于容器长度，则需要一次扩容才能进行增加元素的操作，即扩容。由于无参构造方法时，初始化容量为0，此时调用add方法时，需要扩容，且此时扩容直接给到10的容量大小。扩容时，新的容器大小是原容器的1.5倍，此时考虑到扩容之后可能出现新容器大小大于int的最大长度而溢出的情况

toArray()方法 //无参构造返回object()对象 public Object[] toArray() { return Arrays.copyOf(elementData, size); } //有参构造中，先对a的长度进行判断，如果长度小于list长度，则调用Arrays.copyof方法进行复制，直接返回，此时并没有对传入数组a进行复制操作而是将复制好的数组返回 public <T> T[] toArray(T[] a) { if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); //容量足够时直接进行复制到数组a中 System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } 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; }

该方法主要包括三点：1.当进行无参构造时，反省丢失，返回类型为object。2.数组长度小于list长度，调用Arrays.copyof方法，方法内部重新创建一个数组，对该数组进行复制，返回该数组，没有对传入数组进行操作。3.容量足够时直接将list中的内容复制进a中

clone()浅拷贝 public Object clone() { try { //继承了object的clone方法进行浅拷贝 ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } }

浅拷贝：两个变量指示内存中的地址是不一样的，但是变量中的元素指向同一个元素。