黑马程序员技术交流社区
标题:
ArrayList是如何实现长度可变的?
[打印本页]
作者:
laoyang
时间:
2011-11-8 11:26
标题:
ArrayList是如何实现长度可变的?
本帖最后由 laoyang 于 2011-11-21 10:49 编辑
ArrayList用起来很方便,但是它的实现原理是怎么样的呢?ArrayList是如何实现长度可变的?
作者:
绿影
时间:
2011-11-8 11:40
ArryList和Vector可变长度数组的原理:
当默认10的长度的数组不够存储时,会建立一个新数组。将原来数组的内容拷贝到新的数组当中,并将新增加的元素追加到拷贝完的数组尾,如果仍然不够重复上述动作。其中,ArryList的增加是以原来50%长度进行增加,而Vector是按照100%延长。这里在添一点就是:ArryList是线程不安全的,Vector是安全的。由于是否有锁的判断将影响效率。故Arrylist效率远远高于Vector。而且只要是常用的容器就不是同步的,因为同步效率比较低。
注意:
作者:
柴永菲
时间:
2011-11-8 11:44
ArrayList的实现:
对于ArrayList而言,它实现List接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。
1) 底层使用数组实现:
private transient Object[] elementData;
2) 构造方法:
ArrayList提供了三种方式的构造器,可以构造一个默认初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定
collection的元素的列表,这些元素按照该collection的迭代器返回它们的顺序排列的。
3) 存储:
ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll
(int index, Collection<? extends E> c)这些添加元素的方法
4) 读取:
返回此列表中指定位置上的元素。
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
5) 删除:
ArrayList提供了根据下标或者指定对象两种方式的删除功能
注意:从数组中移除元素的操作,也会导致被移除的元素以后的所有元素的向左移动一个位置
6) 调整数组容量:
从上面介绍的向ArrayList中存储元素的代码中,我们看到,每当向数组中添加元素时,都要去检查添加后元素的个数是否会超出当前数组
的长度,如果超 出,数组将会进行扩容,以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。
在实际添加大量元素前,我也可以使用ensureCapacity来手动增加ArrayList实例的容量,以减少递增 式再分配的数量。
数组进行扩容时,会将老数组中的元素重新拷贝一份到新的数组中,每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很 高的
,因此在实际使用时,我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时,要在构造ArrayList实例时,就指定其容量,
以避免 数组扩容的发生。或者根据实际需求,通过调用ensureCapacity方法来手动增加ArrayList实例的容量。
ArrayList还给我们提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize方法来实现
ArrayList提供了四种add()方法,
publicbooleanadd(Objecto)
publicvoidadd(intindex,Objectelement)
publicbooleanaddAll(Collectionc)
publicbooleanaddAll(intindex,Collectionc)
在每一种add()方法中,都首先调用了一个ensureCapacity(intminiCapacity)方法,这个方法保证elementData数组的长度不小于miniCapacity。ArrayList的自动变长机制就是在这个方法中实现的。
希望能帮到你
作者:
张奇云
时间:
2011-11-8 11:44
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
复制代码
这个方法的作用就是用来判断当前的数组是否需要扩容,应该扩容多少。其中属性:modCount是继承自父类,它表示当前的对象对elementData数组进行了多少次扩容,清空,移除等操作。该属性相当于是一个对于当前List 对象的一个操作记录日志号。 我们主要看下面的代码实现:
1. 首先得到当前elementData 属性的长度oldCapacity。
2. 然后通过判断oldCapacity和minCapacity参数谁大来决定是否需要扩容
如果minCapacity大于oldCapacity,那么我们就对当前的List对象进行扩容。扩容的的策略为:取(oldCapacity * 3)/2 + 1和minCapacity之间更大的那个。然后使用数组拷 贝的方法,把以前存放的数据转移到新的数组对象中
如果minCapacity不大于oldCapacity那么就不进行扩容。
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2