@kiraSally
2018-03-12T10:40:07.000000Z
字数 11851
阅读 3209
JAVA COLLECTIONS 源码 1.7版本
- 笔者个人博客 kiraSally的掘金个人博客 感谢支持
VectorlinkedList设计模式系列中再讲解
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
- 继承
AbstractList，实现了List，它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能- 实现
RandmoAccess接口，实现快速随机访问：通过元素的序号快速获取元素对象- 实现
Cloneable接口，重写clone()，能被克隆（浅拷贝）- 实现
java.io.Serializable接口，支持序列化
/*** The array buffer into which the elements of the ArrayList are stored.* The capacity of the ArrayList is the length of this array buffer. Any* empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to* DEFAULT_CAPACITY when the first element is added.* ArrayList底层实现为动态数组*/private transient Object[] elementData;/*** The size of the ArrayList (the number of elements it contains).* 数组长度 ：注意区分长度（当前数组已有的元素数量）和容量（当前数组可以拥有的元素数量）的概念* @serial*/private int size;/*** The maximum size of array to allocate.Some VMs reserve some header words in an array.* Attempts to allocate larger arrays may result in OutOfMemoryError:* Requested array size exceeds VM limit* 数组所能允许的最大长度；如果超出就会报`内存溢出异常` -- 可怕后果就是宕机*/private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/*** Constructs an empty list with the specified initial capacity.* 创建一个指定容量的空列表* @param initialCapacity the initial capacity of the list* @throws IllegalArgumentException if the specified initial capacity is negative*/public ArrayList(int initialCapacity) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);this.elementData = new Object[initialCapacity];}/*** Constructs an empty list with an initial capacity of ten.* 默认容量为10*/public ArrayList() {this(10);}/*** Constructs a list containing the elements of the specified collection,* in the order they are returned by the collection's iterator.* 接受一个Collection对象直接转换为ArrayList* @param c the collection whose elements are to be placed into this list* @throws NullPointerException if the specified collection is null 万恶的空指针异常*/public ArrayList(Collection<? extends E> c) {elementData = c.toArray();//获取底层动态数组size = elementData.length;//获取底层动态数组的长度// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);}
- ArrayList在新增元素中，会执行一系列额外操作(包括扩容、各类异常校验 - 基本都跟长度相关)
- ArrayList使用尾插入法，新增元素插入到数组末尾；支持动态扩容
add()常见的异常主要包括：IndexOutOfBoundsException、OutOfMemoryError
/*** Appends the specified element to the end of this list.* 使用尾插入法，新增元素插入到数组末尾* 由于错误检测机制使用的是抛异常，所以直接返回true* @param e element to be appended to this list* @return <tt>true</tt> (as specified by {@link Collection#add})*/public boolean add(E e) {//调整容量，修改elementData数组的指向; 当数组长度加1超过原容量时，会自动扩容ensureCapacityInternal(size + 1); // Increments modCount!! add属于结构性修改elementData[size++] = e;//尾部插入，长度+1return true;}/*** Inserts the specified element at the specified position in this list.* Shifts the element currently at that position (if any) and any subsequent elements to* the right (adds one to their indices).* 支持插入一个新元素到指定下标* 该操作会造成该下标之后的元素全部后移（使用时请慎重，避免数组长度过大）* @param index index at which the specified element is to be inserted* @param element element to be inserted* @throws IndexOutOfBoundsException {@inheritDoc}*/public void add(int index, E element) {//下标边界校验，不符合规则 抛出 `IndexOutOfBoundsException`rangeCheckForAdd(index);//调整容量，修改elementData数组的指向; 当数组长度加1超过原容量时，会自动扩容ensureCapacityInternal(size + 1); // Increments modCount!!//注意是在原数组上进行位移操作，下标为 index+1 的元素统一往后移动一位System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = element;//当前下标赋值size++;//数组长度+1}
- 不推荐频繁插入或删除场景的原因在于其执行add或者remove方法时会调用非常耗时的
System.arraycopy方法- 频繁插入或删除场景请选用
LinkedList
/*** 数组拷贝的native方法 -- 所有涉及数组移动的底层实现* @param src the source array. 源数组* @param srcPos starting position in the source array. 源数组要复制的起始位置* @param dest the destination array. 目的数组* @param destPos starting position in the destination data.目的数组放置的起始位置* @param length the number of array elements to be copied. 复制的长度* 注意：src and dest都必须是同类型或者可以进行转换类型的数组．*/public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);
/*** A version of rangeCheck used by add and addAll.* 下标边界校验 ： 下标必须为小于等于数组长度的正整数（Int）* 不符合规则 抛出 `IndexOutOfBoundsException` ，即 下标越界异常*/private void rangeCheckForAdd(int index) {//下标超过数组长度 or 下标 < 0if (index > size || index < 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
/*** 调整容量，修改elementData数组的指向*/private void ensureCapacityInternal(int minCapacity) {modCount++; //add操作属于结构性变动，modCount计数+1// overflow-conscious code 溢出敏感if (minCapacity - elementData.length > 0)grow(minCapacity);//自动扩容}
/*** Increases the capacity to ensure that it can hold at least the* number of elements specified by the minimum capacity argument.* 当数组长度加1超过原容量时，会自动扩容 (size + 1)* @param minCapacity the desired minimum capacity*/private void grow(int minCapacity) {// overflow-conscious code 溢出敏感int oldCapacity = elementData.length;//区别于HashMap的2倍扩容，ArratList选择是的1.5倍扩容(向上取整)//等同于 (int)Math.floor(oldCapacity*1.5) 或 (oldCapacity * 3)/2 + 1//PS:涉及到2次幂的操作推荐直接使用位运算，尤其是设置2次幂容量场景 eg : new ArrayList(x << 1)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://新建一个原数组的拷贝，并修改原数组，指向这个新建数组；原数组自动抛弃，等待GC回收elementData = Arrays.copyOf(elementData, newCapacity);}
/*** 最大容量设置*/private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflow 内存溢出throw new OutOfMemoryError();//注意：最大容量是 Integer.MAX_VALUE 而不是 MAX_ARRAY_SIZE=Integer.MAX_VALUE-8return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE : MAX_ARRAY_SIZE=;}
- 内存溢出：程序在申请内存时，没有足够的内存空间供其使用
- 内存泄露：程序在申请内存后，无法释放已申请的内存空间，一次内存泄露危害可以忽略，但内存泄露堆积后果很严重，无论多少内存,迟早会被占光
各位请期待JVM系列,如果有机会的话会进一步解释
- 根本作用在于只是为了避免一些机器内存溢出，是否-8其实并不重要，实际最大长度还是Integer.MAX_VALUE
- 之所以要-8是因为有些版本的虚拟机会保留8个字节长度的header，下面以HotSpot为例
- For HotSpot:
- The object header consists of a mark word and a klass pointer.
- 对象的header由一个标识字和一个类指针构成
- The mark word has word size (4 byte on 32 bit architectures, 8 byte on 64 bit architectures)
- 标识字,(若系统为)32位则占4个字节，64位则占8个字节
- The klass pointer has word size on 32 bit architectures. On 64 bit architectures the klass pointer either has word size, but can also have 4 byte if the heap addresses can be encoded in these 4 bytes.
/*** Returns the element at the specified position in this list.* 返回指定下标的元素* @param index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E get(int index) {rangeCheck(index);//下标边界校验return elementData(index);//直接调用数组的下标方法}/*** 数组访问方法*/@SuppressWarnings("unchecked")E elementData(int index) {return (E) elementData[index];}
/*** Checks if the given index is in range. If not, throws an appropriate* runtime exception. This method does *not* check if the index is* negative: It is always used immediately prior to an array access,* which throws an ArrayIndexOutOfBoundsException if index is negative.** 当index>=数组长度时，抛出`IndexOutOfBoundsException` 下标越界* 当index为负数时，抛出`ArrayIndexOutOfBoundsException` 数组下标越界*/private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
/*** Removes the element at the specified position in this list.* Shifts any subsequent elements to the left (subtracts one from their indices).** 移除指定下标元素，同时大于该下标的所有数组元素统一左移一位** @param index the index of the element to be removed* @return the element that was removed from the list 返回原数组元素* @throws IndexOutOfBoundsException {@inheritDoc}*/public E remove(int index) {rangeCheck(index);//下标边界校验E oldValue = elementData(index);//获取当前坐标元素fastRemove(int index);//这里我修改了一下源码，改成直接用fastRemove方法，逻辑不变return oldValue;//返回原数组元素}/*** Removes the first occurrence of the specified element from this list,if it is present.* If the list does not contain the element, it is unchanged.* More formally, removes the element with the lowest index <tt>i</tt> such that* <tt>(o==null?get(i)==null:o.equals(get(i)))</tt> (if such an element exists).* Returns <tt>true</tt> if this list contained the specified element* (or equivalently, if this list changed as a result of the call).* 直接移除某个元素：* 当该元素不存在，不会发生任何变化* 当该元素存在且成功移除时，返回true，否则false* 当有重复元素时，只删除第一次出现的同名元素 ：* 例如只移除第一次出现的null（即下标最小时出现的null）* @param o element to be removed from this list, if present* @return <tt>true</tt> if this list contained the specified element*/public boolean remove(Object o) {//按元素移除时都需要按顺序遍历找到该值，当数组长度过长时，相当耗时if (o == null) {//ArrayList允许null，需要额外进行null的处理（只处理第一次出现的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 remove method that skips bounds checking and does not return the value removed.* 私有方法，除去下标边界校验以及不返回移除操作的结果*/private void fastRemove(int index) {modCount++;//remove操作属于结构性改动，modCount计数+1int numMoved = size - index - 1;//需要左移的长度if (numMoved > 0)//大于该下标的所有数组元素统一左移一位System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // Let gc do its work 长度-1，同时加快gc}
/*** Removes all of the elements from this list. The list will be empty after this call returns.* 移除所有元素*/public void clear() {modCount++;// Let gc do its workfor (int i = 0; i < size; i++)elementData[i] = null;//每个元素设置为null，加速gcsize = 0;//长度为0}
//结构性变更操作必须使用迭代器Iterator iter = list.iterator();while (iter.hasNext()) {Integer o = (Integer)iter.next();}
//快速读取时推荐使用随机访问方式for (int i=0; i < list.size(); i++) {Integer o = (Integer)list.get(i);}
for (Object o:list) { }
/*** Save the state of the <tt>ArrayList</tt> instance to a stream (that is, serialize it).* 序列化 ： 直接将size和element写入ObjectOutputStream**@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 序列化操作需要校验modCountint expectedModCount = modCount;s.defaultWriteObject();// 获取数组元素的Class信息// Write out array length 获取缓存数组长度s.writeInt(elementData.length);// 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).* 反序列化：从ObjectInputStream获取size和element，再恢复到elementData*/private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {// Read in size, and any hidden stuff 获取数组元素的Class信息和数组长度s.defaultReadObject();// Read in array length and allocate array 获取数组长度并分配一个该长度动态数组（Object类型）int arrayLength = s.readInt();Object[] a = elementData = new Object[arrayLength];// Read in all elements in the proper order. 依次读出for (int i=0; i<size; i++)a[i] = s.readObject();}
- 原因在于elementData是一个缓存数组，通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而非整个数组，从而节省空间和时间
- 重点：根本是要区别size和capacity的概念，同时也是优化代码的一种策略
toArray() 可能遇到过抛出java.lang.ClassCastException异常？
- ArrayList提供了2个
toArray()函数：
Object[] toArray();-- 调用toArray()函数会抛出java.lang.ClassCastException异常
<T> T[] toArray(T[] contents)-- 调用toArray(T[] contents)能正常返回T[]toArray()会抛出异常是因为toArray()返回的是Object[]数组，将Object[]转换为其它类型(如将Object[]转换为的Integer[])则会抛出java.lang.ClassCastException异常，因为Java不支持向下转型- 解决该问题的办法是调用
<T> T[] toArray(T[] contents)， 而不是Object[] toArray()
public static Integer[] toArray(ArrayList<Integer> arrayList) {//调用 <T> T[] toArray(T[] contents),而不是 Object[] toArray()Integer[] newArrayList = (Integer[])arrayList.toArray(new Integer[0]);return newArrayList;}
集合番@ArrayList一文通(1.7版) 由 黄志鹏kira 创作，采用 知识共享 署名-非商业性使用 4.0 国际 许可协议 进行许可。
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名。