LRU (最も最近使用されていない) アルゴリズムは、一般的なキャッシュ置換戦略です。キャッシュが事前に設定された制限に達すると、キャッシュは最も最近使用されていないデータを自動的に削除して、スペースを解放します。
Golang では、二重リンク リストとハッシュ テーブルを使用して LRU キャッシュを実装できます。この記事では、これら 2 つのデータ構造を使用して LRU キャッシュを実装する方法について説明します。
二重リンク リストの機能は、キャッシュされたデータの順序を維持することであり、新しいデータが挿入されるか、データにアクセスされるたびに、データは進みます。同時に、キャッシュが上限に達した場合、リンクされたリストの最後から最も最近使用されていないデータを削除できます。
ハッシュ テーブルの機能は、データの検索を高速化することです。データにアクセスするたびに、ハッシュ テーブルに格納されているデータ インデックスを通じて、対応するキャッシュされたデータを迅速に見つけることができます。したがって、実装時にはハッシュ テーブルを操作します。
次に、二重リンクリストとハッシュテーブルに基づいたLRUキャッシュの実装方法について説明します。 LRUCache 構造を定義し、リンク リストの先頭ポインタと末尾ポインタ、およびハッシュ テーブル マップとキャッシュ容量を宣言します。
type LRUCache struct {
head, tail *entry // 链表头和链表尾指针
cache map[int]*entry // 哈希表存储缓存中的数据
capacity int // 缓存容量
}次に、二重リンクリストノードの構造を定義します。
type entry struct {
key, value int // 存储节点的键值对
prev, next *entry // 前驱和后继指针
}ここでは、prev と next を使用してそれぞれノードの先行ポインタと後続ポインタを表し、key と value はそれぞれノードのキーと値のペアを表します。
次に、LRUCacheのコンストラクターNewLRUCacheを定義し、キャッシュ容量capacityを渡します。
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{
cache: make(map[int]*entry),
capacity: capacity,
}
}コンストラクターでは、ハッシュテーブルとキャッシュ容量を初期化します。
次に、データにアクセスして保存するための LRUCache の Get メソッドと Put メソッドを定義します。
Getメソッドの実装:
func (c *LRUCache) Get(key int) int {
if elem, ok := c.cache[key]; ok {
// 更新节点位置
c.moveToHead(elem)
return elem.value
}
return -1
}まず、ハッシュテーブルから該当するデータが存在するかどうかを調べ、存在する場合は、そのノードを連結リストの先頭に移動し、そのノードを返します。保管価値。それ以外の場合は、-1 が返されます。
次は、moveToHead メソッドの実装です。
func (c *LRUCache) moveToHead(elem *entry) {
if elem == c.head {
return
} else if elem == c.tail {
c.tail = elem.prev
} else {
elem.prev.next = elem.next
elem.next.prev = elem.prev
}
elem.prev = nil
elem.next = c.head
c.head.prev = elem
c.head = elem
}このメソッドは、ノードをリンク リストの先頭に移動するために使用されるノード ポインター要素を受け取ります。まず、ノードがすでにリンク リストの先頭にある場合は戻り、ノードがリンク リストの末尾にある場合は、リンク リストの末尾ポインタを更新します。そうでない場合は、リンク リストからノードを削除し、ノードをリンクされたリストの先頭に置きます。
Put メソッドの実装:
func (c *LRUCache) Put(key, value int) {
if elem, ok := c.cache[key]; ok {
elem.value = value
c.moveToHead(elem)
} else {
// 创建新节点
elem := &entry{key: key, value: value}
c.cache[key] = elem
if c.head == nil {
c.head = elem
c.tail = elem
} else {
// 在链表头部插入新节点
elem.next = c.head
c.head.prev = elem
c.head = elem
}
// 判断缓存是否达到预设上限
if len(c.cache) > c.capacity {
// 删除链表尾部节点和哈希表中的数据
delete(c.cache, c.tail.key)
c.tail = c.tail.prev
c.tail.next = nil
}
}
}まず、ハッシュ テーブルから該当するデータが存在するかどうかを確認し、存在する場合はノードに格納されている値を更新し、moveToHead メソッドを呼び出します。ノードの移動 リンクされたリストの先頭に移動します。それ以外の場合は、新しいノードを作成し、リンクされたリストの先頭に挿入します。キャッシュがあらかじめ設定した上限に達した場合は、リンクリストの末尾ノードとハッシュテーブルのデータを削除します。
最後に、完全なコードをまとめました:
type LRUCache struct {
head, tail *entry
cache map[int]*entry
capacity int
}
type entry struct {
key, value int
prev, next *entry
}
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{
cache: make(map[int]*entry),
capacity: capacity,
}
}
func (c *LRUCache) Get(key int) int {
if elem, ok := c.cache[key]; ok {
// 更新节点位置
c.moveToHead(elem)
return elem.value
}
return -1
}
func (c *LRUCache) moveToHead(elem *entry) {
if elem == c.head {
return
} else if elem == c.tail {
c.tail = elem.prev
} else {
elem.prev.next = elem.next
elem.next.prev = elem.prev
}
elem.prev = nil
elem.next = c.head
c.head.prev = elem
c.head = elem
}
func (c *LRUCache) Put(key, value int) {
if elem, ok := c.cache[key]; ok {
elem.value = value
c.moveToHead(elem)
} else {
// 创建新节点
elem := &entry{key: key, value: value}
c.cache[key] = elem
if c.head == nil {
c.head = elem
c.tail = elem
} else {
// 在链表头部插入新节点
elem.next = c.head
c.head.prev = elem
c.head = elem
}
// 判断缓存是否达到预设上限
if len(c.cache) > c.capacity {
// 删除链表尾部节点和哈希表中的数据
delete(c.cache, c.tail.key)
c.tail = c.tail.prev
c.tail.next = nil
}
}
}この記事では、二重リンク リストとハッシュ テーブルを使用して LRU キャッシュ アルゴリズムを実装する方法を紹介しました。このアルゴリズムの実装により、キャッシュを効果的に管理し、データ アクセス効率を最適化できます。
以上がgolang lruの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
