Golang LRU-Implementierung

Der LRU-Algorithmus (Least Recent Used) ist eine gängige Strategie zum Ersetzen des Caches. Wenn der Cache das voreingestellte Limit erreicht, löscht der Cache automatisch die zuletzt verwendeten Daten, um Speicherplatz freizugeben.

In Golang können wir doppelt verknüpfte Listen und Hash-Tabellen verwenden, um den LRU-Cache zu implementieren. In diesem Artikel beschreiben wir, wie Sie mithilfe dieser beiden Datenstrukturen einen LRU-Cache implementieren.

Die Funktion der doppelt verknüpften Liste besteht darin, die zwischengespeicherte Datenreihenfolge beizubehalten. Jedes Mal, wenn neue Daten eingefügt werden oder auf Daten zugegriffen wird, werden die Daten erweitert. Wenn der Cache die Obergrenze erreicht, können wir gleichzeitig die zuletzt verwendeten Daten vom Ende der verknüpften Liste löschen.

Die Funktion der Hash-Tabelle besteht darin, die Datensuche zu beschleunigen. Bei jedem Zugriff auf Daten können wir die entsprechenden zwischengespeicherten Daten über den in der Hash-Tabelle gespeicherten Datenindex schnell finden. Daher werden wir während der Implementierung mit Hash-Tabellen arbeiten.

Als nächstes erklären wir, wie man den LRU-Cache basierend auf doppelt verknüpften Listen und Hash-Tabellen implementiert. Wir definieren eine LRUCache-Struktur und deklarieren die Kopf- und Endzeiger der verknüpften Liste sowie die Hash-Tabellenzuordnung und die Cache-Kapazität.

type LRUCache struct {
    head, tail *entry  // 链表头和链表尾指针
    cache      map[int]*entry  // 哈希表存储缓存中的数据
    capacity   int     // 缓存容量
}

Als nächstes definieren wir die Struktur des doppelt verknüpften Listenknotens.

type entry struct {
    key, value int        // 存储节点的键值对
    prev, next *entry    // 前驱和后继指针
}

Hier verwenden wir prev und next, um die Vorgänger- bzw. Nachfolgerzeiger des Knotens darzustellen, und Schlüssel und Wert repräsentieren jeweils das Schlüssel-Wert-Paar des Knotens.

Als nächstes definieren wir den Konstruktor NewLRUCache von LRUCache und übergeben die Cache-Kapazität.

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        cache:    make(map[int]*entry),
        capacity: capacity,
    }
}

Im Konstruktor initialisieren wir die Hash-Tabelle und die Cache-Kapazität.

Als nächstes definieren wir die Get- und Put-Methoden von LRUCache, um auf Daten zuzugreifen und diese zu speichern.

Implementierung der Get-Methode:

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        // 更新节点位置
        c.moveToHead(elem)
        return elem.value
    }
    return -1
}

Zunächst ermitteln wir, ob die entsprechenden Daten aus der Hash-Tabelle vorhanden sind. Wenn vorhanden, verschieben wir den Knoten an den Kopf der verknüpften Liste und gibt den vom Knoten gespeicherten Wert zurück. Andernfalls wird -1 zurückgegeben.

Das Folgende ist die Implementierung der moveToHead-Methode:

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
}

Diese Methode empfängt ein Knotenzeigerelement, das verwendet wird, um den Knoten an den Kopf der verknüpften Liste zu verschieben. Wenn sich der Knoten bereits am Anfang der verknüpften Liste befindet, kehren Sie zurück. Andernfalls aktualisieren Sie den Endzeiger der verknüpften Liste, andernfalls löschen Sie den Knoten aus der verknüpften Liste Platzieren Sie den Knoten an der Spitze der verknüpften Liste.

Put-Methodenimplementierung:

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
        }
    }
}

Zunächst ermitteln wir aus der Hash-Tabelle, ob die entsprechenden Daten vorhanden sind. Wenn vorhanden, aktualisieren Sie den im Knoten gespeicherten Wert und rufen die Methode moveToHead auf Verschiebt den Knoten an den Kopf der verknüpften Liste. Andernfalls erstellen Sie einen neuen Knoten und fügen ihn am Kopf der verknüpften Liste ein. Wenn der Cache die voreingestellte Obergrenze erreicht, löschen Sie den Endknoten der verknüpften Liste und die Daten in der Hash-Tabelle.

Schließlich haben wir den vollständigen Code zusammengestellt:

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
        }
    }
}

In diesem Artikel haben wir vorgestellt, wie man doppelt verknüpfte Listen und Hash-Tabellen verwendet, um den LRU-Cache-Algorithmus zu implementieren. Durch die Implementierung dieses Algorithmus können wir den Cache effektiv verwalten und die Effizienz des Datenzugriffs optimieren.

Das obige ist der detaillierte Inhalt vonGolang LRU-Implementierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!