JAva jdk 8ソース解析のutilパッケージ:list集合クラスソース分析
7207 ワード
List集合は秩序ある集合として,ユーザがリスト内の要素の位置をよく把握し,整数のインデックスによりリストから所望のデータを取得できる.
1.Collection
collectionクラスは集合の中で基本的なインタフェースであり、1つの集合はこのオブジェクトのグループを表し、一部の集合は秩序正しく無秩序であり、jdkはCollectionインタフェースからの直接的な実装を提供していない.リストやsetなどのより多くのサブインタフェースの実装を提供しているので、このインタフェースは集合の最大の汎用性を保証するために設定されている.彼の方法名は主に次のとおりです.
2.ArrayList
サイズ変更可能な配列であり、List(Collectionサブインタフェース)インタフェースを継承し、list操作の大部分を実現し、null値を含むすべてのタイプの要素と重複値を挿入することができる.基本操作のほか、内部配列サイズを制御する方法も多く、スレッド同期ではない.クラス継承は以下の通りである.
拡張方法を主に分析します.
removeメソッド
getメソッド
ソースコードから,追加操作は削除操作よりも時間的複雑度が小さく,追加はO(1),削除はO(n),コンテナの拡張と削除要素はcopyofとarrycopyメソッドを呼び出し,下位層はc++を実現するため効率が高いことが分かる.コンテナの容積は限られており、最大値はintタイプの最大値である.
2.LinkList
ダブルチェーンテーブル構造に属し、ListとDequeインタフェースを継承し、空の値を含む任意の値と重複値を挿入できます.
Deque:デュアルチェーンテーブルの操作方法を定義し、サブクラスの汎用性を向上
AbstraactSequentialList:この抽象クラスは、このインタフェースを実装するワークロードを低減するためのフレームワークの実装を提供し、リストを順次格納する実装に適しています.
addメソッド
removeメソッド
getメソッド
linklistクラスで、内部は双方向チェーンテーブル構造です.チェーンテーブル内のnodeオブジェクトごとに、前後の要素の参照が保存されます.チェーンテーブルの両端に挿入削除を行うことができます.それ以外は容量に制限されません.配列要素は無限に複数あります(仮想マシン構成に関連しています).クエリーでは、比較的線形テーブルを最初から最後から巡回する必要があります.
3.Vector
同期バージョンのArrayListクラスは,ArrayList実装の原理とほぼ同じである.唯一の違いは、Vectorがスレッドで安全であることです.主なadd方法は以下の通りである.
以上がリスト集合に対する私の理解です.
1.Collection
collectionクラスは集合の中で基本的なインタフェースであり、1つの集合はこのオブジェクトのグループを表し、一部の集合は秩序正しく無秩序であり、jdkはCollectionインタフェースからの直接的な実装を提供していない.リストやsetなどのより多くのサブインタフェースの実装を提供しているので、このインタフェースは集合の最大の汎用性を保証するために設定されている.彼の方法名は主に次のとおりです.
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator iterator();
Object[] toArray(); //
boolean add(E e);
boolean remove(Object o);
2.ArrayList
サイズ変更可能な配列であり、List(Collectionサブインタフェース)インタフェースを継承し、list操作の大部分を実現し、null値を含むすべてのタイプの要素と重複値を挿入することができる.基本操作のほか、内部配列サイズを制御する方法も多く、スレッド同期ではない.クラス継承は以下の通りである.
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable{
transient Object[] elementData; // Object
...
} add public boolean add(E e) {
ensureCapacityInternal(size + 1); //
elementData[size++] = e;
return true;
}拡張方法を主に分析します.
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // ，
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
} private void ensureExplicitCapacity(int minCapacity) {
modCount++; //
//
if (minCapacity - elementData.length > 0)
grow(minCapacity);
} private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1/2
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) // （ int ）
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); //
}removeメソッド
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])) { // equals
fastRemove(index);
return true;
}
}
return false;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1; //
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved); // arraycopy
elementData[--size] = null; // clear to let GC do its work
}getメソッド
public E get(int index) {
rangeCheck(index); // index
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index]; //
}ソースコードから,追加操作は削除操作よりも時間的複雑度が小さく,追加はO(1),削除はO(n),コンテナの拡張と削除要素はcopyofとarrycopyメソッドを呼び出し,下位層はc++を実現するため効率が高いことが分かる.コンテナの容積は限られており、最大値はintタイプの最大値である.
2.LinkList
ダブルチェーンテーブル構造に属し、ListとDequeインタフェースを継承し、空の値を含む任意の値と重複値を挿入できます.
public class LinkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable
{
transient int size = 0; //
transient Node first; //
transient Node last; //
private static class Node {
E item;
Node next; //
Node prev; //
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
....
}
Deque:デュアルチェーンテーブルの操作方法を定義し、サブクラスの汎用性を向上
AbstraactSequentialList:この抽象クラスは、このインタフェースを実装するワークロードを低減するためのフレームワークの実装を提供し、リストを順次格納する実装に適しています.
addメソッド
public boolean add(E e) {
linkLast(e); //
return true;
}
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null) //
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
removeメソッド
public boolean remove(Object o) {
if (o == null) {
for (Node x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node x) { //x
// assert x != null;
final E element = x.item;
final Node next = x.next;
final Node prev = x.prev;
if (prev == null) { //
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) { //
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null; //
size--;
modCount++;
return element;
} getメソッド
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) { // index
Node x = first;
for (int i = 0; i < index; i++) //
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
} linklistクラスで、内部は双方向チェーンテーブル構造です.チェーンテーブル内のnodeオブジェクトごとに、前後の要素の参照が保存されます.チェーンテーブルの両端に挿入削除を行うことができます.それ以外は容量に制限されません.配列要素は無限に複数あります(仮想マシン構成に関連しています).クエリーでは、比較的線形テーブルを最初から最後から巡回する必要があります.
3.Vector
同期バージョンのArrayListクラスは,ArrayList実装の原理とほぼ同じである.唯一の違いは、Vectorがスレッドで安全であることです.主なadd方法は以下の通りである.
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1); //
elementData[elementCount++] = e;
return true;
}以上がリスト集合に対する私の理解です.