この記事では、LinkedHashmapのソースコードの分析を開始しました。 LinkedhashmapはHashMapを継承します。つまり、LinkedhashmapはHashMapに基づいて拡張されます。したがって、LinkedHashmapのソースコードを見る前に、読者はHashMapのソースコードを理解する必要があります。以前の記事「Java Collection Series [3] ---- Hashmapソースコード分析」の導入を確認できます。 HashMapの実装原則を深く理解し、LinkedHashmapのソースコードを見ると、HashsetとLinkedhashsetはすべて非常に簡単です。したがって、読者は忍耐強く、ハッシュマップソースコードを研究する必要があります。これは、1つを購入する良いビジネスです。 HashMapソースコードを以前に分析するとき、ソースコードの問題指向分析を使用して、ヘッドレスフライのようにランダムに分析せず、読者も問題をより深く理解できるようにしました。この記事では、この方法を使用してLinkedhashmapを分析することにしました。
1. LinkedHashmap内でどのような構造が使用されていますか？
ご覧のとおり、LinkedHashmapはHashMapから継承されているため、LinkedHashmap内にハッシュテーブルがまだありますが、LinkedHashmapはエントリを書き直し、元のハッシュマップエントリ、つまり以前のノードリファレンスと後継ノードリファレンスに2つのメンバー変数を追加しました。このようにして、すべてのノードがリンクされ、双方向リンクリストを形成します。要素を取得するときは、双方向リンクリストを直接通過するだけです。エントリのLinkedHashmapの実装がどのように見えるか見てみましょう。
プライベート静的クラスエントリ<k、v> hashmap.entry <k、v> {//双方向リンクリストエントリの現在のノードの前のノードの参照<k、v> //双方向リンクリストエントリの現在のノードの後続ノードの参照<k、v> after; entry（int hash、k key、v value、hashmap.entry <k、v> next）{super（hash、key、value、next）; } //このノードをbidirectional linked list private void remove（）{before.after = after; after.before = before; } //現在のノードを双方向リンクリストに既存のノードに挿入しますプライベートボイドaddbebefore（entry <k、v> expentingentry）{// //現在のノードの前のノードの参照は、指定されたノードの前のノードを指しています= expstingEntry.before; //指定されたノードの次のノードの参照は、前の現在のノードをポイントします。After= this; //指定されたノードの前のノードの参照は、現在のノードを指します。before= this; } //アクセスの順に並べ替え、操作が取得されるたびに記録operime opid recordaccess（hashmap <k、v> m）{linkedhashmap <k、v> lm =（linkedhashmap <k、v>）m; //アクセス順序でソートされた場合（lm.Accessorder）{lm.ModCount ++; //最初に双方向リンクリストから自分自身を削除します。 //双方向リンクリストの尾に自分自身を置きますaddbefore（lm.header）; }} void RecordRemoval（hashmap <k、v> m）{remove（）; }}2。LinkedHashmapは挿入順序でソートをどのように実装しますか？
//親クラスのプット方法で呼び出されるメソッドは、void addentry（int hash、k key、v value、int bucketindex）{//親クラスのaddentryメソッドを呼び出すsuper.addentry（hash、key、value、bucketindex）; //次の操作は、LRUキャッシュの実装に便利です。キャッシュ容量が不十分な場合は、最も古い要素エントリ<K、V>高齢者= header.afterを削除します。 if（removeeldestentry（eldest））{removeentryforkey（eldest.key）; }} //メソッドvoid createentry（int hash、k key、v value、int bucketindex）{//最初にHashmap.entry <K、v> old = table [bucketindex]; // linkedhashmapの独自のエントリ<k、v> e = new entry <>（hash、key、value、old）にそれを包みます。表[BucketIndex] = e; //現在のノードを双方向リンクリストのテールに挿入しますe.addbefored（header）;サイズ++;}Linkedhashmapは、親クラスのハッシュマップのアドエントリーとcreateentryのメソッドを無効にします。キー値ペアを挿入する場合、親クラスのハッシュマップのPUTメソッドが最初に呼び出されます。 PUTメソッドでは、対応するキーがハッシュテーブルに存在するかどうかを確認します。存在する場合は、その値を直接交換してください。存在しない場合は、Addentryメソッドを呼び出して新しいエントリを作成します。現時点では、LinkedHashmap独自のAddentryメソッドが呼び出されていることに注意してください。上記のコードが表示されます。親クラスのaddeldestententryメソッドを呼び戻すことに加えて、このaddeldestententryは、最古の要素を削除するためにremoveeldestentryを呼び出します。この操作は、主にLRUアルゴリズムを実装するためのもので、以下で説明します。 LinkedHashmapもCreateEntryメソッドを書き換えていることがわかります。新しいエントリを作成する場合、この方法は呼び出されます。エントリがハッシュテーブルに入力されるたびに、AddBeforeメソッドが呼び出され、現在のノードが双方向リンクリストのテールに挿入されます。このようにして、双方向リンクリストは、挿入された各ノードの順序を記録します。要素を取得するときは、双方向リンクリストを横断するだけです。次の図は、各呼び出しの操作を示しています。これは双方向リンクリストであるため、現在のノードをヘッドノードに挿入する前に、実際に現在のノードを双方向リンクリストのテールに挿入しています。
3. LinkedHashmapを使用してLRUキャッシュを実装する方法は？
キャッシュの実装はコンピューターのメモリに依存し、メモリリソースが非常に限られていることを知っています。また、制限なく要素を保存することは不可能です。したがって、容量が不十分な場合は、いくつかの要素を適切に削除する必要があります。では、どの要素を削除する方が良いでしょうか？ LRUアルゴリズムのアイデアは、最近データにアクセスされた場合、将来アクセスされる可能性も高くなるということです。そのため、アクセスされないデータを削除できます。次に、LinkedHashmapがLRUメカニズムをどのように実装するかを見てみましょう。
public class linkedhashmap <k、v> extends hashmap <k、v>はmap <k、v> {//両方のリンクリストヘッダープライベートトランジェントエントリ<k、v>ヘッダー。 //アクセスの順にプライベートファイナルブールアクセスオーダーを並べ替えます。 ... public linkedhashmap（int initialcapacity、float loadfactor、boolean accessorder）{super（initialcapacity、loadfactor）; this.accessorder = AccessOrder; } //キーパブリックv get（オブジェクトキー）に従って値を取得{//親クラスメソッドを呼び出して対応するエントリエントリ<k、v> e =（entry <k、v>）getentry（key）; if（e == null）{return null; } //アクセス順序でソートされている場合、各使用後のノードは、双方向リンクリストe.RecordAccess（this）の最後に配置されます。 e.valueを返します。 } private staticクラスエントリ<k、v> hashmap.entry <k、v> {... //双方向リンクリストの既存のノードの前に現在のノードを挿入します。 //現在のノードの前のノードの参照は、指定されたノードの前のノードを指しています= expstingEntry.before; //指定されたノードの次のノードの参照は、前の現在のノードをポイントします。After= this; //指定されたノードの前のノードの参照は、現在のノードを指します。before= this; } //アクセス順序でソートされ、操作void recordaccess（hashmap <k、v> m）{linkedhashmap <k、v> lm =（linkedhashmap <k、v>）m; //アクセス順序でソートされた場合（lm.Accessorder）{lm.ModCount ++; //最初に双方向リンクリストから自分自身を削除します。 //双方向リンクリストの尾に自分自身を置きますaddbefore（lm.header）; }} ...} //このメソッドは、親クラスで呼び出されます。 //次の操作は、LRUキャッシュの実装に便利です。キャッシュ容量が不十分な場合は、最も古い要素エントリ<K、V>高齢者= header.afterを削除します。 if（removeeldestentry（eldest））{removeeldestforkey（eldest.key）; }} //最古の要素をどこで削除するのですか？この方法は、サブクラスで上書きされ、保護されたブールンremoverdestententry（map.entry <k、v>高齢者）によって上書きされるように設計されています{return false; }}より直感的になるために、上記のコードにいくつかの無関係なコードを省略しました。 LinkedHashmapにはメンバー変数AccessOrderがあることがわかります。これは、アクセスの順にソートする必要があるかどうかを記録します。 AccessOrder自体の値を指定できるコンストラクターを提供します。 GETメソッドを呼び出して要素を取得するたびに、E.RecordAccess（This）が呼び出され、現在のノードが双方向リンクリストの最後に移動します。 AccessOrderがTrueである場合、要素を取得するたびに、この要素を双方向リンクリストの最後に移動することがわかります。このステップの目的は、最も一般的に使用される要素と頻繁に使用されていない要素を区別することであり、しばしば使用される要素は端に配置され、あまり一般的に使用されていない要素が頭に配置されます。上記のコードに戻り、Addentryメソッドが呼び出されるたびに、最古の要素を削除する必要があるかどうかを判断します。判断の論理は、remodeeldestentryによって実装されます。これは、サブクラスによってオーバーライドされ、内部のロジックを書き直すように設計されています。最近訪問したノードは双方向リンクリストの尾に移動されるため、最古のノードは削除のために双方向リンクリストのヘッドから取り出されることに注意してください。次の例では、単純なLRUキャッシュを実装しています。
public class lrumap <k、v>は、linkedhashmap <k、v> {private int capity;を拡張します。 lrumap（int容量）{//親クラスコンストラクターを呼び、アクセスオーダースーパー（容量、1f、true）でソートするように設定されています。 this.capacity = capurity; } @Override public boolean removeEldestentry（map.entry <k、v> landly）{//キー値ペアがハッシュテーブル容量以上である場合は、this.size（）> =容量を返します。 } public static void main（string [] args）{lrumap <integer、string> map = new lrumap <integer、string>（4）; map.put（1、 "a"）; map.put（2、 "b"）; map.put（3、 "c"）; System.out.println（ "オリジナルコレクション：" +マップ）;文字列s = map.get（2）; system.out.println（ "get element：" + map）; map.put（4、 "d"）; system.out.println（ "挿入後：" +マップ）; }}結果は次のとおりです。
注：上記の分析はすべてJDK1.7に基づいており、異なるバージョン間に違いがあります。読者は注意を払う必要があります。
上記はこの記事のすべての内容です。みんなの学習に役立つことを願っています。誰もがwulin.comをもっとサポートすることを願っています。