Java集合框架ArrayList源码分析(一)

网友投稿 207 2023-07-09


Java集合框架ArrayList源码分析(一)

ArrayList底层维护的是一个动态数组,每个ArrayList实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素,其容量也自动增长。

ArrayList不是同步的(也就是说不是线程安全的),如果多个线程同时访问一个ArrayList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步,在多线程环境下,可以使用Collections.synchronizedList方法声明一个线程安全的ArrayList,例如:

List arraylist = Collections.synchronizedList(new ArrayList());

下面通过ArrayList的源码来分析其原理。

1、ArrayList的构造方法:ArrayList提供了三种不同的构造方法

1) ArrayList(),构造一个初始容量为 10 的空列表。

2) ArrayList(int initialCapacity),构造一个具有指定初始容量的空列表。

3) ArrayList(Collection extends E> c),构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。

源码如下:

private transient Object[] elementData;

public ArrayList(int initialCapacity) {

super();

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);

this.elementData = new Object[initialCapacity]; //生成一个长度为10的Object类型的数组

}

public ArrayList() {

this(10); //调用ArrayList(int i)

}

public ArrayList(Collection extends E> c) {

elementData = c.toArray(); //返回包含此 collection 中所有元素的数组

size = elementData.length;

// c.toArray might (incorrectly) not return Object[] (see 6260652)

if (elementData.getClass() != Object[].class)

elementData = Arrays.copyOf(elementData, size, Object[].class); //复制指定的数组,返回包含相同元素和长度的Object类型的数组

}

当采用不带参数的构造方法ArrayList()生成一个集合对象时,其实是在底层调用ArrayList(int initialCapacity)这一构造方法生产一个长度为10的Object类型的数组。当采用带有集合类型参数的构造方法时,在底层生成一个包含相同的元素和长度的Object类型的数组。

2、add方法:ArrayList提供了两种添加元素的add方法

1) add(E e),将指定的元素添加到此列表的尾部。

2) add(int index, E e),将指定的元素插入此列表中的指定位置。向右移动当前位于该位置的元素(如果有)以及所有后续元素(将其索引加 1)private int size;

public boolean add(E e) {

ensureCapacity(size + 1); // 扩大数组容量

elementData[size++] = e; //将元素e添加到下标为size的Object数组中,并且执行size++

return true;

}

public void add(int index, E element) {

if (index > size || index < 0) //如果指定要插入的数组下标超过数组容量或者指定的下标小于0,抛异常

throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

ensureCapacity(size+1); // 扩大数组容量

SywuqeBHstem.arraycopy(elementData, index, elementData, index + 1,size - index); //从指定源数组中复制一个数组,复制从指定的位置开始,到目标数组的指定位置结束。
// elementData --- 源数组 index --- 源数组中的起始位置
// elementData --- 目标数组 index+1 --- 目标数组中的起始位置
// size - index --- 要复制的数组元素的数量

elementData[index] = element; //将要添加的元素放到指定的数组下标处

size++;

}

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;

// minCapacity is usually close to size, so this is a win:

elementData = Arrays.copyOf(elementData, newCapacity); //复制指定的数组,返回新数组的容量为newCapacity

}

}

如果集合中添加的元素超过了10个,那么ArrayList底层会新生成一个数组,长度为原数组的1.5倍+1,并将原数组中的元素copy到新数组中,并且后续添加的元素都会放在新数组中,当新数组的长度无法容纳新添加的元素时,重复该过程。这就是集合添加元素的实现原理。

3wuqeBH、get方法:

 1) get(int index),返回此列表中指定位置上的元素。

public E get(int index) {

RangeCheck(index); //检查传入的指定下标是否合法

return (E) elementData[index]; //返回数组下标为index的数组元素

}

private void RangeCheck(int index) {

if (index >= size) //如果传入的下标大于或等于集合的容量,抛异常

throw new IndexOutOfBoundsException(

"Index: "+index+", Size: "+size);

}

4、remove方法:

1) E remove(int index),移除此列表中指定位置上的元素。向左移动所有后续元素(将其索引减 1)。

2) boolean remove(Object o),移除此列表中首次出现的指定元素(如果存在)。如果列表不包含此元素,则列表不做改动,返回boolean值。

public E remove(int index) {

RangeCheck(index); //检查指定的下标是否合法

modCount++;

E oldValue = (E) elhttp://ementData[index]; //获取指定下标的数组元素

int numMoved = size - index - 1; //要移动的元素个数

if (numMoved > 0)

System.arraycopy(elementData, index+1, elementData, index, numMoved); //移动数组元素

elementData[--size] = null; // Let gc do its work

return oldValue;

}

public boolean remove(Object o) {

if (o == null) { //如果传入的参数为null

for (int index = 0; index < size; index++)

if (elementData[index] == null) { //移除首次出现的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) { //移除指定位置的元素,实现方法类似remove(int i)

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

}

5、clone方法:

1) Object clone(),返回此ArrayList实例的浅表副本(不复制这些元素本身) 。

public Object clone() {

try {

ArrayList v = (ArrayList) super.clone(); //调用Object类的clone方法返回一个ArrayList对象

v.elementData = Arrays.copyOf(elementData, size); //复制目标数组

v.modCount = 0;

return v;

} catch (CloneNotSupportedException e) {

// this shouldn't happen, since we are Cloneable

throw new InternalError();

}

}

以上通过对ArrayList部分关键源码的分析,知道了ArrayList底层的实现原理,关于ArrayList源码有以下几点几点总结:

 1) ArrayList 底层是基于数组来实现的,可以通过下标准确的找到目标元素,因此查找的效率高;但是添加或删除元素会涉及到大量元素的位置移动,效率低。

 2) ArrayList提供了三种不同的构造方法,无参数的构造方法默认在底层生成一个长度为10的Object类型的数组,当集合中添加的元素个数大于10,数组会自动进行扩容,即生成一个新的数组,并将原数组的元素放到新数组中。

3) ensureCapacity方法对数组进行扩容,它会生成一个新数组,长度是原数组的1.5倍+1,随着向ArrayList中不断添加元素,当数组长度无法满足需要时,重复该过程。


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:java selenium Selenium IDE介绍及用法
下一篇:java使用hashMap缓存保存数据的方法
相关文章

 发表评论

暂时没有评论,来抢沙发吧~