方圆

jcf-arrayList

2019-09-22

1. Important Variables

1
2
3
4
5
6
7
8
// 用数组来存储元素
transient Object[] elementData;
// 默认容量为10;
private static final int DEFAULT_CAPACITY = 10;
// 存储元素的数量;
private int size;
// 被结构性修改的次数,在迭代器中使用
protected transient int modCount = 0;

2. Main Methods

  • constructor

    1. 无参数时,直接elementData 赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    2. 参数为int(初始容量)时,容量>0则建立对应大小数组,==0则赋值为EMPTY_ELEMENTDATA
    3. 参数为Collection,调用传入集合的toArray方法赋值给elementData,如果elementData.length !=0 :检查是否得到对象数组,如果没有,只复制size的大小;否则将elementData赋值为EMPTY_ELEMENTDATA.
  • set()
    索引范围检查、获取旧值、保存新值到索引位置,return旧值。

  • add()

    1. add(int index, E element)添加元素到指定位置,相当于insert,相比于add(E e),前者需要先保证index在 [0, size] 内

    2. 保证 minCapacity=size+1的位置:最终的增长通过grow方法实现:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
              private void grow(int minCapacity) {
      int oldCapacity = elementData.length;
      // 1.5 倍
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      if (newCapacity - minCapacity < 0)
      newCapacity = minCapacity;
      // MAX_ARRAY_SIZE= 2^32-1-8
      if (newCapacity - MAX_ARRAY_SIZE > 0)
      // 如果minCapacity>MAX_ARRAY_SIZE,赋值 2^32-1
      newCapacity = hugeCapacity(minCapacity);
      elementData = Arrays.copyOf(elementData, newCapacity);
      }
      ```

      + get()
      范围检查,合格就返回对应位置对象即可(返回前将类型转换为声明集合时的类型)。
      + addAll()
      方法和add一样也有两种,从指定位置添加和从末尾添加,过程和add类似:空间检查、自动扩容、数组拷贝、如果从指定位置添加,也会涉及元素移动(多调用一次数组拷贝)。
      add多数据时,使用addAll只需要一次拷贝,比循环add多次拷贝高效。
      + remove()
      `remove(int index)`移除指定位置; `remove(Object o)`移除第一个`o.equals(elementData[index])`或者o为null时`elementData[index] == null`的元素。都会涉及元素的移动,然后`elementData[--size] = null;`(可GC,否则会一直不回收,内存泄漏)。

      ## 3. Others
      1. 序列化
      `elementData`使用`transient`标识,标识[序列化](/detail/48)时省略,`ArrayList`也是自定义`writeObject`实现序列化,直接序列化`elementData`会序列化部分未使用的空间。这里序列化完成后和`expectedModCount`比较,也就是要求序列化过程中容器数据不能被修改。

      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();

      }
      }

      1
      2
      反序列化也是自定义实现,读取数据并重建:

      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
       int capacity = calculateCapacity(elementData, size);
       SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, 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();
       }

      }
      }
      ```

Tags: jcf
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章