1

Enthuware 試験シミュレーターからいくつかのサンプル問題を読んでいました。問題文がこのような質問に出くわしました

オブジェクトをキャッシュするクラスを設計しています。オブジェクト識別子が提供されると、オブジェクトを格納および取得できる必要があります。さらに、このクラスは、オブジェクトの「最終アクセス時刻」を追跡することによって機能する必要があります。したがって、その容量がいっぱいの場合、最も長くアクセスされていないオブジェクトのみを削除する必要があります。

オブジェクトを格納するためにどのコレクション クラスを使用しますか?

与えられた可能なオプションは

  1. ハッシュセット
  2. 配列リスト
  3. LinkedHashMap
  4. リンクされたリスト
  5. ツリーマップ

シミュレーターの正解は LinkedHashMap です。シミュレーターによる説明を引用します。

LinkedHashMap クラスは、要素を挿入時間順に維持します。このプロパティを使用して、次のように必要なキャッシュを構築できます。

  1. 通常どおりにキーと値のペアを挿入します。ここで、key はオブジェクト識別子、value はキャッシュされるオブジェクトです。

  2. キーが要求されたら、それを LinkedHashMap から削除してから、再度挿入します。これにより、このペアが最後に挿入されたものとしてマークされます。

  3. 容量がいっぱいの場合は、最初の要素を削除します。

再挿入操作はペアの位置に影響を与えないため、キー値を (最初に削除せずに) 単純に再度挿入することはできないことに注意してください。

私は最初の点だけを理解しています。それでも、次の質問があります。

  1. ポイント1では、値はキャッシュされるオブジェクトになりますか? キャッシングはこのようにどのように適用されますか?
  2. ポイント2以降は理解できません。

誰かが私にこの概念を説明できますか? ありがとう。

4

5 に答える 5

4

この例の「キャッシング」は、一粒の塩で理解する必要があると思います。これは、何らかのコンテキストを提供することを目的としていますが、完全に関連しているわけではありません。

ここでのキャッシングは、データ ソースにアクセスしてそこから値を取得するのではなく、コレクションから値を取得することを意味している可能性があります。

2番目の質問について：

キーが要求されたら、それを LinkedHashMap から削除してから、再度挿入します。これにより、このペアが最後に挿入されたものとしてマークされます。

次のマップを検討してください。

ID | 値
1 | ジャック
5 | ジョン
3 | ジェニー

この状況Jackでは、最初に入力され、次に入力さJohnれましたJenny。のキャッシュされた値を取得しますJohn。そうする場合は、最初に彼の一意の識別子 ( ) の値を取得し、結果として5オブジェクトを取得します。John現在、キャッシュされた値がありますが、最終アクセス時刻を追跡する要件はまだ満たされていません。したがって、彼を削除して再度追加し、基本的に最後に配置します。

ID | 値
1 | ジャック
3 | ジェニー
5 | ジョン

John はキャッシュされたままですが、アクセス時間が更新されました。マップがいっぱいになるたびに、列の最初のアイテム (基本的には、最も長い間アクセスされていないアイテム) を削除します。

マップの最大サイズが で3、 を追加しようとするとJeff、次のような状況になります。

ID | 値
3 | ジェニー
5 | ジョン
7 | ジェフ

最初のアイテム ( Jack) と、最後にアクセスされたオブジェクトが削除され、新しいオブジェクト (最近アクセスされたオブジェクト) が配置されます。

于 2013-08-25T13:25:36.927 に答える
2

ポイント1では、値はキャッシュされるオブジェクトになりますか? キャッシングはこのようにどのように適用されますか?

ここでのオブジェクトのキャッシュとは、作成されたオブジェクトを一部のコレクションに格納して、後で取得できるようにすることを意味します。要件はオブジェクトのキーを使用してオブジェクトを保存および取得することであるため、ここでは明らかに aがオプションであり、オブジェクトからそれ自体へMapのマッピングを保存します。Keyobject

また、LinkedHashMap掲載順を維持するので適しています。したがって、作成する最初のオブジェクトは、そのマップの最初になります。

キーが要求されたら、それを LinkedHashMap から削除してから、再度挿入します。これにより、このペアが最後に挿入されたものとしてマークされます。

もう一度、要件を確認してください。それは、長い間アクセスされていない要素を削除する必要があることを示しています。ここで、最初の位置にあるオブジェクトが長い間アクセスされていないとします。そのため、今アクセスしたときにまだ最初の位置にいることは望ましくありません。その場合、最初の要素を削除すると、アクセスしたばかりの要素が削除されるからです。

そのため、要素を削除して挿入し直して、最後に配置する必要があります。

容量がいっぱいの場合は、最初の要素を削除します。

すでに明らかなように、最初の要素は最初に挿入された要素であり、アクセス時間が最も古い要素です。したがって、要件にあるように、最初の要素のみを削除する必要があります。

その容量がいっぱいの場合、最も長くアクセスされていないオブジェクトのみを削除する必要があります。

于 2013-08-25T13:24:25.230 に答える
1

彼らは次の 3 つの非常に重要な点を省略しています。

  1. とともに、LinkedHashMapオブジェクトの削除をいつ開始するかを決定するメカニズムが必要です。最も単純なものはavailableCapacity、最大容量に初期化され、それに応じてデクリメント/インクリメントされるカウンターです。size()別の方法は、 のLinkedHashMapをmaximumCapacity変数と比較することです。
  2. (LinkedHashMap具体的にはそのvalues()) には、キャッシュされたオブジェクト/構造体へのポインターのみが含まれていると想定されます。他のポインタが保持されている場合、それらは一時的であると見なされます。
  3. キャッシュは、LRU 体制の下で管理されます。

これは言った、そしてあなたの質問に答えるために：

  1. はい。
  2. 定義上、firstLinkedHashMap 内のアイテムは最初に挿入されたもの (「最も古い」) です。キャッシュ エントリが使用されるたびに削除され、マップに再挿入されると、リストの最後に配置されて「最新」になります。 first常に最も長く使用されていないものになります。「2番目」は次のようになります。これが、正面からの要素が削除される理由です。
于 2013-08-25T13:46:16.377 に答える
0

LinkedHashMap は、アイテムが挿入された順に格納します。彼らは、LRU キャッシュを実装するために 1 つを使用しています。キーはオブジェクト識別子です。値は、キャッシュされる項目です。マップのルックアップ時間は非常に高速であり、これがマップをキャッシュにします。ルックアップを実行する方が高速です

アイテムをマップに挿入すると、マップの最後に配置されます。そのため、何かを読むたびに、それを取り出して最後に戻します。次に、キャッシュにさらにスペースが必要な場合は、最初の要素を切り取ります。それはずっと前に進んだので、最も長い間使用されていないものです。

于 2013-08-25T13:24:28.917 に答える