連結ハッシュマップ（Linked HashMap）とは
連結ハッシュマップ（Linked HashMap）とは、
です。
通常のHashMapではキーと値のペアを格納できますが、データの挿入順序は保持できません。
連結ハッシュマップでは、Linked Listを使うことで挿入順序を保持を行います。
連結ハッシュマップの性能
HashMapを使用したデータ構造なので、高速に操作することができます。
メモリの消費については、各エントリに対して追加のポインタが必要となるのでHashMapよりも若干大きくなります。
連結ハッシュマップの用途
連結ハッシュマップ(LinkedHashMap)は、挿入順序やアクセス順序が重要な場合に適しています。
たとえば、LRUキャッシュの実装やログの記録などで使用されます。
ただし、頻繁な再順序化が必要な場合は、TreeMapの方が適しています。
LRUキャッシュとは、
です。
最近使ったものはキャッシュに乗っているので高速にアクセスすることができ、使っていないものは削除されてしまうのでキャッシュ外から自力で探す必要が出てきます。
実装(Python)
挿入順を保持するLinkedHashMapは、OrderedDictを使うことで簡単に実装する事ができます。
from collections import OrderedDict
# OrderedDictを使用して挿入順序を保持
linked_hash_map = OrderedDict()
# 要素の挿入
linked_hash_map["Banana"] = "黄"
linked_hash_map["Apple"] = "赤"
linked_hash_map["Orange"] = "橙"
# 要素にアクセス
print(linked_hash_map["Apple"]) # 1
# 挿入順で出力
print("挿入順序:", linked_hash_map)赤
挿入順序: OrderedDict({'Banana': '黄', 'Apple': '赤', 'Orange': '橙'})
参照順を保持したい場合は、OrderedDictにアクセス時の処理を追記する必要があります。
以下では、LRUの実装を記載します。
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
# 使用されたキーを末尾に移動（最近使用されたものとしてマーク）
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
# 既存のキーを更新して末尾に移動
self.cache.move_to_end(key)
self.cache[key] = value
# キャッシュの容量を超えた場合、最も古い項目（先頭）を削除
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
# 使用例
cache = LRUCache(3)
# 要素の追加
cache.put("banana", "黄")
cache.put("apple", "赤")
print(cache.cache)
# 要素へのアクセス
print(cache.get("banana"))
print(cache.cache)
# 新しい要素の追加
cache.put("orange", "橙")
print(cache.cache)
# キャッシュの容量を超える要素の追加
cache.put("cherry", "赤")
print(cache.cache)OrderedDict({'banana': '黄', 'apple': '赤'})
黄
OrderedDict({'apple': '赤', 'banana': '黄'})
OrderedDict({'apple': '赤', 'banana': '黄', 'orange': '橙'})
OrderedDict({'banana': '黄', 'orange': '橙', 'cherry': '赤'})
コメント