golang lru實現

LRU（Least Recently Used）演算法是一種常見的快取替換策略。當快取達到預設上限時，快取會自動淘汰最近最少使用的數據，以釋放空間。

在 Golang 中，我們可以使用雙向鍊錶和雜湊表來實作 LRU 快取。在本文中，我們將介紹如何使用這兩種資料結構實作 LRU 快取。

雙向鍊錶的作用在於維護快取的資料順序，每次插入新資料或存取資料時，都會提前此資料。同時，在快取達到上限時，我們可以從鍊錶的末端刪除最近最少使用的資料。

雜湊表的作用在於加速資料的查找，每次進行資料存取時，透過雜湊表中儲存的資料索引，我們可以快速地查找到對應的快取資料。因此，我們將在實作過程中對哈希表進行操作。

接下來，我們將講解如何實作基於雙向鍊錶和雜湊表的 LRU 快取。我們定義一個 LRUCache 結構體，並宣告鍊錶頭和鍊錶尾指針，以及哈希表 map 和快取容量 capacity。

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
}

此方法接收一個節點指標 elem，用於將該節點移到鍊錶頭部。首先，如果該節點已經是鍊錶頭部，則返回；否則，如果該節點是鍊錶尾部，則更新鍊錶尾部指標 tail；否則，將該節點從鍊錶中刪除，並將該節點放置到鍊錶頭部。

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中文網其他相關文章！