Java基礎知識トラップ(七)
7723 ワード
本文は本人ブログに発表された.
前回HashSetとHashMapの関係についてお話ししましたが、HashMapという内部には次のようなものがあります.
この文は定数を表し、容器の数が0.75%に達すると、2倍の大きさの配列を再構築する役割を果たす.なんとこの2つが集合なのか、今日は他の集合クラスを見てみましょう.例えば、ArrayList、Vector、LinkedList、始めましょう.
まずArrayListのソースコードを見てみましょう.これらの集合クラスはjavaです.utilパッケージ下;構造を見てください.
new ArrayList()の場合、本質的には内部で長さ10のObjectオブジェクト配列をデフォルトで初期化していることがわかります.内部は配列で実現されていることが分かった.続けて見てみましょう.もし私たちがaddしたときはどうでしたか.コードを見てみましょう.
ここで、addオブジェクトの場合はまず挿入位置の小標が配列の長さより大きいかどうかを判断し、そうであれば1つの配列を再インスタンス化してelementDataに割り当て、配列を再インスタンス化する場合は長さを現在の長さ*3/2+1で計算します.それはaddのたびに判断し、一度に多くの(数百数千万)要素オブジェクトを挿入すれば想像できます.10個の要素の場合は1つの配列を再インスタンス化し、16個の場合は再び、25個の場合は再び、このような性能はあまりにも悪いはずなので、配列の長さを知っている場合は、直接パラメータ構造を呼び出して性能を向上させることができます.
次に、クエリーの方法を見てみましょう.
クエリが配列全体を巡っていることがわかります!コードを削除するには、次の手順に従います.
この削除されたコードも、まず小標が超えているかどうかを判断し、そうでなければ配列を切り取る.この書き込みから,ArrayListは検索時に直接下付きループを用い,削除を増やす際に新しい配列を再構築する必要があり,性能消費が大きいことがわかる.
では、Vectorというクラスを見てみましょう.まず、その構造を見てみましょう.
このVectorの内部でもObject配列を使用して実装されていることがわかります.initialCapacityでは、設定された配列の長さを見ることができますが、capacityIncrementは何ですか.注釈を見てみましょう.
私は英語が下手で、奇抜で、私たちが使う場所を見るのは少し難しいです.
このコードからcapacityIncrement>0が設定されている場合、オブジェクトを追加すると、新しい配列を再構築するときに新しい配列の長さとして使用され、そうでなければ元の配列の長さの2倍になります.OK!兄弟は英語が下手で,苦労しているんだよ.
次に、その追加削除がどのように実現されているかを見てみましょう.コードを見てください:
あら、synchronizedキーワードが出てきました.同期管理ですよ.Addを追加するときは、新しい配列を再構築する必要があるかどうかを判断し、値を付与します.削除するときは下付き文字が超えているかどうかを判断し、そうでなければ直接配列を切り取ります.これはArrayListと同じです.これにより,Vector内部でも配列を用いて実現されていることが分かるが,削除を増やしていくつかの方法がある場合には同期を用いてマルチスレッドでも正確であることが保証される.このパフォーマンスはArrayListよりもやや優れていますが、マルチスレッド環境ではこれを使用してクエリが正しく実行されるようにする必要があります.
次にLinkedListを見て、そのコードを見てみましょう.
これを見ると、このLinkedListがDequeを実現していることがわかりますよ.これを見てみると、双方向ループのチェーンテーブルです.それはチェーンテーブルです.皆さんは知っているはずです.チェーンテーブルはデータを挿入してデータを削除するときに配列しないのが速いです.データを削除しなくても直接ポインタを修正すればいいからです.しかし、悪いところはクエリーです.まず、現在のノードの位置から下かネット上で次の検索に時間がかかります.
上記のコードから,削除を増やすことはヘッダのノードを操作するだけでよいことがわかり,パフォーマンスが大幅に向上する.
このコードからヘッダをリンクノードとして使用し,ヘッダにpreviousおよびnextノードを探し,前後にチェーンテーブル全体のループを構成していることがわかる.
今回はとりあえずここまで.記録を続けて少しずつ!
前回HashSetとHashMapの関係についてお話ししましたが、HashMapという内部には次のようなものがあります.
static final float DEFAULT_LOAD_FACTOR = 0.75f;この文は定数を表し、容器の数が0.75%に達すると、2倍の大きさの配列を再構築する役割を果たす.なんとこの2つが集合なのか、今日は他の集合クラスを見てみましょう.例えば、ArrayList、Vector、LinkedList、始めましょう.
まずArrayListのソースコードを見てみましょう.これらの集合クラスはjavaです.utilパッケージ下;構造を見てください.
private transient Object[] elementData;
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() {
this(10);
}new ArrayList()の場合、本質的には内部で長さ10のObjectオブジェクト配列をデフォルトで初期化していることがわかります.内部は配列で実現されていることが分かった.続けて見てみましょう.もし私たちがaddしたときはどうでしたか.コードを見てみましょう.
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
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 = Arrays.copyOf(elementData, newCapacity);
}
}ここで、addオブジェクトの場合はまず挿入位置の小標が配列の長さより大きいかどうかを判断し、そうであれば1つの配列を再インスタンス化してelementDataに割り当て、配列を再インスタンス化する場合は長さを現在の長さ*3/2+1で計算します.それはaddのたびに判断し、一度に多くの(数百数千万)要素オブジェクトを挿入すれば想像できます.10個の要素の場合は1つの配列を再インスタンス化し、16個の場合は再び、25個の場合は再び、このような性能はあまりにも悪いはずなので、配列の長さを知っている場合は、直接パラメータ構造を呼び出して性能を向上させることができます.
ArrayList list = new ArrayList(10000);次に、クエリーの方法を見てみましょう.
public boolean contains(Object o) {
return indexOf(o) >= 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 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;
return oldValue;
}
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
}この削除されたコードも、まず小標が超えているかどうかを判断し、そうでなければ配列を切り取る.この書き込みから,ArrayListは検索時に直接下付きループを用い,削除を増やす際に新しい配列を再構築する必要があり,性能消費が大きいことがわかる.
では、Vectorというクラスを見てみましょう.まず、その構造を見てみましょう.
protected Object[] elementData;
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector() {
this(10);
}
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}このVectorの内部でもObject配列を使用して実装されていることがわかります.initialCapacityでは、設定された配列の長さを見ることができますが、capacityIncrementは何ですか.注釈を見てみましょう.
/**
* The amount by which the capacity of the vector is automatically
* incremented when its size becomes greater than its capacity. If
* the capacity increment is less than or equal to zero, the capacity
* of the vector is doubled each time it needs to grow.
*
* @serial
*/私は英語が下手で、奇抜で、私たちが使う場所を見るのは少し難しいです.
private void ensureCapacityHelper(int minCapacity) {
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object[] oldData = elementData;
int newCapacity = (capacityIncrement > 0) ?(oldCapacity + capacityIncrement) : (oldCapacity * 2);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
}このコードからcapacityIncrement>0が設定されている場合、オブジェクトを追加すると、新しい配列を再構築するときに新しい配列の長さとして使用され、そうでなければ元の配列の長さの2倍になります.OK!兄弟は英語が下手で,苦労しているんだよ.
次に、その追加削除がどのように実現されているかを見てみましょう.コードを見てください:
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
Object oldValue = elementData[index];
int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--elementCount] = null;
return (E)oldValue;
}あら、synchronizedキーワードが出てきました.同期管理ですよ.Addを追加するときは、新しい配列を再構築する必要があるかどうかを判断し、値を付与します.削除するときは下付き文字が超えているかどうかを判断し、そうでなければ直接配列を切り取ります.これはArrayListと同じです.これにより,Vector内部でも配列を用いて実現されていることが分かるが,削除を増やしていくつかの方法がある場合には同期を用いてマルチスレッドでも正確であることが保証される.このパフォーマンスはArrayListよりもやや優れていますが、マルチスレッド環境ではこれを使用してクエリが正しく実行されるようにする必要があります.
次にLinkedListを見て、そのコードを見てみましょう.
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializableこれを見ると、このLinkedListがDequeを実現していることがわかりますよ.これを見てみると、双方向ループのチェーンテーブルです.それはチェーンテーブルです.皆さんは知っているはずです.チェーンテーブルはデータを挿入してデータを削除するときに配列しないのが速いです.データを削除しなくても直接ポインタを修正すればいいからです.しかし、悪いところはクエリーです.まず、現在のノードの位置から下かネット上で次の検索に時間がかかります.
public boolean add(E e) {
addBefore(e, header);
return true;
}
private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
size--;
modCount++;
return result;
}上記のコードから,削除を増やすことはヘッダのノードを操作するだけでよいことがわかり,パフォーマンスが大幅に向上する.
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
public LinkedList() {
header.next = header.previous = header;
}
private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
......
......
}このコードからヘッダをリンクノードとして使用し,ヘッダにpreviousおよびnextノードを探し,前後にチェーンテーブル全体のループを構成していることがわかる.
今回はとりあえずここまで.記録を続けて少しずつ!