人気の説明: キャッシュ、キャッシュ アルゴリズム、キャッシュ フレームワークの概要

[[437580]]

導入

私たちは皆、キャッシュについて聞いたことがあります。キャッシュとは何かと尋ねると、完璧な答えが返ってきますが、キャッシュがどのように構築されるのか、またキャッシュ フレームワークを選択する際にどのような基準を使用すべきかはわかりません。この記事では、キャッシュ、キャッシュ アルゴリズム、キャッシュ フレームワーク、およびどのキャッシュ フレームワークが優れているかについて説明します。

インタビュー

「キャッシュは、元のデータを取得するにはコストがかかりすぎるため、データ（頻繁に使用されるデータ）を一時的に保存して、より速く取得できるようにする場所です。」

これは、プログラマー 1 号 (プログラマー 1 号はインタビュー対象者) がインタビューで答えた内容です (1 か月前、彼はキャッシュ、キャッシュ フレームワーク、大規模データ操作に関する豊富な経験を必要とする Java 開発職に応募したいと、履歴書を会社に提出しました)。

プログラマー 1 はハッシュ テーブルを使用して独自のキャッシュを実装しましたが、彼が知っていたのは、キャッシュと 150 件のレコードを格納するハッシュ テーブルだけで、それが大規模なデータであると考えていました (キャッシュ = ハッシュ テーブル、ハッシュ テーブルで検索するだけで済みます)。それでは、面接プロセスを見てみましょう。

インタビュアー: キャッシュ ソリューションの選択はどのような基準に基づいて行いましたか?

プログラマー 1: えーと、(5 分間考える) えーと、データに基づいて、データに基づいて、データに基づいて (咳払い...)

インタビュアー: 素晴らしいです！もう一度言っていただけますか？

プログラマー1: データ? ！

インタビュアー：わかりました。いくつかのキャッシュアルゴリズムとその機能について説明します

プログラマー 1: (非常に奇妙な表情で面接官を見つめる。人間がそのような表情をすることができるとは誰も知らなかった。)

インタビュアー: では、別の言い方をしましょう。キャッシュの容量がいっぱいになるとどうなるのでしょうか?

プログラマー1: 容量は?うーん（考え中...ハッシュテーブルの容量は無制限なので、エントリを好きなだけ追加でき、容量は自動的に拡張されます）（これはプログラマー1が考えたことですが、口には出しませんでした）

面接官はプログラマー 1 人に礼を言い (面接は 10 分間続きました)、その後、女性がやって来てこう言いました。「お時間をいただきありがとうございました。こちらからお電話いたします。ご機嫌をお取りください。」これはプログラマー 1 にとって最悪の面接でした (彼は、応募者に豊富なキャッシュ経験のバックグラウンドが必要であることを知らず、実際、高額な給与しか見ていなかったのです)。

否や言うほどない

プログラマー 1 が去った後、面接官が尋ねた質問と回答を知りたくなり、オンラインで調べました。プログラマー 1 は、キャッシュが必要な場合はハッシュ テーブルを使用すること以外、キャッシュについて何も知りませんでした。

お気に入りの検索エンジンで検索した後、キャッシュに関する素晴らしい記事を見つけ、読み始めました...

なぜキャッシュが必要なのでしょうか?

はるか昔、キャッシュがなかった頃は、ユーザーはオブジェクトを頻繁にリクエストし、そのオブジェクトはデータベースから取得されていました。すると、オブジェクトはどんどん大きくなり、ユーザーのリクエスト時間は毎回どんどん長くなり、常に動作していたデータベースにも大きな負担がかかっていました。したがって、このインシデントはユーザーとデータベースを非常に怒らせ、次の 2 つのことが起こる可能性があります。

1. ユーザーがイライラしたり、不満を言ったり、アプリの使用をやめたりする（ほとんどの場合、これが起こります）

2. データベースがパックされてアプリケーションを残してホームに戻り、大きな問題（データを保存する場所がない）が発生する（非常にまれなケースで発生します）

神が送ったキャッシュ

数年後、IBM の研究者 (1960 年代) は「キャッシュ」と呼ばれる新しい概念を導入しました。

キャッシュとは何ですか?

冒頭の段落で述べたように、キャッシュとは「元のデータを取得するにはコストがかかりすぎるため、より速く取得できるように、データ（頻繁に使用されるデータ）を一時的に保存する場所」です。

キャッシュは、データベース内の実際のデータからコピーされ、簡単に取得できるようにラベル (キー ID) が付けられたデータのプールと考えることができます。素晴らしい

プログラマー 1 はすでにこれを知っていますが、次のキャッシュ用語についてはまだ知りません。

ヒット数:

クライアントがリクエストを行うと (たとえば、製品情報を表示したい場合)、アプリケーションはそのリクエストを受け取り、キャッシュを初めてチェックする場合は、データベースにアクセスして製品情報を読み取る必要があります。

キャッシュ内にタグ付きのエントリが見つかった場合、そのエントリが使用され、それをキャッシュ ヒットと呼びます。したがって、ヒット率を理解するのは難しくありません。

キャッシュミス:

しかし、ここで注意すべき点が 2 つあります。

1. キャッシュスペースがまだ残っている場合、ヒットしなかったオブジェクトはキャッシュに保存されます。

2. キャッシュがいっぱいでキャッシュヒットがない場合、キャッシュ内の古いオブジェクトは特定の戦略に従って追い出され、新しいオブジェクトがキャッシュプールに追加されます。これらの戦略は総称して置換戦略 (キャッシュ アルゴリズム) と呼ばれ、どのオブジェクトを提案するかを決定します。

保管コスト:

ヒットがない場合は、データベースからデータを取得してキャッシュに格納します。このデータをキャッシュに格納するために必要な時間とスペースがストレージ コストです。

インデックス作成コスト:

ストレージコストと同様です。

無効化:

キャッシュ内のデータを更新する必要がある場合、それはキャッシュ内のデータが無効であることを意味します。

代替戦略:

キャッシュヒットがなく、キャッシュ容量がいっぱいになった場合は、キャッシュ内の古いエントリを追い出し、新しいエントリを追加する必要があります。どのエントリを追い出すかは、置き換え戦略によって決まります。

最善の代替戦略:

最適な置換戦略は、キャッシュ内の最も役に立たないエントリを追い出すことですが、将来を予測することはできないため、この戦略を実装することは不可能です。しかし、この目標に向けて取り組んでいる戦略は数多くあります。

ジャワストリートの悪夢:

プログラマー 1 はこの記事を読んでいるときに眠ってしまい、悪夢を見ました (誰でも時々悪夢を見ます)。

プログラマー 1: ニハハ、君を無効にしてやるよ! （狂気状態）

キャッシュ オブジェクト: いいえ、いいえ、生かしてください。彼らはまだ私を必要としています。私にはまだ子供がいます。

プログラマー 1: すべてのキャッシュ オブジェクトは、無効化される前にそのことを言います。いつから子供を産み始めたのですか？心配しないでください。もう永久に消え去りました!

ハハハハ…プログラマー1はひどく笑いましたが、サイレンが静寂を破りました。警察はプログラマー1を逮捕し、まだ使用する必要のあるキャッシュオブジェクトを殺した（無効にした）として告発しました。彼は刑務所に連行されました。

プログラマー1は突然目が覚め、怖くなって汗をかき、辺りを見回し、それが本当に夢であることに気づき、慌てて記事を読み続け、パニックを解消しようとしました。

プログラマー1は目を覚ました後、再び記事を読み始めました。

キャッシュアルゴリズム

どのキャッシュアルゴリズムが他のキャッシュアルゴリズムよりも優れているかは誰にも分かりません。

最も使用頻度の低いもの (LFU):

みなさんこんにちは。私は LFU です。各キャッシュ オブジェクトがどのくらいの頻度で使用されているかを計算します。最も使用頻度の低いキャッシュされたオブジェクトを削除します。

最も最近使用していないユーザー（LRU）：

私は LRU キャッシュ アルゴリズムを使用して、最近使用されていないキャッシュ オブジェクトを排除します。

いつ、どのキャッシュ オブジェクトが使用されるかを常に把握する必要があります。私がなぜ最近使用されていないオブジェクトを常に排除できるのか理解したい人がいるとしても、それは非常に困難です。

ブラウザはキャッシュ アルゴリズムとして LRU を使用します。新しいオブジェクトはキャッシュの一番上に配置されます。キャッシュが容量制限に達すると、一番下のオブジェクトを追い出します。秘訣は、最近アクセスされたキャッシュされたオブジェクトをキャッシュ プールの一番上に配置することです。

したがって、頻繁に読み取られるキャッシュ オブジェクトは常にキャッシュ プールに残ります。これを実装するには、配列またはリンク リストの 2 つの方法があります。

私は速く、データ アクセス パターンに適応できます。私には大家族がいて、みんな私を褒めてくれて、私よりも上手に物事をやってくれます（時々嫉妬もしますが、それは大丈夫です）。私のファミリーのメンバーには、LRU を完了するために存在する LRU2 と 2Q が含まれています。

最も最近使われていない 2 (LRU2):

私は Least Recently Used 2 です。Least Recently Used Twice と呼ぶ人もいますが、私はこの名前の方が好きです。 2 回アクセスされたオブジェクトをキャッシュ プールに入れます。キャッシュ プールがいっぱいになったら、2 回の使用回数が最も少ないキャッシュ オブジェクトを追い出します。オブジェクトを 2 回追跡する必要があるため、キャッシュ プールが増加するとアクセス負荷が増加します。大きなキャッシュプールで使用すると問題が発生します。さらに、2 度目に読み取られていないためにキャッシュ内になくなったオブジェクトも追跡する必要があります。私はLRUよりも優れており、アクセスモードに適応しています。

2つのキュー（2Q）：

私は 2 つのキューです。アクセスされたデータを LRU キャッシュに格納し、オブジェクトが再度アクセスされた場合は、それを 2 番目のより大きな LRU キャッシュに転送します。

最初のキャッシュ プールを 2 番目のキャッシュ プールの 1/3 に保つために、キャッシュされたオブジェクトを追い出しました。キャッシュのアクセス負荷が固定されている場合、キャッシュ容量を増やすよりも、LRU を LRU2 に置き換える方が効果的です。このメカニズムにより、私は LRU2 よりも優れています。また、私は LRU ファミリーのメンバーであり、アクセス モデルを採用しています。

アダプティブ リプレイスメント キャッシュ (ARC):

私はARCです。LRUとLFUの中間だと言う人もいます。効果を高めるために、私は2つのLRUで構成されています。最初のLRU、つまりL1には、最近1回だけ使用されたエントリが含まれ、2番目のLRU、つまりL2には、最近2回使用されたエントリが含まれます。したがって、L1 には新しいオブジェクトが含まれ、L2 には頻繁に使用されるオブジェクトが含まれます。だから他の人は私が LRU と LFU の間にいると思っているのですが、それは問題ではありませんし、私は気にしません。

これは、最もパフォーマンスの高いキャッシュ アルゴリズムの 1 つと考えられており、自己調整機能があり、負荷が低いです。また、オブジェクトの履歴も保持して、どのオブジェクトが削除されたかを覚えておくことができ、削除されたオブジェクトが残っていて、代わりに何か他のものが削除されたかどうかを確認することもできます。私の記憶力はひどいですが、私は素早いし順応性もあります。

最近使用した項目 (MRU):

私はLRUに対応するMRUです。最近使用したオブジェクトを削除しますが、その理由を尋ねているはずです。まあ、言っておきますが、訪問が来たときに、いくつかのことは予測できず、キャッシュ システム内で最近最も使用されていないオブジェクトを見つけることは非常に時間のかかる操作です。そのため、私が最良の選択なのです。

データベース メモリ キャッシュの使用がどの程度一般的か気になりました。キャッシュ エントリが使用されるたびに、それをスタックの一番上にプッシュします。スタックがいっぱいになったら、どうなると思いますか?スタックの一番上にあるオブジェクトを新しいオブジェクトに置き換えます。

先入れ先出し（FIFO）：

私は先入先出アルゴリズムであり、低負荷アルゴリズムであり、キャッシュ オブジェクトの管理要件は高くありません。キャッシュされたすべてのオブジェクトを追跡するためにキューを使用します。最近使用されたキャッシュされたオブジェクトは後部に配置され、以前にキャッシュされたオブジェクトは前部に配置されます。キャッシュ容量がいっぱいになると、前部のキャッシュされたオブジェクトが追い出され、新しいキャッシュされたオブジェクトが追加されます。速いけど、応用が利かない。

セカンドチャンス:

みなさんこんにちは。私はセカンドチャンスです。私は FIFO から改良されたもので、セカンドチャンス キャッシュ アルゴリズムと呼ばれています。私が FIFO よりも優れているのは、FIFO のコストが改善されたことです。 FIFO のようにキューの先頭を監視していますが、すぐに追い出す FIFO とは異なり、追い出すオブジェクトに以前使用されたフラグ (1 ビットで示される) があるかどうかを確認します。使用されていない場合は追い出します。そうでない場合はこのフラグをクリアしてから、このキャッシュ オブジェクトを新しく追加されたキャッシュ オブジェクトとしてキューに追加します。これをリングキューとして想像することができます。チームのリーダーであるこの人物に再び会ったとき、彼はもうこのマーカーを持っていなかったので、私はすぐに彼を追い払いました。私はFIFOよりも速いです。

クロック：

私はクロックであり、より優れた FIFO であり、セカンドチャンスよりも優れています。セカンドチャンスのようにマークされたキャッシュオブジェクトをキューの最後尾に配置することはありませんが、セカンドチャンスの効果も実現できます。

キャッシュされたオブジェクトの循環リストを維持し、ヘッド ポインターがリスト内の最も古いキャッシュされたオブジェクトを指します。キャッシュ ミスが発生し、新しいキャッシュ スペースがない場合、ポインターが指すキャッシュ オブジェクトのフラグ ビットを参照して、何をすべきかを決定します。フラグが 0 の場合は、キャッシュ オブジェクトを新しいキャッシュ オブジェクトに直接置き換えます。フラグが 1 の場合は、ヘッド ポインターを増分し、新しいキャッシュ オブジェクトを配置できるようになるまでこのプロセスを繰り返します。私は二度目のチャンスよりも速いです。

シンプルな時間ベース:

私は単純な時間ベースのキャッシュ アルゴリズムを使用しており、キャッシュされたオブジェクトを絶対時間期間を通じて無効にします。新しく追加されたオブジェクトについては、特定の時間を保存します。速いけど、応用が利かない。

時間ベースの有効期限の延長:

私は、拡張された時間ベースの有効期限キャッシュ アルゴリズムを使用します。キャッシュされたオブジェクトは相対時間で期限切れになります。新しく追加されたキャッシュされたオブジェクトについては、毎日 5 分ごとや 12 時など、特定の時間に保存します。

スライディング時間ベースの有効期限:

私はスライディング時間ベースの有効期限を使用しています。以前のものとの違いは、管理するキャッシュ オブジェクトの有効期間がこのキャッシュの最終アクセス時間から始まることです。私は速いですが、順応性もあまりありません。

他のキャッシュ アルゴリズムでは、次の点も考慮されます。

コスト: キャッシュされたオブジェクトのコストが異なる場合は、取得が困難なオブジェクトを保存する必要があります。

容量: キャッシュされたオブジェクトのサイズが異なる場合は、より大きなキャッシュされたオブジェクトをクリアして、より小さなキャッシュされたオブジェクトを追加できるようにする必要があります。

時間: 一部のキャッシュでは、キャッシュの有効期限も保存されます。それらは古いため、コンピューターによって無効にされます。

キャッシュされたオブジェクトのサイズによっては、他のキャッシュ アルゴリズムをオーバーライドする必要がある場合があります。

メール！

プログラマー1は、その記事を読んでしばらく考えた後、著者にメールを送ることにしました。著者の名前をどこかで聞いたことがあるような気がしましたが、思い出せませんでした。彼はとにかくメールを送信し、分散環境でのキャッシュの仕組みを著者に尋ねました。

記事の著者がそのメールを受け取りました。皮肉なことに、この著者はプログラマー 1 にインタビューした人物でした。著者は次のように返信しました...

このセクションでは、これらのよく知られたキャッシュ アルゴリズムを実装する方法について説明します。以下のコードは単なる例です。キャッシュ アルゴリズムを自分で実装する場合は、追加の作業が必要になる場合があります。

残されたメカニズム

プログラマー 1 は記事を読んだ後、記事のコメントを読みました。そのコメントの 1 つに、残されたメカニズムであるランダム キャッシュについて言及されていました。

ランダムキャッシュ

私はランダム キャッシャーであり、キャッシュ エンティティをランダムに置き換えますが、誰も文句を言うことはありません。置き換えられたエンティティは不運だったと言えるでしょう。これらのアクションを通じて、エンティティを任意の場所にキャッシュします。私は FIFO よりも優れており、場合によっては LRU よりも優れていますが、通常は LRU の方が私よりも優れています。

今こそコメントの時間です

プログラマー 1 がコメントを読み続けると、非常に興味深いコメントを見つけました。このコメントには、いくつかのキャッシュ アルゴリズムが実装されていました。このコメントには、コメント投稿者の Web サイトへのリンクが張られていました。プログラマー 1 はその Web サイトへのリンクをたどり、読み続けました。

キャッシュ要素（キャッシュエンティティ）を確認する

パブリッククラス CacheElement 
 
 { 
 
プライベートオブジェクトオブジェクト値; 
 
プライベートオブジェクトオブジェクトキー; 
 
プライベートintインデックス; 
 
 privateinthitCount; // ゲッターとセッター  
 
 } 
 
 // このキャッシュ エンティティには、キャッシュされたキーと値があります。このエンティティのデータ構造は、次のすべてのキャッシュ アルゴリズムで使用されます。   
 
 //キャッシュアルゴリズムの共通コード  
 
パブリック最終同期 void addElement(オブジェクトキー、オブジェクト値) 
 
 { 
 
整数インデックス; 
 
オブジェクト obj; 
 
 // テーブルからエントリを取得する  
 
 obj = テーブル.get(キー); 
 
 // テーブルにすでにエントリがある場合  
 
 // 次にそれを取得してその値だけを置き換えます。   
 
 obj = テーブル.get(キー); 
 
 (オブジェクト!= null )の場合
 
 { 
 
 CacheElement 要素; 
 
要素 = (CacheElement)obj; 
 
要素.setObjectValue(値); 
 
要素.setObjectKey(キー); 
 
戻る; 
 
 } 
 
 }

上記のコードは、すべてのキャッシュ アルゴリズムの実装で使用されます。このコードは、キャッシュ要素がすでにキャッシュ内にあるかどうかを確認します。存在する場合は、それを置き換えます。しかし、このキーのキャッシュが見つからない場合はどうなるでしょうか?それでは、何が起こるのか詳しく見てみましょう。

現地訪問

今日のトピックは特別なものです。特別ゲストが来ているからです。実際、私たちが話を聞きたいのは出席者の方々です。まずは、ゲストの Random Cache、FIFO Cache を紹介しましょう。まずはランダムキャッシュから始めましょう。

ランダムキャッシュの実装を見てみましょう

パブリック最終同期 void addElement(オブジェクトキー、オブジェクト値) 
 
 { 
 
整数インデックス; 
 
オブジェクト obj; 
 
 obj = テーブル.get(キー); 
 
 (オブジェクト!= null )の場合
 
 { 
 
 CacheElement 要素; // 値を置き換えるだけです。   
 
要素 = (CacheElement)obj; 
 
要素.setObjectValue(値); 
 
要素.setObjectKey(キー); 
 
戻る; 
 
 } // キャッシュがまだいっぱいになっていない場合は、最後に配置します。   
 
 if (!isFull()) 
 
 { 
 
インデックス = エントリ数; 
 
 ++エントリ数; 
 
 } 
 
 else { // それ以外の場合は、ランダムなエントリを置き換えます。   
 
インデックス = ( int )(cache.length * random.nextFloat()); 
 
テーブルを削除します(キャッシュ[インデックス].getObjectKey()); 
 
 } 
 
キャッシュ[インデックス].setObjectValue(値); 
 
キャッシュ[インデックス].setObjectKey(キー); 
 
 table.put(キー、キャッシュ[インデックス]); 
 
 } 
 
 //FIFOバッファアルゴリズムの実装を見てみましょう  
 
パブリック最終同期 void addElement(オブジェクトキー、オブジェクト値) 
 
 { 
 
整数インデックス; 
 
オブジェクト obj; 
 
 obj = テーブル.get(キー); 
 
 (オブジェクト!= null )の場合
 
 { 
 
 CacheElement 要素; // 値を置き換えるだけです。   
 
要素 = (CacheElement)obj; 
 
要素.setObjectValue(値); 
 
要素.setObjectKey(キー); 
 
戻る; 
 
 } 
 
 // キャッシュがまだいっぱいになっていない場合は、最後に配置します。   
 
 if (!isFull()) 
 
 { 
 
インデックス = エントリ数; 
 
 ++エントリ数; 
 
 } 
 
 else { // それ以外の場合は、現在のポインタを置き換えます。   
 
 // 新しいエントリを追加します。   
 
インデックス = 現在; 
 
 // 循環FIFOを作るために  
 
 (++current >= キャッシュの長さ)の場合
 
電流 = 0 ; 
 
テーブルを削除します(キャッシュ[インデックス].getObjectKey()); 
 
 } 
 
キャッシュ[インデックス].setObjectValue(値); 
 
キャッシュ[インデックス].setObjectKey(キー); 
 
 table.put(キー、キャッシュ[インデックス]); 
 
 }

LFUキャッシュアルゴリズムの実装を見てみましょう

パブリック synchronizedObjectgetElement(オブジェクトキー) 
 
 { 
 
オブジェクト obj; 
 
 obj = テーブル.get(キー); 
 
 (オブジェクト!= null )の場合
 
 { 
 
 CacheElement要素 = (CacheElement)obj; 
 
要素.setHitCount(要素.getHitCount() + 1 ); 
 
戻り値: 
 
 } 
 
 null を返します。 
 
 } 
 
パブリック最終同期 void addElement(オブジェクトキー、オブジェクト値) 
 
 { 
 
オブジェクト obj; 
 
 obj = テーブル.get(キー); 
 
 (オブジェクト!= null )の場合
 
 { 
 
 CacheElement 要素; // 値を置き換えるだけです。   
 
要素 = (CacheElement)obj; 
 
要素.setObjectValue(値); 
 
要素.setObjectKey(キー); 
 
戻る; 
 
 } 
 
 if (!isFull()) 
 
 { 
 
インデックス = エントリ数; 
 
 ++エントリ数; 
 
 } 
 
それ以外  
 
 { 
 
 CacheElement要素 = removeLfuElement(); 
 
インデックス = element.getIndex(); 
 
テーブルを削除します(要素の getObjectKey()); 
 
 } 
 
キャッシュ[インデックス].setObjectValue(値); 
 
キャッシュ[インデックス].setObjectKey(キー); 
 
キャッシュ[インデックス].setIndex(インデックス); 
 
 table.put(キー、キャッシュ[インデックス]); 
 
 } 
 
パブリックキャッシュ要素の削除LfuElement() 
 
 { 
 
 CacheElement[]要素 = getElementsFromTable(); 
 
 CacheElement leastElement = leastHit(要素); 
 
最小要素を返します。 
 
 } 
 
パブリック静的CacheElement leastHit(CacheElement[]elements) 
 
 { 
 
 CacheElement lowestElement = null ; 
 
 (int i = 0 ;i < elements.length;i++)の場合
 
 { 
 
 CacheElement要素 = elements[i]; 
 
最低要素 == nullの場合
 
 { 
 
 lowestElement = 要素; 
 
 } 
 
それ以外{ 
 
 (element.getHitCount() < lowestElement.getHitCount())の場合
 
 { 
 
 lowestElement = 要素; 
 
 } 
 
 } 
 
 } 
 
最低要素を返します。 
 
 }

今日のトピックは特別なものです。特別ゲストが来ているからです。実際、私たちが話を聞きたいのは出席者の方々です。まずは、ゲストの Random Cache、FIFO Cache を紹介しましょう。まずはランダムキャッシュから始めましょう。

最も重要なコードはleastHitメソッドです。このコードは

ヒットカウントが最も低い要素を見つけて削除し、新しいキャッシュ要素のためのスペースを確保します。

LRUキャッシュアルゴリズムの実装を見てみましょう

プライベート void moveToFront(int インデックス) 
 
 { 
 
 int次のインデックス、前のインデックス; 
 
 if (head != インデックス) 
 
 { 
 
 nextIndex = next[インデックス]; 
 
 prevIndex = prev[インデックス]; 
 
 // 先頭にのみ無効なインデックスである前のエントリがあります  
 
 // したがってチェックしません。   
 
次[前のインデックス] = 次のインデックス; 
 
 // インデックスが有効であることを確認します。有効でない場合は末尾です  
 
 // prev[next]を設定しないでください。   
 
 (次のインデックス >= 0 )の場合
 
 prev[次のインデックス] = prevIndex; 
 
それ以外  
 
末尾 = 前インデックス; 
 
前[インデックス] = - 1 ; 
 
次[インデックス] = ヘッド; 
 
 prev[head] = インデックス; 
 
ヘッド = インデックス; 
 
 } 
 
 } 
 
パブリック最終同期 void addElement(オブジェクトキー、オブジェクト値) 
 
 { 
 
 intindex;オブジェクトオブジェクト; 
 
 obj = テーブル.get(キー); 
 
 (オブジェクト!= null )の場合
 
 { 
 
 CacheElement エントリ。 
 
 // 値を置き換えますが、先頭に移動します。   
 
エントリ = (CacheElement)obj; 
 
エントリ.setObjectValue(値); 
 
エントリ.setObjectKey(キー); 
 
エントリを最前面に移動します。 
 
戻る; 
 
 } 
 
 // キャッシュがまだいっぱいになっていない場合は、次の利用可能なキャッシュに置きます  
 
 // スポットして最前線に移動します。   
 
 if (!isFull()) 
 
 { 
 
 _numEntries > 0の場合
 
 { 
 
 prev[_numEntries] = 末尾; 
 
次の[_numEntries] = - 1 ; 
 
エントリ数を最前面に移動します。 
 
 } 
 
 ++エントリ数; 
 
 } 
 
 else { // リストの末尾を置き換えます。   
 
テーブルを削除します(cache[tail].getObjectKey()); 
 
末尾を前方に移動します。 
 
 } 
 
キャッシュ[head].setObjectValue(値); 
 
キャッシュ[head].setObjectKey(キー); 
 
テーブルにキーを格納します。 
 
 }

このコードのロジックは、LRU アルゴリズムの説明と同じです。再度使用されるキャッシュを先頭に抽出し、そのたびに最後の要素を削除します。

結論は

LFU キャッシュ アルゴリズムと LRU キャッシュ アルゴリズムの実装方法を見てきました。実装方法については、配列を使用するか LinkedHashMap を使用するかは自由ですが、私は通常、キャッシュ容量が小さい場合は配列を使用し、大きい場合は LinkedHashMap を使用します。