回答について質問があります。
ハッシュ マップがいっぱいだとします (インタビュアーが最大サイズを教えてくれました) [マップに既に存在するペアを取得する必要がある場合は、最近使用したことを示すためにリスト エントリを先頭に移動します。]
しかし、追加するエントリがあり、このキーが別のキーと同じ位置にハッシュされるとどうなりますか。(衝突) どうすればいいの？
チェーニングまたはプロービングを行いますか? チェーンを行う場合、マップ サイズを大きくする必要がありますか? 最も古いエントリを削除すると、ハッシュ マップ内の場所が空になります。しかし、新しいエントリはこの場所にハッシュされない可能性がありますか? 別の完全なエントリにハッシュされる可能性がありますか? (異なるキー、値のペア) これを解決するにはどうすればよいですか?
ここではダイレクト マップ キャッシュを設計しており、ダイレクト マップ キャッシュはキャッシュからエントリを削除する前にエントリの最新性のみを考慮し、要求される頻度は考慮しないというトレードオフが知られているため、この設計には連鎖が含まれません。
リンク リストのサイズには最大サイズ制限が課され、リンク リストがいっぱいのときに新しいエントリを追加しようとするたびに、(リンク リストの) 最後に使用されたエントリと対応するマップ エントリが削除されます。新しいエントリが挿入される場所は、削除されたものとは無関係です。
同時実行の詳細については、このリンクを確認してください。
マップのサイズはマップに存在するキーと値のペアの数であるため、キーと値のペアが同じハッシュ バケットに存在するかどうかとは関係ありません。
したがって、ハッシュマップのデータ構造をチェックすると、リンクリストの配列になるため、ハッシュの衝突があるとチェーンが発生し、マップのサイズも大きくなります。
新しいエントリが null ではない場所にハッシュされる場合は、リンクリストで行っているようにチェーンする必要があります。
PS: LRU キャッシュについては、LinkedHashMapを確認できます