[关闭]
@kiraSally 2018-03-12T18:40:07.000000Z 字数 11851 阅读 3328

集合番@ArrayList一文通(1.7版)

JAVA COLLECTIONS 源码 1.7版本


1.什么是ArrayList

2.ArrayList的数据结构

2.1 类定义

  1. public class ArrayList<E> extends AbstractList<E>
  2. implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  • 继承 AbstractList,实现了 List,它是一个数组队列,提供了相关的添加、删除、修改、遍历等功能
  • 实现 RandmoAccess 接口,实现快速随机访问:通过元素的序号快速获取元素对象
  • 实现 Cloneable 接口,重写 clone(),能被克隆(浅拷贝)
  • 实现 java.io.Serializable 接口,支持序列化

2.2 重要全局变量

  1. /**
  2. * The array buffer into which the elements of the ArrayList are stored.
  3. * The capacity of the ArrayList is the length of this array buffer. Any
  4. * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
  5. * DEFAULT_CAPACITY when the first element is added.
  6. * ArrayList底层实现为动态数组
  7. */
  8. private transient Object[] elementData;
  9. /**
  10. * The size of the ArrayList (the number of elements it contains).
  11. * 数组长度 :注意区分长度(当前数组已有的元素数量)和容量(当前数组可以拥有的元素数量)的概念
  12. * @serial
  13. */
  14. private int size;
  15. /**
  16. * The maximum size of array to allocate.Some VMs reserve some header words in an array.
  17. * Attempts to allocate larger arrays may result in OutOfMemoryError:
  18. * Requested array size exceeds VM limit
  19. * 数组所能允许的最大长度;如果超出就会报`内存溢出异常` -- 可怕后果就是宕机
  20. */
  21. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

2.3 构造器

  1. /**
  2. * Constructs an empty list with the specified initial capacity.
  3. * 创建一个指定容量的空列表
  4. * @param initialCapacity the initial capacity of the list
  5. * @throws IllegalArgumentException if the specified initial capacity is negative
  6. */
  7. public ArrayList(int initialCapacity) {
  8. super();
  9. if (initialCapacity < 0)
  10. throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
  11. this.elementData = new Object[initialCapacity];
  12. }
  13. /**
  14. * Constructs an empty list with an initial capacity of ten.
  15. * 默认容量为10
  16. */
  17. public ArrayList() {
  18. this(10);
  19. }
  20. /**
  21. * Constructs a list containing the elements of the specified collection,
  22. * in the order they are returned by the collection's iterator.
  23. * 接受一个Collection对象直接转换为ArrayList
  24. * @param c the collection whose elements are to be placed into this list
  25. * @throws NullPointerException if the specified collection is null 万恶的空指针异常
  26. */
  27. public ArrayList(Collection<? extends E> c) {
  28. elementData = c.toArray();//获取底层动态数组
  29. size = elementData.length;//获取底层动态数组的长度
  30. // c.toArray might (incorrectly) not return Object[] (see 6260652)
  31. if (elementData.getClass() != Object[].class)
  32. elementData = Arrays.copyOf(elementData, size, Object[].class);
  33. }

3.ArrayList的存储

3.1 概述

  • ArrayList在新增元素中,会执行一系列额外操作(包括扩容、各类异常校验 - 基本都跟长度相关)
  • ArrayList使用尾插入法,新增元素插入到数组末尾;支持动态扩容
  • add()常见的异常主要包括:IndexOutOfBoundsExceptionOutOfMemoryError

3.2 add方法

  1. /**
  2. * Appends the specified element to the end of this list.
  3. * 使用尾插入法,新增元素插入到数组末尾
  4. * 由于错误检测机制使用的是抛异常,所以直接返回true
  5. * @param e element to be appended to this list
  6. * @return <tt>true</tt> (as specified by {@link Collection#add})
  7. */
  8. public boolean add(E e) {
  9. //调整容量,修改elementData数组的指向; 当数组长度加1超过原容量时,会自动扩容
  10. ensureCapacityInternal(size + 1); // Increments modCount!! add属于结构性修改
  11. elementData[size++] = e;//尾部插入,长度+1
  12. return true;
  13. }
  14. /**
  15. * Inserts the specified element at the specified position in this list.
  16. * Shifts the element currently at that position (if any) and any subsequent elements to
  17. * the right (adds one to their indices).
  18. * 支持插入一个新元素到指定下标
  19. * 该操作会造成该下标之后的元素全部后移(使用时请慎重,避免数组长度过大)
  20. * @param index index at which the specified element is to be inserted
  21. * @param element element to be inserted
  22. * @throws IndexOutOfBoundsException {@inheritDoc}
  23. */
  24. public void add(int index, E element) {
  25. //下标边界校验,不符合规则 抛出 `IndexOutOfBoundsException`
  26. rangeCheckForAdd(index);
  27. //调整容量,修改elementData数组的指向; 当数组长度加1超过原容量时,会自动扩容
  28. ensureCapacityInternal(size + 1); // Increments modCount!!
  29. //注意是在原数组上进行位移操作,下标为 index+1 的元素统一往后移动一位
  30. System.arraycopy(elementData, index, elementData, index + 1,size - index);
  31. elementData[index] = element;//当前下标赋值
  32. size++;//数组长度+1
  33. }

3.3 System.arraycopy方法

  • 不推荐频繁插入或删除场景的原因在于其执行add或者remove方法时会调用非常耗时的System.arraycopy方法
  • 频繁插入或删除场景请选用LinkedList
  1. /**
  2. * 数组拷贝的native方法 -- 所有涉及数组移动的底层实现
  3. * @param src the source array. 源数组
  4. * @param srcPos starting position in the source array. 源数组要复制的起始位置
  5. * @param dest the destination array. 目的数组
  6. * @param destPos starting position in the destination data.目的数组放置的起始位置
  7. * @param length the number of array elements to be copied. 复制的长度
  8. * 注意:src and dest都必须是同类型或者可以进行转换类型的数组.
  9. */
  10. public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);

3.4 rangeCheckForAdd方法

  1. /**
  2. * A version of rangeCheck used by add and addAll.
  3. * 下标边界校验 : 下标必须为小于等于数组长度的正整数(Int)
  4. * 不符合规则 抛出 `IndexOutOfBoundsException` ,即 下标越界异常
  5. */
  6. private void rangeCheckForAdd(int index) {
  7. //下标超过数组长度 or 下标 < 0
  8. if (index > size || index < 0)
  9. throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  10. }

3.4 ensureCapacityInternal方法

  1. /**
  2. * 调整容量,修改elementData数组的指向
  3. */
  4. private void ensureCapacityInternal(int minCapacity) {
  5. modCount++; //add操作属于结构性变动,modCount计数+1
  6. // overflow-conscious code 溢出敏感
  7. if (minCapacity - elementData.length > 0)
  8. grow(minCapacity);//自动扩容
  9. }

3.5 grow方法

  1. /**
  2. * Increases the capacity to ensure that it can hold at least the
  3. * number of elements specified by the minimum capacity argument.
  4. * 当数组长度加1超过原容量时,会自动扩容 (size + 1)
  5. * @param minCapacity the desired minimum capacity
  6. */
  7. private void grow(int minCapacity) {
  8. // overflow-conscious code 溢出敏感
  9. int oldCapacity = elementData.length;
  10. //区别于HashMap的2倍扩容,ArratList选择是的1.5倍扩容(向上取整)
  11. //等同于 (int)Math.floor(oldCapacity*1.5) 或 (oldCapacity * 3)/2 + 1
  12. //PS:涉及到2次幂的操作推荐直接使用位运算,尤其是设置2次幂容量场景 eg : new ArrayList(x << 1)
  13. int newCapacity = oldCapacity + (oldCapacity >> 1);
  14. if (newCapacity - minCapacity < 0)
  15. newCapacity = minCapacity; //最小容量设置
  16. if (newCapacity - MAX_ARRAY_SIZE > 0)
  17. newCapacity = hugeCapacity(minCapacity); //最大容量设置
  18. // minCapacity is usually close to size, so this is a win:
  19. //新建一个原数组的拷贝,并修改原数组,指向这个新建数组;原数组自动抛弃,等待GC回收
  20. elementData = Arrays.copyOf(elementData, newCapacity);
  21. }

3.6 hugeCapacity方法

  1. /**
  2. * 最大容量设置
  3. */
  4. private static int hugeCapacity(int minCapacity) {
  5. if (minCapacity < 0) // overflow 内存溢出
  6. throw new OutOfMemoryError();
  7. //注意:最大容量是 Integer.MAX_VALUE 而不是 MAX_ARRAY_SIZE=Integer.MAX_VALUE-8
  8. return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE : MAX_ARRAY_SIZE=;
  9. }

3.7 内存溢出 VS 内存泄露

  • 内存溢出:程序在申请内存时,没有足够的内存空间供其使用
  • 内存泄露:程序在申请内存后,无法释放已申请的内存空间,一次内存泄露危害可以忽略,但内存泄露堆积后果很严重,无论多少内存,迟早会被占光
  • 各位请期待JVM系列,如果有机会的话会进一步解释

3.8 对于Integer.MAX_VALUE - 8的拓展解读

  • 根本作用在于只是为了避免一些机器内存溢出,是否-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.

4.ArrayList的读取

4.1 get方法

  1. /**
  2. * Returns the element at the specified position in this list.
  3. * 返回指定下标的元素
  4. * @param index index of the element to return
  5. * @return the element at the specified position in this list
  6. * @throws IndexOutOfBoundsException {@inheritDoc}
  7. */
  8. public E get(int index) {
  9. rangeCheck(index);//下标边界校验
  10. return elementData(index);//直接调用数组的下标方法
  11. }
  12. /**
  13. * 数组访问方法
  14. */
  15. @SuppressWarnings("unchecked")
  16. E elementData(int index) {
  17. return (E) elementData[index];
  18. }

4.2 rangeCheck方法

  1. /**
  2. * Checks if the given index is in range. If not, throws an appropriate
  3. * runtime exception. This method does *not* check if the index is
  4. * negative: It is always used immediately prior to an array access,
  5. * which throws an ArrayIndexOutOfBoundsException if index is negative.
  6. *
  7. * 当index>=数组长度时,抛出`IndexOutOfBoundsException` 下标越界
  8. * 当index为负数时,抛出`ArrayIndexOutOfBoundsException` 数组下标越界
  9. */
  10. private void rangeCheck(int index) {
  11. if (index >= size)
  12. throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  13. }

5.ArrayList的移除

5.1 remove方法

  1. /**
  2. * Removes the element at the specified position in this list.
  3. * Shifts any subsequent elements to the left (subtracts one from their indices).
  4. *
  5. * 移除指定下标元素,同时大于该下标的所有数组元素统一左移一位
  6. *
  7. * @param index the index of the element to be removed
  8. * @return the element that was removed from the list 返回原数组元素
  9. * @throws IndexOutOfBoundsException {@inheritDoc}
  10. */
  11. public E remove(int index) {
  12. rangeCheck(index);//下标边界校验
  13. E oldValue = elementData(index);//获取当前坐标元素
  14. fastRemove(int index);//这里我修改了一下源码,改成直接用fastRemove方法,逻辑不变
  15. return oldValue;//返回原数组元素
  16. }
  17. /**
  18. * Removes the first occurrence of the specified element from this list,if it is present.
  19. * If the list does not contain the element, it is unchanged.
  20. * More formally, removes the element with the lowest index <tt>i</tt> such that
  21. * <tt>(o==null?get(i)==null:o.equals(get(i)))</tt> (if such an element exists).
  22. * Returns <tt>true</tt> if this list contained the specified element
  23. * (or equivalently, if this list changed as a result of the call).
  24. * 直接移除某个元素:
  25. * 当该元素不存在,不会发生任何变化
  26. * 当该元素存在且成功移除时,返回true,否则false
  27. * 当有重复元素时,只删除第一次出现的同名元素 :
  28. * 例如只移除第一次出现的null(即下标最小时出现的null)
  29. * @param o element to be removed from this list, if present
  30. * @return <tt>true</tt> if this list contained the specified element
  31. */
  32. public boolean remove(Object o) {
  33. //按元素移除时都需要按顺序遍历找到该值,当数组长度过长时,相当耗时
  34. if (o == null) {//ArrayList允许null,需要额外进行null的处理(只处理第一次出现的null)
  35. for (int index = 0; index < size; index++)
  36. if (elementData[index] == null) {
  37. fastRemove(index);
  38. return true;
  39. }
  40. } else {
  41. for (int index = 0; index < size; index++)
  42. if (o.equals(elementData[index])) {
  43. fastRemove(index);
  44. return true;
  45. }
  46. }
  47. return false;
  48. }

5.2 fastRemove方法

  1. /*
  2. * Private remove method that skips bounds checking and does not return the value removed.
  3. * 私有方法,除去下标边界校验以及不返回移除操作的结果
  4. */
  5. private void fastRemove(int index) {
  6. modCount++;//remove操作属于结构性改动,modCount计数+1
  7. int numMoved = size - index - 1;//需要左移的长度
  8. if (numMoved > 0)
  9. //大于该下标的所有数组元素统一左移一位
  10. System.arraycopy(elementData, index+1, elementData, index,numMoved);
  11. elementData[--size] = null; // Let gc do its work 长度-1,同时加快gc
  12. }

5.3 clear方法

  1. /**
  2. * Removes all of the elements from this list. The list will be empty after this call returns.
  3. * 移除所有元素
  4. */
  5. public void clear() {
  6. modCount++;
  7. // Let gc do its work
  8. for (int i = 0; i < size; i++)
  9. elementData[i] = null;//每个元素设置为null,加速gc
  10. size = 0;//长度为0
  11. }

6.ArrayList的迭代

  1. //结构性变更操作必须使用迭代器
  2. Iterator iter = list.iterator();
  3. while (iter.hasNext()) {
  4. Integer o = (Integer)iter.next();
  5. }
  1. //快速读取时推荐使用随机访问方式
  2. for (int i=0; i < list.size(); i++) {
  3. Integer o = (Integer)list.get(i);
  4. }
  1. for (Object o:list) { }

7.ArrayList的序列化方法解析

7.1 writeObject方法

  1. /**
  2. * Save the state of the <tt>ArrayList</tt> instance to a stream (that is, serialize it).
  3. * 序列化 : 直接将size和element写入ObjectOutputStream
  4. *
  5. *@serialData The length of the array backing the <tt>ArrayList</tt> instance is emitted (int),
  6. * followed by all of its elements (each an <tt>Object</tt>) in the proper order.
  7. */
  8. private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
  9. // Write out element count, and any hidden stuff 序列化操作需要校验modCount
  10. int expectedModCount = modCount;
  11. s.defaultWriteObject();// 获取数组元素的Class信息
  12. // Write out array length 获取缓存数组长度
  13. s.writeInt(elementData.length);
  14. // Write out all elements in the proper order. 依次写入
  15. for (int i=0; i<size; i++)
  16. s.writeObject(elementData[i]);
  17. if (modCount != expectedModCount) {
  18. throw new ConcurrentModificationException();
  19. }
  20. }

7.2 readObject

  1. /**
  2. * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,deserialize it).
  3. * 反序列化:从ObjectInputStream获取size和element,再恢复到elementData
  4. */
  5. private void readObject(java.io.ObjectInputStream s)
  6. throws java.io.IOException, ClassNotFoundException {
  7. // Read in size, and any hidden stuff 获取数组元素的Class信息和数组长度
  8. s.defaultReadObject();
  9. // Read in array length and allocate array 获取数组长度并分配一个该长度动态数组(Object类型)
  10. int arrayLength = s.readInt();
  11. Object[] a = elementData = new Object[arrayLength];
  12. // Read in all elements in the proper order. 依次读出
  13. for (int i=0; i<size; i++)
  14. a[i] = s.readObject();
  15. }
  • 原因在于elementData是一个缓存数组,通常会预留一些容量,等容量不足时再扩充容量,那么有些空间可能就没有实际存储元素,采用上诉的方式来实现序列化时,就可以保证只序列化实际存储的那些元素,而非整个数组,从而节省空间和时间
  • 重点:根本是要区别size和capacity的概念,同时也是优化代码的一种策略

8.ArrayList的toArray方法异常

  • 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()
  1. public static Integer[] toArray(ArrayList<Integer> arrayList) {
  2. //调用 <T> T[] toArray(T[] contents),而不是 Object[] toArray()
  3. Integer[] newArrayList = (Integer[])arrayList.toArray(new Integer[0]);
  4. return newArrayList;
  5. }

集合番@ArrayList一文通(1.7版)黄志鹏kira 创作,采用 知识共享 署名-非商业性使用 4.0 国际 许可协议 进行许可。

本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注