Java集合フレームのソースコード分析のLinkdHashMap詳細
15652 ワード
Linked HashMap概要
Linked HashMapはHashMapのサブクラスであり、HashMapと同じ記憶構造を持っていますが、双方向のチェーンの頭の結点を入れて、すべてのputからLinked Hashmapのノードを一つの双方向の循環チェーンテーブルにしています。したがって、ノードが挿入する順序を保持しています。ノードの出力順序は入力順序と同じになります。
Linked HashMapはLRUアルゴリズムを実現するために使用できます。
Linked HashMapは同じ非スレッドでも安全です。単スレッド環境でのみ使用します。
Linked HashMapソースの分析
Linked HashMapのソースコードは以下の通りです。
Linked HashMapのソースコードについては、以下のいくつかの比較的重要な要約を与えます。
1、ソースからは、LinkdHashMapにheadの最後のポイントを追加し、Linked HashMapに挿入されたすべてのEntryは挿入された順にheadを先頭とする双方向循環リンクの最後に順次加入していることが分かります。
1、実際にはHashMapとLinkdListの2つのセットの記憶構造の組み合わせです。Linked HashMapMapでは、すべてのputから入ってきたEntryはハッシュテーブルに保存されていますが、headを頭とする空の双方向循環チェーンテーブルを追加的に定義しました。putは毎回Entryに入ってきて、ハッシュテーブルに対応する位置に保存する以外に、双方向循環チェーンの末尾に挿入します。
2、Linked HashMapはHashMapから継承されているため、HashMapの全ての特性を持っており、同様にkeyとvalueをnullとすることができます。
3、ソースコードのaccessOrderマークの位置に注意してください。falseの場合、双方向チェーンの要素はEntryによってLinked HashMapに挿入された順に並べ替えられます。つまり、毎回putからLinkdHashMapのEntryは双方向チェーンの末尾に置かれます。このように双方向チェーン表を巡る時、Entryの出力順は挿入順と一致します。これもデフォルトの双方向チェーンの格納順序です。trueの場合は、双方向リンクの要素が訪問順に配列されていることを示していますが、Entryチェーンを挿入する順序は依然としてputからLinked HashMapまでの順ですが、putとgetはrecordAccessメソッドを呼び出します。この方法はaccessOrderがtrueであるかどうかを判断し、もしそうであれば、現在訪問しているEntryを双方向チェーンの末尾に移動させます。また、putの新しいEntryを呼び出すと、creat Entryを呼び出します。この方法は同じように新たに挿入された要素を双方向チェーンの末尾に挿入します。また訪問の先着順にも合致します。この時はEntryも訪問されますから。そうでなければ、何もしません。
4、構造方法に注意して、前の4つの構造方法はいずれもaccessOrderをfalseとして設定し、デフォルトは挿入順に並べ替えられていると説明していますが、第5の構造方法は輸入されたaccessOrderの値をカスタマイズできます。したがって、双方向循環チェーンにおける要素の並べ替え規則を指定できます。一般的に、LinkdHashMapでLRUアルゴリズムを実現します。この構造方法を使います。accessOrderをtrueにします。
5、Linked HashMapはHashMapのputメソッドを上書きしていません。putメソッドで呼び出されたaddEnty方法とrecordAccess方法を上書きしました。私達は振り返ってHashMapのput方法を見ます。
まずrecordAccessの方法を見に来ました。
addEntry方法を見てみます。
上にはレモベ・ワールド・エンドの方法があります。この方法は以下の通りです。
6、Linked HashMapにHashMapのget方法を上書きしました。
7、最後にLinked HashMapがどのようにLRUを実現したかを話します。
まず、accessOrderがtrueであるときに、アクセス順に並べ替えられたモードが開かれ、LRUアルゴリズムが実現される。put方法であれget方法であれ、ターゲットのEntryが最近の訪問のEntryになるため、このEnttryを双方向チェーンの末尾に追加しました。（get方法はrecordAccessメソッドを呼び出すことによって実現されます。put方法は既存のkeyを上書きする場合も、recordAccessメソッドを呼び出すことによって実現されます。新しいEntyを挿入する時にも、このように、最近使ったEntryを双方向チェーンの後ろに入れ、複数回操作した後、双方向チェーンの前のEntryは最近は使われていません。ノードの数がいっぱいになると、一番前のEntryが削除されます。
結尾語
以上はJava集合フレームワークのソースコード分析のLinkedHashMapの詳細な内容のすべてです。Javaの学習に役立つことを願っています。みなさん、当駅の他のテーマを参照してください。私たちのサポートを読んでくれてありがとうございます。
Linked HashMapはHashMapのサブクラスであり、HashMapと同じ記憶構造を持っていますが、双方向のチェーンの頭の結点を入れて、すべてのputからLinked Hashmapのノードを一つの双方向の循環チェーンテーブルにしています。したがって、ノードが挿入する順序を保持しています。ノードの出力順序は入力順序と同じになります。
Linked HashMapはLRUアルゴリズムを実現するために使用できます。
Linked HashMapは同じ非スレッドでも安全です。単スレッド環境でのみ使用します。
Linked HashMapソースの分析
Linked HashMapのソースコードは以下の通りです。
package java.util;
import java.io.*;
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
private static final long serialVersionUID = 3801124242820219131L;
// ， LinkedHashMap header，
// Entry ，header key-value ，
private transient Entry<K,V> header;
// 。
//accessOrder false，
//accessOrder true，
private final boolean accessOrder;
// HashMap
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false; //
}
// 0.75f
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
// 0.75f， 16
public LinkedHashMap() {
super();
accessOrder = false;
}
// Map ， HashMap
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(m);
accessOrder = false;
}
//
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
// init() （HashMap init ），
// Clone、readObject ，
// ， ， 。
void init() {
header = new Entry<K,V>(-1, null, null, null);
header.before = header.after = header;
}
// HashMap transfer ， resize ，
// ， key-value newTable
// ，
// ， for 。
void transfer(HashMap.Entry[] newTable) {
int newCapacity = newTable.length;
for (Entry<K,V> e = header.after; e != header; e = e.after) {
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}
// HashMap containsValue ，
// ，
// ， for
public boolean containsValue(Object value) {
// Overridden to take advantage of faster iterator
if (value==null) {
for (Entry e = header.after; e != header; e = e.after)
if (e.value==null)
return true;
} else {
for (Entry e = header.after; e != header; e = e.after)
if (value.equals(e.value))
return true;
}
return false;
}
// HashMap get ， getEntry Entry 。
// recordAccess ，
// ， ，
// ， e 。
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
// HashMap，
public void clear() {
super.clear();
header.before = header.after = header;
}
//Enty ，
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// These fields comprise the doubly linked list used for iteration.
Entry<K,V> before, after;
//
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
// ， Entry
private void remove() {
before.after = after;
after.before = before;
}
// ， Entry existingEntry
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
// HashMap recordAccess （HashMap ），
// put ， key ， ，
// LinkedHashmap get ， ，
// LRU ， Entry ，
//accessOrder true ，get recordAccess
//put key-value recordAccess
// Entry ，
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
// ， Entry ，
// ， 。
if (lm.accessOrder) {
lm.modCount++;
// Entry
remove();
// Entry
addBefore(lm.header);
}
}
void recordRemoval(HashMap<K,V> m) {
remove();
}
}
//
private abstract class LinkedHashIterator<T> implements Iterator<T> {
Entry<K,V> nextEntry = header.after;
Entry<K,V> lastReturned = null;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;
public boolean hasNext() {
return nextEntry != header;
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
// head
Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
}
//key
private class KeyIterator extends LinkedHashIterator<K> {
public K next() { return nextEntry().getKey(); }
}
//value
private class ValueIterator extends LinkedHashIterator<V> {
public V next() { return nextEntry().value; }
}
//Entry
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() { return nextEntry(); }
}
// These Overrides alter the behavior of superclass view iterator() methods
Iterator<K> newKeyIterator() { return new KeyIterator(); }
Iterator<V> newValueIterator() { return new ValueIterator(); }
Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
// HashMap addEntry ，LinkedHashmap HashMap put ，
// put addEntry recordAccess ，
//put key ， recordAccess ，
// key ， addEntry Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
// Entry， LinkedHashMap
createEntry(hash, key, value, bucketIndex);
// （header ）
Entry<K,V> eldest = header.after;
// ， ，
// removeEldestEntry , false， 。
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
// 2
if (size >= threshold)
resize(2 * table.length);
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
// Entry， ， HashMap
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
table[bucketIndex] = e;
// Entry ， ，
// Entry LinkedHashMap ，
// ， put Entry Entry， ， LRU
e.addBefore(header);
size++;
}
// ， LinkedHashmap LRU ， ，
// ， true， LinkedHashMap put
//Entry ， addEntry （header ）。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
} Linked HashMapのソースコードについては、以下のいくつかの比較的重要な要約を与えます。
1、ソースからは、LinkdHashMapにheadの最後のポイントを追加し、Linked HashMapに挿入されたすべてのEntryは挿入された順にheadを先頭とする双方向循環リンクの最後に順次加入していることが分かります。
1、実際にはHashMapとLinkdListの2つのセットの記憶構造の組み合わせです。Linked HashMapMapでは、すべてのputから入ってきたEntryはハッシュテーブルに保存されていますが、headを頭とする空の双方向循環チェーンテーブルを追加的に定義しました。putは毎回Entryに入ってきて、ハッシュテーブルに対応する位置に保存する以外に、双方向循環チェーンの末尾に挿入します。
2、Linked HashMapはHashMapから継承されているため、HashMapの全ての特性を持っており、同様にkeyとvalueをnullとすることができます。
3、ソースコードのaccessOrderマークの位置に注意してください。falseの場合、双方向チェーンの要素はEntryによってLinked HashMapに挿入された順に並べ替えられます。つまり、毎回putからLinkdHashMapのEntryは双方向チェーンの末尾に置かれます。このように双方向チェーン表を巡る時、Entryの出力順は挿入順と一致します。これもデフォルトの双方向チェーンの格納順序です。trueの場合は、双方向リンクの要素が訪問順に配列されていることを示していますが、Entryチェーンを挿入する順序は依然としてputからLinked HashMapまでの順ですが、putとgetはrecordAccessメソッドを呼び出します。この方法はaccessOrderがtrueであるかどうかを判断し、もしそうであれば、現在訪問しているEntryを双方向チェーンの末尾に移動させます。また、putの新しいEntryを呼び出すと、creat Entryを呼び出します。この方法は同じように新たに挿入された要素を双方向チェーンの末尾に挿入します。また訪問の先着順にも合致します。この時はEntryも訪問されますから。そうでなければ、何もしません。
4、構造方法に注意して、前の4つの構造方法はいずれもaccessOrderをfalseとして設定し、デフォルトは挿入順に並べ替えられていると説明していますが、第5の構造方法は輸入されたaccessOrderの値をカスタマイズできます。したがって、双方向循環チェーンにおける要素の並べ替え規則を指定できます。一般的に、LinkdHashMapでLRUアルゴリズムを実現します。この構造方法を使います。accessOrderをtrueにします。
5、Linked HashMapはHashMapのputメソッドを上書きしていません。putメソッドで呼び出されたaddEnty方法とrecordAccess方法を上書きしました。私達は振り返ってHashMapのput方法を見ます。
// “key-value” HashMap
public V put(K key, V value) {
// “key null”， table[0] 。
if (key == null)
return putForNullKey(value);
// “key null”， key ， 。
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// “ key” ， value value。 ！
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// “ key” ， “key-value” table
modCount++;
// key-value table[i]
addEntry(hash, key, value, i);
return null;
} まずrecordAccessの方法を見に来ました。
// HashMap recordAccess （HashMap ），
// put ， key ， ，
// LinkedHashmap get ， ，
// LRU ， Entry ，
//accessOrder true ，get recordAccess
//put key-value recordAccess
// Entry ，
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
// ， Entry ，
// ， 。
if (lm.accessOrder) {
lm.modCount++;
// Entry
remove();
// Entry
addBefore(lm.header);
}
} addEntry方法を見てみます。
// HashMap addEntry ，LinkedHashmap HashMap put ，
// put addEntry recordAccess ，
//put key ， recordAccess ，
// key ， addEntry Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
// Entry， LinkedHashMap
createEntry(hash, key, value, bucketIndex);
// （header ）
Entry<K,V> eldest = header.after;
// ， ，
// removeEldestEntry , false， 。
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
// 2
if (size >= threshold)
resize(2 * table.length);
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
// Entry， ， HashMap
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
table[bucketIndex] = e;
// Entry ， ，
// Entry LinkedHashMap ，
// ， put Entry Entry， ， LRU
e.addBefore(header);
size++;
} 上にはレモベ・ワールド・エンドの方法があります。この方法は以下の通りです。
// ， LinkedHashmap LRU ， ，
// ， true， LinkedHashMap put
//Entry ， addEntry （header ）。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
} 6、Linked HashMapにHashMapのget方法を上書きしました。
// HashMap get ， getEntry Entry 。
// recordAccess ，
// ， ，
// ， e 。
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
} 7、最後にLinked HashMapがどのようにLRUを実現したかを話します。
まず、accessOrderがtrueであるときに、アクセス順に並べ替えられたモードが開かれ、LRUアルゴリズムが実現される。put方法であれget方法であれ、ターゲットのEntryが最近の訪問のEntryになるため、このEnttryを双方向チェーンの末尾に追加しました。（get方法はrecordAccessメソッドを呼び出すことによって実現されます。put方法は既存のkeyを上書きする場合も、recordAccessメソッドを呼び出すことによって実現されます。新しいEntyを挿入する時にも、このように、最近使ったEntryを双方向チェーンの後ろに入れ、複数回操作した後、双方向チェーンの前のEntryは最近は使われていません。ノードの数がいっぱいになると、一番前のEntryが削除されます。
結尾語
以上はJava集合フレームワークのソースコード分析のLinkedHashMapの詳細な内容のすべてです。Javaの学習に役立つことを願っています。みなさん、当駅の他のテーマを参照してください。私たちのサポートを読んでくれてありがとうございます。