设计LRU缓存结构

1. 题目描述

设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能

• set(key, value)：将记录(key, value)插入该结构
• get(key)：返回key对应的value值

2. 思路

• map+双向链表

3. 实现

3.1. Golang

3.1.1. map+list

package main

import (
	"container/list"
)

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
 */

type data struct {
	key   int
	value int
}

type LruCache struct {
	eList    *list.List
	eMap     map[int]*list.Element
	capacity int
}

func NewLruCache(capacity int) *LruCache {
	return &LruCache{
		eList:    list.New(),
		eMap:     make(map[int]*list.Element, 0),
		capacity: capacity,
	}
}

func (l *LruCache) Set(key int, value int) {

	//已存在但不是头节点
	element, ok := l.eMap[key]
	if ok {
		element.Value.(*data).value = value
		l.eList.MoveToFront(element)
		return
	}

	//不存在并且已满
	if l.isFull() {
		lastElement := l.eList.Back()
		//删除尾节点
		l.eList.Remove(lastElement)
		//清理map
		delete(l.eMap, lastElement.Value.(*data).key)
	}

	//不存在并且未满
	element = l.eList.PushFront(&data{
		key:   key,
		value: value,
	})
	l.eMap[key] = element
}

func (l *LruCache) isFull() bool {
	return len(l.eMap) == l.capacity
}

func (l *LruCache) Get(key int) int {
	element, ok := l.eMap[key]
	if !ok {
		return -1
	}

	l.eList.MoveToFront(element)
	return element.Value.(*data).value
}

func LRU(operators [][]int, k int) []int {

	res := make([]int, 0)
	cache := NewLruCache(k)
	for _, operator := range operators {
		switch operator[0] {
		case 1:
			cache.Set(operator[1], operator[2])
		case 2:
			val := cache.Get(operator[1])
			res = append(res, val)
		}
	}

	return res
}

3.1.2. map+slice

type node struct {
	key   int
	value int
}

type LRUCache struct {
	m        map[int]*node
	lst      []*node
	capacity int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		m:        make(map[int]*node, 0),
		lst:      make([]*node, 0),
		capacity: capacity,
	}
}

func (this *LRUCache) Get(key int) int {
	n, ok := this.m[key]
	if !ok {
		return -1
	}

	// 存在那么把node移动到链表头部
	this.moveToHead(key)
	return n.value
}

func (this *LRUCache) moveToHead(key int) {
	var movedNode *node
	var movedIndex int
	for i, n := range this.lst {
		if n.key == key {
			movedNode = n
			movedIndex = i
			break
		}
	}

	newList := append([]*node{movedNode}, this.lst[:movedIndex]...)
	newList = append(newList, this.lst[movedIndex+1:]...)
	this.lst = newList
}

func (this *LRUCache) Put(key int, value int) {
	n, ok := this.m[key]
	if ok {
		n.value = value
		// 存在那么把node移动到链表头部
		this.moveToHead(key)
		return
	}

	if len(this.m) == this.capacity {
		// 取出链表尾部并删除
		tail := this.removeTail()
		// 删除m中的元素
		delete(this.m, tail.key)
	}

	// 新建node
	newNode := &node{
		key:   key,
		value: value,
	}
	// 插入链表头部
	this.addToHead(newNode)
	// 插入map
	this.m[key] = newNode
}

func (this *LRUCache) addToHead(n *node) {
	this.lst = append([]*node{n}, this.lst...)
}

func (this *LRUCache) removeTail() *node {
	tail := this.lst[len(this.lst)-1]
	this.lst = this.lst[:len(this.lst)-1]
	return tail
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

package main

import "fmt"


type node struct {
    key int
    value int
}

type LRU struct {
    m map[int]*node
    lst []*node
    capacity int
}

func (l *LRU)String() string {
    s := ""
    for _, n := range l.lst {
        s += fmt.Sprintf("%d:%d,", n.key,n.value)
    }
    
    return s
} 

func LRUCache(capacity int ) *LRU {
    return &LRU{
        m: make(map[int]*node),
        lst: make([]*node, 0),
        capacity:capacity,
    }
}


func (l *LRU) get(key int) int {
    n, ok := l.m[key]
    if !ok {
        return -1
    }
    
    idx := findNodeFromList(l.lst, n)
    newLst := []*node{l.lst[idx]}
    newLst = append(newLst, l.lst[:idx]...)
    newLst = append(newLst, l.lst[idx+1:]...)
    l.lst = newLst
    return n.value
}

func findNodeFromList(lst []*node, n *node) int {
    for idx,nd := range lst {
        if nd == n {
            return idx
        }
    }
    return 0
}


func (l *LRU) put(key, value int) {
    n, ok := l.m[key]
    if ok {
        n.value = value
        idx := findNodeFromList(l.lst, n)
        newLst := []*node{l.lst[idx]}
        newLst = append(newLst, l.lst[:idx]...)
        newLst = append(newLst, l.lst[idx+1:]...)
        l.lst = newLst
        return
    }
    

    
    if l.capacity == len(l.m) { 
        deleteNode := l.lst[len(l.lst)-1]
        l.lst = l.lst[:len(l.lst)-1]
        delete(l.m, deleteNode.key)
    }
    
    addNode := &node{
        key: key,
        value: value,
    }
    l.m[key] = addNode
    newLst := make([]*node, 0)
    newLst = append(newLst, addNode)
    newLst = append(newLst, l.lst...)
    l.lst = newLst
}



func main() {
    lru := LRUCache(3)
    
    fmt.Println(lru.get(1))
    lru.put(1,10)
    fmt.Println(lru.get(1))
    
    lru.put(2,20)
    lru.put(3,30)
    fmt.Println(lru)
    
    lru.put(4,40)
    fmt.Println(lru)
    
    lru.put(4,50)
    fmt.Println(lru)
}

3.2. Java

public class LRU
{
    public static void main(String[] args)
    {
        //默认LinkedHashMap是按照插入顺序排序的，可以用有参的构造函数设置成按访问顺序排序
        Map<Integer,Integer> map = new LinkedHashMap<Integer, Integer>(3, (float) 0.75, true)
        {
            //重写removeEldestEntry方法，设置LRU的容量
            //size大于3的时候如果在插入新的数据，那么会把链表头部的节点删除
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest)
            {
                return size() > 3;
            }
        };

        map.put(1, 1);
        map.put(2, 2);
        map.put(3, 3);
        System.out.println(map);//{1=1, 2=2, 3=3}
        map.put(4, 4);
        System.out.println(map);//{2=2, 3=3, 4=4}，删除了头部的1，尾部插入了4
        map.get(2);
        System.out.println(map);//{3=3, 4=4, 2=2}，2移动到了尾部

    }
}

4. 参考

• 设计LRU缓存结构_牛客题霸_牛客网
• 146. LRU 缓存机制 - 力扣（LeetCode）