LinkedHashMapは、Java 1.4で導入されたデータ構造で、HashMapのO(1)の平均検索時間と、挿入順序またはアクセス順序を持つ確定的な反復順序を提供する二重リンクリストを組み合わせたハイブリッドデータ構造です。この設計により、removeEldestEntryテンプレートメソッドが導入され、サブクラスが希望するサイズを超えたときにtrueを返すことでLRU（Least Recently Used）追放ポリシーを実装できるようになりました。しかし、この実装は同時使用を意図していなかったため、HashMapの非スレッドセーフな特性を継承し、すべてのエントリ間で双方向のbeforeおよびafterポインタを維持するという複雑さを追加しました。
同時構造変更が行われるとき、たとえば一つのスレッドが挿入し、他のスレッドが削除またはサイズ変更を行う場合、リンクリストのポインタが非原子的に更新され、エントリが循環参照を形成したり、メインチェーンから孤立したりする腐敗したグラフ構造が生じます。たとえば、スレッドAがエントリのafterポインタをエントリBを指すように更新しているときに、スレッドBがエントリBを削除し、そのbeforeポインタを同時に更新した場合、リストはAがBを指し、BがCを指す状態になり、Aをスキップしたりサイクルを作成したりします。この腐敗により、イテレータは無限にスピンし（CPUを100%消費）、有効なエントリを静かにスキップすることになり、removeEldestEntryポリシーが信頼できないものになります。なぜなら、"eldest"ポインタがリストの真の先頭を反映しなくなるためです。
マルチスレッドの文脈でLinkedHashMapを安全に使用するには、すべての操作を外部で同期させる必要があります。accessOrder=trueのキャッシュでは、get()も構造的変更を伴う（リンクリストの順序を変更するため）ため、標準のReadWriteLock最適化は無効になります。すべての操作を書き込みとして扱うか、グローバルミューテックスを使用する必要があります。最も安全なアプローチはCollections.synchronizedMapですが、反復操作時にはマップに手動で同期を取る必要があります。しかし、商業システムでは、LinkedHashMapをCaffeineやGuavaのCacheBuilderに置き換えるべきです。これらはロックストライプまたは完全に同時の追放アルゴリズムを提供し、グローバルコンテンションなしに動作します。
public class SafeLRUCache<K, V> { private final Map<K, V> map; public SafeLRUCache(int maxSize) { // LinkedHashMapはスレッドセーフではありません; 外部で同期してください this.map = Collections.synchronizedMap(new LinkedHashMap<>(16, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxSize; } }); } // すべてのメソッドはマップで同期を取る必要があります public V get(K key) { synchronized (map) { return map.get(key); } } public void put(K key, V value) { synchronized (map) { map.put(key, value); } } // 反復には明示的な同期が必要です public void forEach(BiConsumer<K, V> action) { synchronized (map) { map.forEach(action); } } }
電子商取引プラットフォームのバックエンドサービスは、データベースの負荷を軽減するために製品価格データのインメモリキャッシュを必要としていました。最初の実装は、accessOrder=trueのLinkedHashMapを使用し、1,000件のアイテム制限を強制するためにremoveEldestEntryをオーバーライドして、マップが古いエントリを自動的に削除すると仮定しました。低負荷試験の間、これは正しく機能しました。しかし、40の同時スレッドがフラッシュセールを処理する生産トラフィックのもとで、このサービスは断続的にCPU負荷が100%に達し、最終的にはスレッドのスタベーションが発生しました。
スレッドダンプは、複数のスレッドがLinkedHashMapイテレータ内にスタックし、同時変更によって生じた二重リンクリスト内の循環参照を移動していることを明らかにしました。具体的には、あるスレッドが内部テーブルのサイズを変更している間に、別のスレッドがエントリのアクセス順序を更新していたため、Entryノードのafterポインタが自分自身を参照するようになり、反復中に無限ループが発生しました。さらに、removeEldestEntryコールバックは、"eldest"ポインタが同時の再構成によって破損してしまったために、時折誤ったエントリを削除する結果となり、最近アクセスされたアイテムが古いものの代わりに追放されるキャッシュアボリションがありました。
チームは最初にマップをCollections.synchronizedMapでラッピングすることを検討しました。 利点: これは最小限のコード変更で済み、synchronizedメソッドでラップすることで個々の操作の原子性を確保します。 欠点: それはグローバルなモニタを導入し、すべての読み書きを直列化し、期待される20,000オペレーション/秒から3000未満にスループットを低下させました。さらに、イテレータはまだ明示的なsynchronized(map)ブロックが必要で、開発者が時折それを忘れ、ConcurrentModificationExceptionにつながることがありました。
次に、彼らはConcurrentHashMapとConcurrentLinkedQueueを使用して、アクセスの新しさを追跡し、バックグラウンドのクリーンスレッドを評価しました。 利点: これは読み書きの高い同時処理を提供します。 欠点: LRUを正しく実装することはエラーを引き起こしやすいです。古いエントリを削除することは挿入と原子的ではないため、キャッシュが高負荷時にサイズ制限を一時的に大幅に超える可能性があります。さらに、各get()呼び出しでキューを更新するには書き込み操作が必要で、キューとマップの間の一貫性を維持する複雑さと同様にコンテンションポイントを作成しました。
最後に、彼らは高性能キャッチライブラリのCaffeineのベンチマークを実施しました。 利点: これはロックストライピングと追放のための書き込みバッファを備えたBoundedLocalCacheを使用し、ロックなしでの同時読み取りと高スループットの書き込みを可能にします。LRU/W-TinyLFUの追放を明示的な同期なしで原子的に処理します。 欠点: これは外部依存関係を追加し、新しいAPI（例：CacheLoader）を学ぶ必要があります。
チームは、負荷試験でCaffeineが80,000以上のオペレーションを1秒あたり持続し、p99レイテンシが1ms未満であることが示され、一方で同期されたLinkedHashMapが5k ops/secでボトルネックを作り、p99が500msに達することを確認した後、Caffeineを選定しました。マップをCaffeine.newBuilder().maximumSize(1000).build()で置き換え、クリーンアップロジックのために削除リスナーを登録するという移行が行われました。
デプロイ後のモニタリングは、安定したCPU使用率とスレッドのハングがないことを示しました。キャッシュのヒット率は85%から94%に向上し、追放が決定論的かつ競合のないものとなりました。この事件は、LinkedHashMapがその便利なAPIにもかかわらず、同時LRUキャッシュに不適切な単一スレッドデータ構造であることを浮き彫りにしました。
高いハッシュ衝突のためにツリー化バケット（赤黒木）に移動されたエントリのLRU順序をLinkedHashMapはどのように維持していますか？
LinkedHashMapは、HashMap.Nodeを拡張する特殊な内包クラスEntryを使用し、beforeおよびafterポインタを含んでいます。バケットがツリー化されると、LinkedHashMapはnewTreeNodeをオーバーライドしてTreeNodeインスタンスを作成し、それでもLinkedHashMap.Entry（経由してLinkedHashMap.TreeNode）から継承されます。その結果、エントリがO(log n)の衝突解決のためにツリー構造で保管されている場合でも、グローバルな二重リンクリストのノードのままです。afterNodeAccessメソッドは、すべてのアクセス後にこれらのポインタを更新し、LRUチェーンがエントリを横断できるようにします。
accessOrder=trueのLinkedHashMapでのget()を呼び出すと、反復中に実行される場合にConcurrentModificationExceptionが発生するのはなぜですか？同じ操作が標準のHashMapでは発生しないのですか？
accessOrderモードでは、LinkedHashMapはget()を構造的変更として扱います。なぜなら、アクセスされたエントリを二重リンクリストの末尾に移動させるためにmodCountが増加するからです。フェイルファーストイテレータはこのカウンタを確認し、変更を検出するとすぐにスローします。それに対して、標準のHashMapは挿入、削除、サイズ変更でのみmodCountを増加させるため、get()はテーブル構造に対して読み取り専用です。この違いにより、「読み取り専用」の論理操作であっても、LinkedHashMapでイテレータを無効にする可能性があるため、同時反復時に読み込みを含むすべての操作に対して同期が必要です。
標準のHashMapでは不可能な、LinkedHashMapにおける同時サイズ変更（リハッシュ）中の特定のポインタの破損は何ですか？
サイズ変更の際、HashMapはノードを新しいテーブル配列に転送し、同時に行うとバケット内で無限ループのリスクがあります。LinkedHashMapは、補助的なリンクリストを形成するbeforeおよびafterポインタの破損リスクもあります。もしスレッドAが新しいテーブルで順序を保つためにエントリを再リンクしている間に、スレッドBがリストを変更している場合（例としてremove）、スレッドAはすでにunlinkされた後続エントリにリンクしてしまうかもしれず、ダングリング参照やサイクルを作成します。具体的には、ヘッダノードのafterポインタが別のスレッドによってヌルにされたエントリを指す可能性があり、リストの不変条件を破り、next()が壊れたチェーンを追うとイテレータが永遠にスピンすることになります。