Javaコレクションシリーズ:ArrayListの詳細(ソース解析)と使用例
概要
前章では、Collectionのアーキテクチャについて学びました.この章では、Collectionの具体的な実装クラスについて説明します.まず,リストについて説明するが,リストではArrayListが最もよく用いられる.そこで、本章ではArrayListについて説明します.まずArrayListについて全体的な認識を持ってから、そのソースコードを学び、最後に例を通じてどのように使用するかを学びます.
第1部ArrayList紹介
ArrayListの概要
ArrayListは、動的配列に相当する配列キューです.Javaの配列に比べて容量が動的に増加します.AbstractListに継承され、List、RandomAccess、Cloneable、java.io.Serializableなどのインタフェースを実現します.
ArrayListはAbstractListを継承し,Listを実現した.これは配列キューであり、関連する追加、削除、変更、遍歴などの機能を提供します.ArrayListはRandmoAccessインタフェースを実現し,ランダムアクセス機能を提供する.RandmoAccessはjavaでListによって実装され、Listに高速アクセス機能を提供するために使用される.ArrayListでは、要素のシーケンス番号で要素オブジェクトをすばやく取得できます.これが高速ランダムアクセスです.後で、Listの「高速ランダムアクセス」と「Iterator反復器によるアクセス」の効率を比較します.
ArrayListはCloneableインタフェースを実現し,すなわち関数clone()を上書きし,クローン化できる.
ArrayListはjava.io.Serializableインタフェースを実現し、これはArrayListがシーケンス化をサポートし、シーケンス化によって伝送できることを意味する.
Vectorとは異なり、ArrayListでの操作はスレッドセキュリティではありません!したがって、ArrayListは単一スレッドで使用することを推奨し、マルチスレッドではVectorまたはCopyOnWriteArrayListを選択することができる.
ArrayListコンストラクタ
ArrayListのAPI
第2部ArrayListデータ構造
ArrayListの継承関係
ArrayListとCollectionの関係は下図の通りです.
ArrayListには、
(01)
(02)
第3部ArrayListソースコード解析(JDK 1.6.0_45ベース)
ArrayListの原理をより理解するために、以下にArrayListソースコードを分析する.ArrayListは配列により実現されており,ソースコードは比較的容易に理解できる.
まとめ:
(01)ArrayListは実際には1つの配列でデータを保存している.ArrayListを構築するとデフォルトコンストラクション関数を使用する場合、ArrayListのデフォルト容量サイズは10です.(02)ArrayListの容量が全ての要素を収容するのに足りない場合、ArrayListは容量を新たに設定する:「(元の容量x 3)/2+1」.(03)ArrayListのクローン関数,すなわち全要素を1つの配列にクローンする.(04)ArrayListがjava.io.Serializableを実現する方式.出力ストリームに書き込む場合は、「容量」を書き込み、「各要素」を順次書き込む.入力ストリームを読み出す場合は、「容量」を読み出し、「各要素」を順次読み出す.
第4部ArrayList遍歴方式
ArrayListは3種類の遍歴方式をサポート
(01)第1種は,反復器により遍歴する.つまり、Iteratorを通して巡ります.
(02)2つ目は,ランダムアクセス,インデックス値による遍歴である.ArrayListはRandomAccessインタフェースを実装しているため、インデックス値による要素へのランダムアクセスをサポートします.
(03)第3種,forサイクル遍歴.次のようになります.
次に、この3つの方法の効率を1つの例で比較し、インスタンスコード(ArrayListRandomAccessTest.java)は以下の通りである.
実行結果:
iteratorThroughRandomAccess:3 msiteratorThroughIterator:8 msiteratorThroughFor2:5 ms
このことから,ArrayListを巡る場合,ランダムアクセス(すなわちインデックスシーケンス番号でアクセス)が最も効率的であり,反復器での効率が最も低いことが分かる.
第5部toArray()異常
ArrayListの
ArrayListには2つのtoArray()関数があります.
toArray()関数を呼び出すと「java.lang.ClassCastException」異常が放出されますが、toArray(T[]contents)を呼び出すとT[]が正常に返されます.
toArray()が例外を放出するのは、toArray()がObject[]配列を返し、Object[]を他のタイプ(たとえば、Object[]をInteger[]に変換)に変換すると、Java.lang.ClassCastException例外が放出されます.Javaはダウンコンバートをサポートしていないためです.具体的には、前のArrayList.javaのソースコード紹介部のtoArray()を参照してください.この問題を解決する方法は、Object[]toArray()ではなく、T[]toArray(T[]contents)を呼び出すことです.
toArray(T[]contents)を呼び出してT[]を返すことは、以下のいくつかの方法で実現することができる.
第6部ArrayList例
ここでは、ArrayListTest.javaの例を用いて、ArrayListでよく使用されるAPIの使用方法について説明します.
実行結果:
the first element is: 5Arraylist size=: 4ArrayList contains 3 is: falsenext is: 5next is: 10next is: 2next is: 4str: 5str: 10str: 2str: 4ArrayList is empty: true
出典:http://www.cnblogs.com/skywang12345/p/3308513.html文章には不適切な点があります.指摘を歓迎します.あなたも私の微信の公衆番号:
前章では、Collectionのアーキテクチャについて学びました.この章では、Collectionの具体的な実装クラスについて説明します.まず,リストについて説明するが,リストではArrayListが最もよく用いられる.そこで、本章ではArrayListについて説明します.まずArrayListについて全体的な認識を持ってから、そのソースコードを学び、最後に例を通じてどのように使用するかを学びます.
第1部ArrayList紹介
ArrayListの概要
ArrayListは、動的配列に相当する配列キューです.Javaの配列に比べて容量が動的に増加します.AbstractListに継承され、List、RandomAccess、Cloneable、java.io.Serializableなどのインタフェースを実現します.
ArrayListはAbstractListを継承し,Listを実現した.これは配列キューであり、関連する追加、削除、変更、遍歴などの機能を提供します.ArrayListはRandmoAccessインタフェースを実現し,ランダムアクセス機能を提供する.RandmoAccessはjavaでListによって実装され、Listに高速アクセス機能を提供するために使用される.ArrayListでは、要素のシーケンス番号で要素オブジェクトをすばやく取得できます.これが高速ランダムアクセスです.後で、Listの「高速ランダムアクセス」と「Iterator反復器によるアクセス」の効率を比較します.
ArrayListはCloneableインタフェースを実現し,すなわち関数clone()を上書きし,クローン化できる.
ArrayListはjava.io.Serializableインタフェースを実現し、これはArrayListがシーケンス化をサポートし、シーケンス化によって伝送できることを意味する.
Vectorとは異なり、ArrayListでの操作はスレッドセキュリティではありません!したがって、ArrayListは単一スレッドで使用することを推奨し、マルチスレッドではVectorまたはCopyOnWriteArrayListを選択することができる.
ArrayListコンストラクタ
//
ArrayList()
// capacity ArrayList 。 , 。
ArrayList(int capacity)
// collection ArrayList
ArrayList(Collection extends E> collection)
ArrayListのAPI
// Collection API
boolean add(E object)
boolean addAll(Collection extends E> collection)
void clear()
boolean contains(Object object)
boolean containsAll(Collection> collection)
boolean equals(Object object)
int hashCode()
boolean isEmpty()
Iterator iterator()
boolean remove(Object object)
boolean removeAll(Collection> collection)
boolean retainAll(Collection> collection)
int size()
T[] toArray(T[] array)
Object[] toArray()
// AbstractCollection API
void add(int location, E object)
boolean addAll(int location, Collection extends E> collection)
E get(int location)
int indexOf(Object object)
int lastIndexOf(Object object)
ListIterator listIterator(int location)
ListIterator listIterator()
E remove(int location)
E set(int location, E object)
List subList(int start, int end)
// ArrayList API
Object clone()
void ensureCapacity(int minimumCapacity)
void trimToSize()
void removeRange(int fromIndex, int toIndex)
第2部ArrayListデータ構造
ArrayListの継承関係
java.lang.Object
↳ java.util.AbstractCollection
↳ java.util.AbstractList
↳ java.util.ArrayList
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable {}
ArrayListとCollectionの関係は下図の通りです.
ArrayListには、
elementData
とsize
の2つの重要なオブジェクトが含まれています.(01)
elementData
は「Object[]タイプの配列」であり、ArrayListに追加された要素が保存されている.実際、elementDataは動的配列であり、構造関数ArrayList(int initialCapacity)によってその初期容量がinitialCapacityであることを実行することができる.パラメータを含まないコンストラクション関数ArrayList()でArrayListを作成する場合、elementDataの容量はデフォルトで10です.ElementData配列のサイズは、ArrayList容量の増加に応じて動的に増加します.具体的な成長方法は、ソース分析のensureCapacity()関数を参照してください.(02)
size
は動的配列の実際の大きさである.第3部ArrayListソースコード解析(JDK 1.6.0_45ベース)
ArrayListの原理をより理解するために、以下にArrayListソースコードを分析する.ArrayListは配列により実現されており,ソースコードは比較的容易に理解できる.
package java.util;
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable
{
//
private static final long serialVersionUID = 8683452581122892189L;
// ArrayList
private transient Object[] elementData;
// ArrayList
private int size;
// ArrayList 。
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
//
this.elementData = new Object[initialCapacity];
}
// ArrayList 。 10。
public ArrayList() {
this(10);
}
// collection ArrayList
public ArrayList(Collection extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
// =
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
// ArrarList 。
// ArrayList , =“( x3)/2 + 1”
public void ensureCapacity(int minCapacity) {
// “ ”+1
modCount++;
int oldCapacity = elementData.length;
// , =“( x3)/2 + 1”
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
// e
public boolean add(E e) {
// ArrayList
ensureCapacity(size + 1); // Increments modCount!!
// e ArrayList
elementData[size++] = e;
return true;
}
// ArrayList
public int size() {
return size;
}
// ArrayList Object(o)
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
// ArrayList
public boolean isEmpty() {
return size == 0;
}
// ,
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;
}
// ( ), (o)
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;
}
// ArrayList Object
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
// ArrayList 。 , T
public T[] toArray(T[] a) {
// a < ArrayList ;
// T[] , “ArrayList ”, “ArrayList”
if (a.length < size)
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
// a >= ArrayList ;
// ArrayList a 。
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
// index
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
// index element
public E set(int index, E element) {
RangeCheck(index);
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
// e ArrayList
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// e ArrayList
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
// ArrayList
public E remove(int index) {
RangeCheck(index);
modCount++;
E oldValue = (E) 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;
}
// ArrayList
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;
}
// index
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
// "index+1" , 。
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// null
elementData[--size] = null; // Let gc do its work
}
//
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// ArrayList, “ o”, , true。
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// ArrayList, null
public void clear() {
modCount++;
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
// c ArrayList
public boolean addAll(Collection extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
// index , c ArrayList
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;
}
// fromIndex toIndex 。
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// Let gc do its work
int newSize = size - (toIndex-fromIndex);
while (size != newSize)
elementData[--size] = null;
}
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
}
//
public Object clone() {
try {
ArrayList v = (ArrayList) super.clone();
// ArrayList v
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();
}
}
// java.io.Serializable
// ArrayList “ , ”
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// “ ”
s.writeInt(elementData.length);
// “ ”
for (int i=0; i
まとめ:
(01)ArrayListは実際には1つの配列でデータを保存している.ArrayListを構築するとデフォルトコンストラクション関数を使用する場合、ArrayListのデフォルト容量サイズは10です.(02)ArrayListの容量が全ての要素を収容するのに足りない場合、ArrayListは容量を新たに設定する:「(元の容量x 3)/2+1」.(03)ArrayListのクローン関数,すなわち全要素を1つの配列にクローンする.(04)ArrayListがjava.io.Serializableを実現する方式.出力ストリームに書き込む場合は、「容量」を書き込み、「各要素」を順次書き込む.入力ストリームを読み出す場合は、「容量」を読み出し、「各要素」を順次読み出す.
第4部ArrayList遍歴方式
ArrayListは3種類の遍歴方式をサポート
(01)第1種は,反復器により遍歴する.つまり、Iteratorを通して巡ります.
Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}
(02)2つ目は,ランダムアクセス,インデックス値による遍歴である.ArrayListはRandomAccessインタフェースを実装しているため、インデックス値による要素へのランダムアクセスをサポートします.
Integer value = null;
int size = list.size();
for (int i=0; i
(03)第3種,forサイクル遍歴.次のようになります.
Integer value = null;
for (Integer integ:list) {
value = integ;
}
次に、この3つの方法の効率を1つの例で比較し、インスタンスコード(ArrayListRandomAccessTest.java)は以下の通りである.
import java.util.*;
import java.util.concurrent.*;
/*
* @desc ArrayList 。
*
* @author skywang
*/
public class ArrayListRandomAccessTest {
public static void main(String[] args) {
List list = new ArrayList();
for (int i=0; i<100000; i++)
list.add(i);
//isRandomAccessSupported(list);
iteratorThroughRandomAccess(list) ;
iteratorThroughIterator(list) ;
iteratorThroughFor2(list) ;
}
private static void isRandomAccessSupported(List list) {
if (list instanceof RandomAccess) {
System.out.println("RandomAccess implemented!");
} else {
System.out.println("RandomAccess not implemented!");
}
}
public static void iteratorThroughRandomAccess(List list) {
long startTime;
long endTime;
startTime = System.currentTimeMillis();
for (int i=0; i
実行結果:
iteratorThroughRandomAccess:3 msiteratorThroughIterator:8 msiteratorThroughFor2:5 ms
このことから,ArrayListを巡る場合,ランダムアクセス(すなわちインデックスシーケンス番号でアクセス)が最も効率的であり,反復器での効率が最も低いことが分かる.
第5部toArray()異常
ArrayListの
toArray()
を呼び出すと、「java.lang.ClassCastException
」異常が投げ出されたことがある.これはどういうことですか.ArrayListには2つのtoArray()関数があります.
Object[] toArray()
T[] toArray(T[] contents)
toArray()関数を呼び出すと「java.lang.ClassCastException」異常が放出されますが、toArray(T[]contents)を呼び出すとT[]が正常に返されます.
toArray()が例外を放出するのは、toArray()がObject[]配列を返し、Object[]を他のタイプ(たとえば、Object[]をInteger[]に変換)に変換すると、Java.lang.ClassCastException例外が放出されます.Javaはダウンコンバートをサポートしていないためです.具体的には、前のArrayList.javaのソースコード紹介部のtoArray()を参照してください.この問題を解決する方法は、Object[]toArray()ではなく、T[]toArray(T[]contents)を呼び出すことです.
toArray(T[]contents)を呼び出してT[]を返すことは、以下のいくつかの方法で実現することができる.
// toArray(T[] contents)
public static Integer[] vectorToArray1(ArrayList v) {
Integer[] newText = new Integer[v.size()];
v.toArray(newText);
return newText;
}
// toArray(T[] contents) 。 !
public static Integer[] vectorToArray2(ArrayList v) {
Integer[] newText = (Integer[])v.toArray(new Integer[0]);
return newText;
}
// toArray(T[] contents)
public static Integer[] vectorToArray3(ArrayList v) {
Integer[] newText = new Integer[v.size()];
Integer[] newStrings = (Integer[])v.toArray(newText);
return newStrings;
}
第6部ArrayList例
ここでは、ArrayListTest.javaの例を用いて、ArrayListでよく使用されるAPIの使用方法について説明します.
import java.util.*;
/*
* @desc ArrayList API
* @author skywang
* @email [email protected]
*/
public class ArrayListTest {
public static void main(String[] args) {
// ArrayList
ArrayList list = new ArrayList();
// “”
list.add("1");
list.add("2");
list.add("3");
list.add("4");
// 1
list.add(0, "5");
// 1
System.out.println("the first element is: "+ list.get(0));
// “3”
list.remove("3");
// ArrayList
System.out.println("Arraylist size=: "+ list.size());
// list "3"
System.out.println("ArrayList contains 3 is: "+ list.contains(3));
// 2 10
list.set(1, "10");
// Iterator ArrayList
for(Iterator iter = list.iterator(); iter.hasNext(); ) {
System.out.println("next is: "+ iter.next());
}
// ArrayList
String[] arr = (String[])list.toArray(new String[0]);
for (String str:arr)
System.out.println("str: "+ str);
// ArrayList
list.clear();
// ArrayList
System.out.println("ArrayList is empty: "+ list.isEmpty());
}
}
実行結果:
the first element is: 5Arraylist size=: 4ArrayList contains 3 is: falsenext is: 5next is: 10next is: 2next is: 4str: 5str: 10str: 2str: 4ArrayList is empty: true
出典:http://www.cnblogs.com/skywang12345/p/3308513.html文章には不適切な点があります.指摘を歓迎します.あなたも私の微信の公衆番号:
java
に注目することができます.良質な学習資源を得ることができます.QQ技術交流グループに参加することもできます.766946816
、javaについて話しましょう.