JDK源码分析

发布日期: 2019-07-18

文章字数: 2.4k

阅读时长: 10 分

jdk源码分析(2)-ArrayList

1.ArrayList简介

ArrayList是基于Object[] 数组的，也就是我们常说的动态数组。它能很方便的实现数组的增加删除等操作。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable</span>

1. ArrayList支持泛型，它继承自AbstractList，实现了List、RandomAccess、Cloneable、java.io.Serializable接口。
2. List接口定义了列表必须实现的方法。
3. RandomAccess是一个标记接口，接口内没有定义任何内容。
4. 实现了Cloneable接口的类，可以调用Object.clone方法返回该对象的浅拷贝。
5. 通过实现 java.io.Serializable 接口以实现序列化功能

2.ArrayList成员变量

private static final int DEFAULT_CAPACITY = 10;                        // 默认容量
private static final Object[] EMPTY_ELEMENTDATA = {};                  // 空实例的空数组对象
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  // 也是空数组对象，用于计算添加第一个元素时要膨胀多少
transient Object[] elementData;                                        // 存储内容的数组
private int size;                                                      // 存储的数量

**Java关键字 transient:**是为了在序列化时保护对象的某些域不被序列化

其中elementData被声明为了transient，那么ArrayList是如何实现序列化的呢？
查看writeObject和readObject的源码如下：

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

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

可以看到在序列化的时候是把elementData里面的元素逐个取出来放到ObjectOutputStream里面的；而在反序列化的时候也是把元素逐个拿出来放回到elementData里面的；

这样繁琐的操作，其中最重要的一个好处就是节省空间，因为elementData的大小是大于ArrayList中实际元素个数的。所以没必要将elementData整个序列化。

3.ArrayList构造函数

ArrayList的构造函数主要就是要初始化elementData和size，但是其中有一个注意点

public ArrayList(Collection<? extends E> c) {
  elementData = c.toArray();
  if ((size = elementData.length) != 0) {
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
      elementData = Arrays.copyOf(elementData, size, Object[].class);
  } else {
    // replace with empty array.
    this.elementData = EMPTY_ELEMENTDATA;
  }
}

可以看到在Collection.toArray()之后又判断了他的Class类型是不是Object[].class，这个也注释了是一个bug!

4.常用方法

由于ArrayList是基于数组的，所以他的api基本都是基于System.arraycopy()实现的；

public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

可以看到这是一个native方法，并且JVM有对这个方法做特殊的优化处理

1、void trimToSize()

public void trimToSize() {//节约内存
    modCount++;//此变量记录ArrayList被改变的次数  ！！！超级注意！！！
    int oldCapacity = elementData.length;
    if (size < oldCapacity) {//!!size往往不等于elementData.length;elementData.length是数组的初始长度，size是实际内容的长度！！
            elementData = Arrays.copyOf(elementData, size);
    }
    }

modCount变量是记录ArrayList被改变的次数

ArrayList不是线程安全（异步）的

ArrayList不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。

这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对ArrayList 结构的修改（长度的变化，增加，删除；赋值不是结构变化）都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了ArrayList。
ArrayList中的mouCount是在他的父类Abstract中申明的。

protected transient int modCount = 0;

2、void ensureCapacity(int minCapacity)

public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;//若传入参数大于原容量，先扩为  1.5*原容量+1
            if (newCapacity < minCapacity)
        newCapacity = minCapacity;//若扩为 1.5*原容量+1 后还是小于传入的参数，则把传入的参数作为新容量
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
    }
    }

ArrayList需要扩容时至少都是扩为 1.5*原容量+1 ，若1.5*原容量+1 还是小于传入的参数，才把传入的参数作为新容量。

3、boolean contains(Object o)

public boolean contains(Object o) {
    return indexOf(o) >= 0;
    }

4、int indexOf(Object o)

public int indexOf(Object o) {
    if (o == null) {//定位是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;
    }

5、Object[] toArray() / T[] toArray(T[] a)

调用的是Arrays.copyOf(）

public Object[] toArray() {

        return Arrays.copyOf(elementData, size);
    }

 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());//若传入的数组长度小于size（ArrayList实际长度）,则返回一个长度为size新的数组
    System.arraycopy(elementData, 0, a, 0, size);//若传入数组长度相等，则把elementData复制进传入数组
        if (a.length > size)//若传入的a的长度大于原本数组，则后面补null
            a[size] = null;
        return a;
    }

6、E set(int index, E element)

set是直接替换掉该位置元素；而add是插入该位置，其余元素后移。

public E set(int index, E element) {
    RangeCheck(index);//参数检查的方法~~一定要时刻注意参数检查哦~~
    E oldValue = (E) elementData[index];
    elementData[index] = element;
    return oldValue;

    }

7、boolean add(E e) / void add(int index, E element)

public boolean add(E e) {
    ensureCapacity(size + 1);  // add()时先扩容！
    elementData[size++] = e;//!!写的很好，size++的同时还完成了在最后位置的赋值。之所以size++不会报边界溢出的错误是因为上面已经扩容了。
    return true;
    }

 public void add(int index, E element) {
    if (index > size || index < 0)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
    ensureCapacity(size+1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,size - index);//!!把elementData的数据从index->末尾全部复制到从index+1开始，复制长度无size-index
    elementData[index] = element;//相当于把传入的element插入到空出的位置，即原index
    size++;
    }

8、E remove(int index) / boolean remove(Object o) / void fastRemove(int index)

public E remove(int index) {
    RangeCheck(index);
    modCount++;
    E oldValue = (E) elementData[index];//得到需要返回的被remove掉的元素
    int numMoved = size - index - 1;//复制时复制的长度，
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,numMoved);//把原数组从index+1-->末尾的数据复制到 index的位置，即相当于把原本index上的数据覆盖掉了，这样最后就空出了一个位置。
elementData<span class="token punctuation">[</span><span class="token operator">--</span>size<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span> <span class="token comment">// 先把size减一，在把最后一赋值为null</span>
<span class="token keyword">return</span> oldValue<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
public boolean remove(Object o) {
    if (o == 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 void fastRemove(int index) {//快速移除！ 此方法跳过了边界检查这一步，且不会返回被移除的元素。平时还是不要用哦~~
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        elementData[–size] = null; // Let gc do its work
    }

:hexoPostRenderEscape–>

5.迭代方式

1. 随机访问
由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。
```
for (int i=0, len = list.size(); i < len; i++) {
  String s = list.get(i);
}
```

2. 迭代器遍历

这其实就是迭代器模式

Iterator iter = list.iterator();
while (iter.hasNext()) {
  String s = (String)iter.next();
}

3. 增强for循环遍历
这其实是一个语法糖
```
for (String s : list) {
  ...
}
```

4.增强for循环遍历的实现

public void test_List() {
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
for (String s : list) {
  System.out.println(s);
}
}

6.fail-fast机制

fail-fast是说当并发的对容器内容进行操作时，快速的抛出ConcurrentModificationException；但是这种快速失败操作无法得到保证，它不能保证一定会出现该错误，但是快速失败操作会尽最大努力抛出ConcurrentModificationException异常。所以我们程序的正确性不能完全依赖这个异常，只应用于bug检测。

protected transient int modCount = 0;
private void checkForComodification() {
  if (ArrayList.this.modCount != this.modCount)
    throw new ConcurrentModificationException();
}

在ArrayList的Iterator和SubList中，每当进行内存操作时，都会先使用checkForComodification来检测内容是否已修改。

7.总结

a.ArrayList动态数组！

b.ArrayList 非线程安全，即是异步的。单线程才用ArrayList。

c.ArrayList整体来看就是一个更加安全和方便的数组，但是他的插入和删除操作也实在是蛋疼，对于这一点其实可以通过树或者跳表来解决

邓滔

http://dtbox.com/2019/07/18/jdk-yuan-ma-fen-xi-2-arraylist/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源邓滔 !

JDK源码分析 ArrayList

jdk源码分析(3)-LinkedList

2019-07-18 JDK源码分析

JDK源码分析 LinkedList

jdk源码分析(1)-String

2019-07-17 JDK源码分析

JDK源码分析 string

jdk源码分析(2)-ArrayList

jdk源码分析(2)-ArrayList

1.ArrayList简介

2.ArrayList成员变量

3.ArrayList构造函数

4.常用方法

1、void trimToSize()

2、void ensureCapacity(int minCapacity)

3、boolean contains(Object o)

4、int indexOf(Object o)

5、Object[] toArray() / T[] toArray(T[] a)

6、E set(int index, E element)

7、boolean add(E e) / void add(int index, E element)

8、E remove(int index) / boolean remove(Object o) / void fastRemove(int index)

5.迭代方式

1. 随机访问

2. 迭代器遍历

3. 增强for循环遍历

4.增强for循环遍历的实现

6.fail-fast机制

7.总结

你的赏识是我前进的动力