首页 > 代码库 > 深入java集合学习2-ArrayList的实现原理

深入java集合学习2-ArrayList的实现原理

2024-07-03 16:32:05   227人阅读

ArrayList概述

类概述

          ArrayList是List 接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。

每个 ArrayList 实例都有一个容量(capacity)。该容量是指用来存储列表元素的数组的大小。它大于或等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。在添加大量元素前，应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。注意，此实现不是同步的。

类结构


ArrayList实现

          通过查看ArrayList的源码我们可以得知,ArrayList底层是通过操作数组来实现,其实就是用java实现了数据结构中的顺序表。

底层采用数组实现

?
1
private transient Object[] elementData;
          看到这行代码，或许有很多同学和我刚开始一样。为什么ArrayList源代码中要将elementData定义为transient变量呢？这个问题的研究大家可以看这篇文章【http://kakaluyi.iteye.com/blog/870137】.如果对java中的序列化知识不懂的可以看本博客中的关于序列化的文章。【理解Java对象序列化】     【java中可定制的序列化过程 writeObject与readObject】      【Java中的序列化Serialable高级详解【转载】】          

可变数组

            在java中我们知道，当一个数组的长度被定义好之后，数组的长度是不可变的。那么可变数组时怎么一回事呢？其实可变数组只是表现形式上的可变。
例如
      
?
1
int array1[]={1,2,3};//定义一个数组长度为3的整形数组,此时数组的三个元素分别为1,2,3
此时如果想添加一个元素"4"到数组中去,因为数组长度是不可变的，无法直接array[3]=4;那么此时只能借助另外一个长度为4的数组array2,将数组array1的元素拷贝到新数组array2中，再赋值array[3]=4;然后将array1的引用指向array2。此时array1的表现形式就像是可变数组了.
?
1
2
3
4
5
6
7
int  array1[]={1,2,3};
int array2[]=new int[4];
for(int i=0;i<array1.length;i++){
array2[i]=array1[i];
}
array2[3]=4;
array1=array2;
此时我们就可以想到，要想动态的实现ArrayList的可变数组，那么在ArrayList初始化的时候我们要初始化一个容量，往ArrayList中添加元素时我们要动态的改变底层数组的长度。那我们来看看jdk源码是怎么初始化和动态改变数组容量的

初始化

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        this.elementData = http://www.mamicode.com/new Object[initialCapacity];
    }
 
    public ArrayList() {
        this(10);
    }
 
    public ArrayList(Collection<? extends E> c) {
        elementData = http://www.mamicode.com/c.toArray();
        size = elementData.length;
        if (elementData.getClass() != Object[].class)
            elementData = http://www.mamicode.com/Arrays.copyOf(elementData, size, Object[].class);
    }

从源码中我们可以得知ArrayList提供了三种方式的构造器
           1 构造一个默认初始容量为10的空列表
           2 构造一个指定初始容量的空列表
           3 构造一个包含指定collection中元素的列表

动态调整底层数组的容量

?
1
2
3
4
5
6
7
8
9
10
11
public void ensureCapacity(int minCapacity) {
        modCount++;//Fast-Fail机制(具体机制本文章中专门有说的)
        int oldCapacity = elementData.length;
        if (minCapacity > oldCapacity) {
            Object oldData[] = elementData;
            int newCapacity = (oldCapacity * 3) / 2 + 1;
            if (newCapacity < minCapacity)
                newCapacity = minCapacity;
            elementData = http://www.mamicode.com/Arrays.copyOf(elementData, newCapacity);
        }
    }
从源码中我们可知动态调整容量的过程是
          1 获取当前数组的大小(旧容量)
          2 如果当前要保证的容量小于旧容量，那么容量不进行扩充，反之就扩充。
          3 如果要扩充容量，那么新容量为 旧容量的1.5倍+1
             3.1  取计算出来的新容量和需要的容量中的最大值，最为最后底层数组的真实容量
             3.2  拷贝旧数组的数据到新数组中，让底层数组的引用指向新容量的数组
从上述分析可知如果可预知数据量的多少，可在构造ArrayList时指定其容量。在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。这样可以减少内存的占用和提高存储效率。

集合操作

ArrayList提供了add,set,get,delete等一系列操作。下面对ArrayList中实现这些操作一一讲解。

add添加元素

元素添加到列表的尾部

?
1
2
3
4
5
public boolean add(E e) {
        ensureCapacity(size + 1); //动态调整底层数组的容量
        elementData[size++] = e;//将元素添加到列表尾部,列表大小加1
        return true;//返回true,添加成功
    }

元素添加到指定位置



?
1
2
3
4
5
6
7
8
public void add(int index, E element) {
        if (index > size || index < 0)// 首先检查index是否合法,要保证不能大于列表的实际长度,且index不能为负数,如果不满足就抛出异常
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        ensureCapacity(size + 1);// 添加元素的操作都要动态的调整底层数组的容量
        System.arraycopy(elementData, index, elementData, index + 1, size - index);//调用System的数组拷贝方法
        elementData[index] = element;// 设置新数组处index处的值为指定的元素
        size++;// 列表长度加1
    }


集合中的元素添加到列表尾部

?
1
2
3
4
5
6
7
8
public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacity(size + numNew);
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

从指定位置开始添加集合中元素


?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean addAll(int index, Collection<? extends E> c) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
 
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacity(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;
    }

get获取元素

我们知道ArrayList底层是通过数组实现的,那么我们就可以通过数组的索引获取元素。代码如下
?
1
2
3
4
5
public E get(int index) {
        RangeCheck(index);// 检查index是否合法
 
        return (E) elementData[index];// 返回指定index处的元素
    }
ArrayList中有一私有方法，来检测index是否合法。
?
1
2
3
4
5
private void RangeCheck(int index) {
        //如果index不小于列表的元素个数,就抛出异常
        if (index >= size)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

remove删除元素

删除指定位置处的元素


?
1
2
3
4
5
6
7
8
9
10
11
12
13
public E remove(int index) {
        RangeCheck(index);// 检查index是否合法
 
        modCount++;// Fail-Fast机制
        E oldValue = http://www.mamicode.com/(E) elementData[index];// 获取待删除的元素
 
        int numMoved = size - index - 1;//移动元素个数
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);//向前移动元素
        }
        elementData[--size] = null;//将原来size-1处的元素设置为空,列表大小-1
        return oldValue;//返回删除的元素
    }

删除首次出现的指定元素

ArrayList允许重复元素的存在，此方法删除的是首次出现的指定元素，要想删除指定元素内部实现过程是：（1）循环遍历列表中找到指定元素首次出现的位置 （2）删除此位置的元素，那么这样就类似remove(int index)方法。jdk内部实现代码如下:
?
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
27
// 删除首次出现的指定元素，元素存在返回 true,元素不存在返回false
    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;
    }
 
    // ArrayList的私有方法,与remove(int index)方法类似
    private void fastRemove(int index) {
        modCount++;// Fail-Fast机制
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        elementData[--size] = null;
    }

删除指定位置区间内的元素


?
1
2
3
4
5
6
7
8
9
// 移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
        int newSize = size - (toIndex - fromIndex);
        while (size != newSize)
            elementData[--size] = null;
    }

为什么jdk源码中此方法是protected呢？具体的解释请参考

ArrayList removeRange方法分析这篇博文。





 


联系
我们