Java集合类源码之路(一)ArrayList

作者: 烤地瓜次不次 | 来源:发表于2019-03-13 16:17 被阅读0次

基础知识参考了一个大佬的博客。内容很全，很有层次。
https://www.cnblogs.com/skywang12345/p/3308498.html

这里我主要是就自己的源码学习过程做一个笔记及总结。
源码的学习和查看顺序打算按照 非线程安全的集合 > 多线程相关 > 线程安全的集合 这样的顺序学习。

ArrayList

笔记基于博客 https://www.cnblogs.com/skywang12345/p/3308556.html + 自己阅读 JDK1.8 源码整理。

1. 继承关系

// List代表这是一个序列
// 基类AbstractList实现了一些与数据结构无关的通用方法
// RandomAccess接口提供了可以通过下表访问元素的功能，可以对比LinkedList,并没有实现该接口
// Cloneable是拷贝接口
// Serializable是序列化接口，代表该类可以被序列化成文件存储或发送
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

2. 成员变量

// 默认初始化容量，该参数其实就是为了预估使用者需要的大小，以便减少重新分配size的次数
private static final int DEFAULT_CAPACITY = 10;

// static final的对象，当ArrayList的size为空时，实际的elementData都指向这里
private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 数据的实际存储方式是Object数组
transient Object[] elementData; // non-private to simplify nested class access

// 数据的实际大小
private int size;

3. 构造方法

ArrayList()

// 初始化一个默认长度为10的ArrayList
 public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ArrayList(int)

// 初始化一个特定容量的ArrayList，这个initialCapacity也只是建议长度，ArrayList的实际size不取决于这个值
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];// 以容量大小创建数组
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;// 默认为0长度的数组
    } else {// 小于0报错
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

ArrayList(Collection<? extends E>)

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {// 将c中的数据转为数组存入elementData
        // 这里注释说，c.toArray()方法不一定可以正确的返回Object数组
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {// 如果c的数据不存在,正常初始化
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

可以看到，除非指定了容量大小，elementData会变成长度为容量大小的数组，否则，elementData都会被赋值为0长度的数组。

4. ArrayList 的 add() 方法

4.1 add(E)

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 添加前先确认容量
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果是初始化并且没分配过容量，先确定容量大小，此步骤保证数组大小在执行过add后不小于10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 返回目前size+1
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 如果需要的容量 大于 现实容量 说明需要扩容
    // 此处可以看到如果Integer.Max再加1，无法满足条件，所以不执行扩容
    // 相应的elementData[size++]会报数组越界的错误
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
// 扩容操作 设置 新的容量=“(原始容量x3)/2 + 1”
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
// 如果需要的容量大于int类型的最大值，就只去int的最大值
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

4.2 add(int, E)

public void add(int index, E element) {
    rangeCheckForAdd(index);// index检查

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // native方法 index位置的数据全部需要向后移动一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

4.3 addAll(Collection<? extends E>)

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

4.4 addAll(int, Collection<? extends E>)

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

5. ArrayList 的 indexOf() 方法

通过索引遍历，使用equals来比较

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

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

5. ArrayList 的 get() 方法

public E get(int index) {
    rangeCheck(index);// index检查

    return elementData(index);
}

E elementData(int index) {
    // 直接通过数组索引取值
    return (E) elementData[index];
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

6. ArrayList 的 set() 方法

public E set(int index, E element) {
    rangeCheck(index);// index检查

    E oldValue = elementData(index);// 通过索引取值
    elementData[index] = element;
    return oldValue;
}

6. ArrayList 的 remove() 方法

// 通过索引移除元素
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;// index+1位置的元素全部需要前移一位
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}
// 直接移除元素
public boolean remove(Object o) {
    if (o == 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; // clear to let GC do its work
}

8. ArrayList 的遍历方式

通过迭代器遍历
通过索引遍历
通过foreach遍历

运行结果：

iteratorThroughRandomAccess：3 ms

iteratorThroughIterator：8 ms

iteratorThroughFor2：5 ms

由此可见，遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低！

9. ArrayList 的 trimToSize() 方法

// 将当前容量值设为 实际元素个数
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

10. SubList

SubList内置了ArrayList对象，计做parent，同时存有offset,index等索引。操作SubList的数据会改变原本ArrayList的数据！

Vector

LinkedList

Stack

HashTable

HashMap&HashSet

LinkedHashMap

TreeMap&TreeSet

ConcurrentHashMap

CopyOnWriteArrayList

WeakHashMap

网友评论

本文标题：Java集合类源码之路(一)ArrayList

本文链接：https://www.haomeiwen.com/subject/pqdtmqtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

Java集合类源码之路(一)ArrayList

ArrayList

1. 继承关系

2. 成员变量

3. 构造方法

4. ArrayList 的 add() 方法

4.1 add(E)

4.2 add(int, E)

4.3 addAll(Collection<? extends E>)

4.4 addAll(int, Collection<? extends E>)

5. ArrayList 的 indexOf() 方法

5. ArrayList 的 get() 方法

6. ArrayList 的 set() 方法

6. ArrayList 的 remove() 方法

8. ArrayList 的遍历方式

9. ArrayList 的 trimToSize() 方法

10. SubList

Vector

LinkedList

Stack

HashTable

HashMap&HashSet

LinkedHashMap

TreeMap&TreeSet

ConcurrentHashMap

CopyOnWriteArrayList

WeakHashMap

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Java集合类源码之路(一)ArrayList

ArrayList

1. 继承关系

2. 成员变量

3. 构造方法

4. ArrayList 的 add() 方法

4.1 add(E)

4.2 add(int, E)

4.3 addAll(Collection<? extends E>)

4.4 addAll(int, Collection<? extends E>)

5. ArrayList 的 indexOf() 方法

5. ArrayList 的 get() 方法

6. ArrayList 的 set() 方法

6. ArrayList 的 remove() 方法

8. ArrayList 的 遍历方式

9. ArrayList 的 trimToSize() 方法

10. SubList

Vector

LinkedList

Stack

HashTable

HashMap&HashSet

LinkedHashMap

TreeMap&TreeSet

ConcurrentHashMap

CopyOnWriteArrayList

WeakHashMap

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

8. ArrayList 的遍历方式