`
andymu1117
  • 浏览: 37936 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

(转)ArrayList实现

    博客分类:
  • java
 
阅读更多

ArrayList是List接口的一个可变长数组实现。实现了所有List接口的操作,并允许存储null值。除了没有进行同步,ArrayList基本等同于Vector。在Vector中几乎对所有的方法都进行了同步,但ArrayList仅对writeObject和 readObject进行了同步,其它比如add(Object)、remove(int)等都没有同步。

1.存储
ArrayList使用一个Object的数组存储元素。
private transient Object elementData[];
ArrayList实现了java.io.Serializable接口,这儿的transient标示这个属性不需要自动序列化。下面会在writeObject()方法中详细讲解为什么要这样作。

2.add和remove

Java代码 复制代码
  1. public boolean add(Object o) {   
  2. ensureCapacity(size + 1); // Increments modCount!!   
  3. elementData[size++] = o;   
  4. return true;   
  5. }   
public boolean add(Object o) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = o;
return true;
} 
 



注意这儿的ensureCapacity()方法,它的作用是保证elementData数组的长度可以容纳一个新元素。在“自动变长机制”中将详细讲解。

Java代码 复制代码
  1. public Object remove(int index) {   
  2. RangeCheck(index);   
  3. modCount++;   
  4. Object oldValue = elementData[index];   
  5. int numMoved = size - index - 1;   
  6. if (numMoved > 0)   
  7. System.arraycopy(elementData, index+1, elementData, index,   
  8. numMoved);   
  9. elementData[--size] = null// Let gc do its work   
  10. return oldValue;   
  11. }   
public Object remove(int index) {
RangeCheck(index);
modCount++;
Object oldValue = elementData[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;
} 
 



RangeCheck()的作用是进行边界检查。由于ArrayList采用一个对象数组存储元素,所以在删除一个元素时需要把后面的元素前移。删除一个元素时只是把该元素在elementData数组中的引用置为null,具体的对象的销毁由垃圾收集器负责。
modCount的作用将在下面的“iterator()中的同步”中说明。
注:在前移时使用了System提供的一个实用方法:arraycopy(),在本例中可以看出System.arraycopy()方法可以对同一个数组进行操作,这个方法是一个native方法,如果对同一个数组进行操作时,会首先把从源部分拷贝到一个临时数组,在把临时数组的元素拷贝到目标位置。

3.自动变长机制

在实例化一个ArrayList时,你可以指定一个初始容量。这个容量就是elementData数组的初始长度。如果你使用:

ArrayList list = new ArrayList();

则使用缺省的容量:10。

public ArrayList() {
this(10);
}

ArrayList提供了四种add()方法,

Java代码 复制代码
  1. public boolean add(Object o)   
  2.   
  3. public void add(int index, Object element)   
  4.   
  5. public boolean addAll(Collection c)   
  6.   
  7. public boolean addAll(int index, Collection c)   
public boolean add(Object o)

public void add(int index, Object element)

public boolean addAll(Collection c)

public boolean addAll(int index, Collection c) 
 



在每一种add()方法中,都首先调用了一个ensureCapacity(int miniCapacity)方法,这个方法保证elementData数组的长度不小于miniCapacity。ArrayList的自动变长机制就是在这个方法中实现的。

Java代码 复制代码
  1. public void ensureCapacity(int minCapacity) {   
  2. modCount++;   
  3. int oldCapacity = elementData.length;   
  4. if (minCapacity > oldCapacity) {   
  5. Object oldData[] = elementData;   
  6. int newCapacity = (oldCapacity * 3)/2 + 1;   
  7. if (newCapacity < minCapacity)   
  8. newCapacity = minCapacity;   
  9. elementData = new Object[newCapacity];   
  10. System.arraycopy(oldData, 0, elementData, 0, size);   
  11. }   
  12. }   
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;
elementData = new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);
}
} 
 



从这个方法实现中可以看出ArrayList每次扩容,都扩大到原来大小的1.5倍。
每种add()方法的实现都大同小异,下面给出add(Object)方法的实现:

Java代码 复制代码
  1. public boolean add(Object o) {   
  2. ensureCapacity(size + 1); // Increments modCount!!   
  3. elementData[size++] = o;   
  4. return true;   
  5. }  
public boolean add(Object o) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = o;
return true;
}
 



4.iterator()中的同步
在父类AbstractList中定义了一个int型的属性:modCount,记录了ArrayList结构性变化的次数。

protected transient int modCount = 0;

在ArrayList的所有涉及结构变化的方法中都增加modCount的值,包括:add()、remove()、addAll()、removeRange()及clear()方法。这些方法每调用一次,modCount的值就加1。
注:add()及addAll()方法的modCount的值是在其中调用的ensureCapacity()方法中增加的。

AbstractList中的iterator()方法(ArrayList直接继承了这个方法)使用了一个私有内部成员类Itr,生成一个Itr对象(Iterator接口)返回:

public Iterator iterator() {
return new Itr();
}

Itr实现了Iterator()接口,其中也定义了一个int型的属性:expectedModCount,这个属性在Itr类初始化时被赋予ArrayList对象的modCount属性的值。

int expectedModCount = modCount;

注:内部成员类Itr也是ArrayList类的一个成员,它可以访问所有的AbstractList的属性和方法。理解了这一点,Itr类的实现就容易理解了。

在Itr.hasNext()方法中:

public boolean hasNext() {
return cursor != size();
}

调用了AbstractList的size()方法,比较当前光标位置是否越界。

在Itr.next()方法中,Itr也调用了定义在AbstractList中的get(int)方法,返回当前光标处的元素:

Java代码 复制代码
  1. public Object next() {   
  2. try {   
  3. Object next = get(cursor);   
  4. checkForComodification();   
  5. lastRet = cursor++;   
  6. return next;   
  7. catch(IndexOutOfBoundsException e) {   
  8. checkForComodification();   
  9. throw new NoSuchElementException();   
  10. }   
  11. }   
public Object next() {
try {
Object next = get(cursor);
checkForComodification();
lastRet = cursor++;
return next;
} catch(IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
} 
 


注意,在next()方法中调用了checkForComodification()方法,进行对修改的同步检查:

Java代码 复制代码
  1. final void checkForComodification() {   
  2. if (modCount != expectedModCount)   
  3. throw new ConcurrentModificationException();   
  4. }  
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
 


现在对modCount和expectedModCount的作用应该非常清楚了。在对一个集合对象进行跌代操作的同时,并不限制对集合对象的元素进行操作,这些操作包括一些可能引起跌代错误的add()或remove()等危险操作。在AbstractList中,使用了一个简单的机制来规避这些风险。这就是modCount和expectedModCount的作用所在。

5.序列化支持
ArrayList实现了java.io.Serializable接口,所以ArrayList对象可以序列化到持久存储介质中。ArrayList的主要属性定义如下:

private static final long serialVersionUID = 8683452581122892189L;

private transient Object elementData[];

private int size;

可以看出serialVersionUID和size都将自动序列化到介质中,但elementData数组对象却定义为transient了。也就是说 ArrayList中的所有这些元素都不会自动系列化到介质中。为什么要这样实现?因为elementData数组中存储的“元素”其实仅是对这些元素的一个引用,并不是真正的对象,序列化一个对象的引用是毫无意义的,因为序列化是为了反序列化,当你反序列化时,这些对象的引用已经不可能指向原来的对象了。所以在这儿需要手工的对ArrayList的元素进行序列化操作。这就是writeObject()的作用。

Java代码 复制代码
  1. private synchronized void writeObject(java.io.ObjectOutputStream s)   
  2. throws java.io.IOException{   
  3. // Write out element count, and any hidden stuff   
  4. s.defaultWriteObject();   
  5. // Write out array length   
  6. s.writeInt(elementData.length);   
  7. // Write out all elements in the proper order.   
  8. for (int i=0; i<size; i++)   
  9. s.writeObject(elementData[i]);   
  10. }   
private synchronized void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
s.defaultWriteObject();
// Write out array length
s.writeInt(elementData.length);
// Write out all elements in the proper order.
for (int i=0; i<size; i++)
s.writeObject(elementData[i]);
} 
 



这样元素数组elementData中的所以元素对象就可以正确地序列化到存储介质了。
对应的readObject()也按照writeObject()方法的顺序从输入流中读取:

Java代码 复制代码
  1. private synchronized void readObject(java.io.ObjectInputStream s)   
  2. throws java.io.IOException, ClassNotFoundException {   
  3. // Read in size, and any hidden stuff   
  4. s.defaultReadObject();   
  5. // Read in array length and allocate array   
  6. int arrayLength = s.readInt();   
  7. elementData = new Object[arrayLength];   
  8. // Read in all elements in the proper order.   
  9. for (int i=0; i<size; i++)   
  10. elementData[i] = s.readObject();   
  11. }   
private synchronized void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in array length and allocate array
int arrayLength = s.readInt();
elementData = new Object[arrayLength];
// Read in all elements in the proper order.
for (int i=0; i<size; i++)
elementData[i] = s.readObject();
} 
 
分享到:
评论

相关推荐

    ArrayList的一个C++类模板实现

    在这个ArrayList实现中,第一层散列可能是用来快速定位元素的位置,而第二层散列可能是为了处理散列冲突,确保每个元素都有一个唯一的索引。这种双层散列结构可以显著减少查找和插入的时间复杂度,使其接近O(1)。 ...

    深入Java集合学习系列:ArrayList的实现原理

    《深入Java集合学习系列:ArrayList的实现原理》 在Java编程中,ArrayList是集合框架中一个重要的类,属于List接口的实现,它提供了动态数组的功能,允许我们在集合中存储、添加、删除元素,并且可以按索引访问。这...

    jni操作arraylist对象

    ArrayList是Java集合框架中的一个重要类,它实现了List接口,用于存储可变大小的有序对象列表。ArrayList通过数组来存储元素,因此可以快速访问任意位置的元素,但插入和删除元素时可能需要移动其他元素,这可能导致...

    arraylist用法

    在.NET Framework中,`ArrayList`实现了`ICollection`和`IList`接口,这意味着它支持列表的基本功能,如添加、删除元素等。 #### 二、如何使用ArrayList? 创建一个`ArrayList`实例非常简单: ```csharp ...

    arraylist的C#基本实现

    在本项目中,我们将深入探讨ArrayList的基本实现和在Visual Studio环境下的使用方法。 ArrayList的基础概念: 1. 动态数组:ArrayList实际上是一个可以自动调整大小的动态数组,可以根据需要自动扩展或收缩容量。 2...

    ArrayList类操作程序实例

    ArrayList是一个基于数组实现的动态列表,可以存储任何类型的数据,并且支持动态扩容。在本实例中,我们将深入探讨ArrayList的常用操作、特性和注意事项。 一、ArrayList的构造方法 ArrayList提供了几种构造方法,...

    你必须知道的C# ArrayList

    - ArrayList是一个基于数组实现的动态列表,它允许存储任意类型的对象,这得益于C#的类型擦除特性。 - ArrayList内部维护了一个Object类型的数组,当添加或删除元素时,它会自动调整数组大小以适应变化。 2. **...

    java ArrayList的使用与分析

    - **实现接口**:ArrayList 实现了 `java.util.List`、`java.util.RandomAccess` 和 `java.util.Iterator` 等接口,提供了丰富的操作方法。 - **性能考虑**:ArrayList 的操作速度通常比 LinkedList 快,因为它是...

    Java ArrayList 实现实例讲解

    ArrayList是Java集合框架中的一员,它是一个基于数组实现的动态列表。ArrayList的主要特点是其容量能够自动增长,以适应添加更多的元素。在Java中,ArrayList类位于`java.util`包下,它实现了`List`接口,同时也实现...

    ArrayList深度剖析与简单实用

    ArrayList是Java中一种常见的动态数组实现,它是List接口的一个实现类,主要特点是可以在运行时自动调整其容量以适应元素数量的变化。ArrayList的核心概念基于数组,但比数组更加灵活,因为它支持动态增长和缩小,...

    使用数组列表ArrayList填充ListBox

    - 如果ArrayList包含复杂对象,考虑使用ObjectDataSource和DataBinding,这有助于实现数据层和UI层的解耦。 6. 事件处理: - 可以监听ListBox的SelectedIndexChanged事件,以便在用户选择新项时执行相应操作。 -...

    ArrayList源码分析(含jdk1.8).pdf

    在了解ArrayList的源码分析时,我们主要探讨其在Java Development Kit (JDK) 1.8中的实现。ArrayList是一个非常重要的集合框架,用于动态数组的实现,其功能类似于数组,但可以在运行时动态调整大小。它是一个非线程...

    ArrayList和Linkedlist1

    在IT领域,特别是Java编程中,ArrayList和LinkedList是两种非常重要的数据结构,它们都是List接口的实现类。理解这两者的区别对于优化程序性能至关重要。面试官询问这些知识点,旨在评估应聘者的理论基础和实践能力...

    ArrayList演示

    ArrayList类实现了List接口,提供了可变大小的数组,允许我们在列表的任何位置进行添加、删除和修改元素的操作。这篇ArrayList演示将通过一系列实例帮助我们深入理解ArrayList的用法。 首先,ArrayList的基本操作...

    ArrayList,HashMap

    ArrayList属于List接口的实现,而HashMap则实现了Map接口。两者在用途、性能和特性上都有所不同。 ArrayList是一个动态数组,它允许我们在集合中按索引顺序访问元素。它通过内部维护一个数组来存储元素,当添加...

    Java中ArrayList的removeAll方法详解

    ArrayList的removeAll方法的实现机制是通过循环遍历ArrayList中的每个元素,然后使用contains方法判断该元素是否在另外一个集合中,如果在,则删除该元素。这种实现机制的问题是,它需要两层循环,时间复杂度为O(m*n...

    C#ArrayList用法

    相比于普通的数组,`ArrayList`提供了更加灵活的功能,比如动态地增加和减少元素,以及实现`ICollection`和`IList`接口的能力。这使得`ArrayList`成为一种在不知道数组大小的情况下处理数据的有效方式。 #### 二、...

    有关于C#的程序(ArrayList类,动态添加,删除的)

    在提供的资源中,"ClassLibrary1"可能是一个包含ArrayList实现的类库项目,"list01.sln"是解决方案文件,用于打开和管理项目,"list01"可能是项目的源代码文件夹,而"list01.suo"是Visual Studio的用户选项文件,...

    ArrayList测试.

    ArrayList是.NET框架中System.Collections命名空间下的一个类,它是基于数组实现的动态列表。ArrayList提供了在集合中添加、删除、查找和访问元素的功能,适用于存储各种类型的数据。在这个ArrayList测试中,我们将...

Global site tag (gtag.js) - Google Analytics