这是一个用 双向链表与哈希表实现的 LRU (Least Recently Used) 缓存淘汰算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package main

import (
	"container/list"
	"fmt"
)

type Data struct {
	Key string
	Val interface{}
}

type LRU struct {
	Cap  int
	List *list.List
	Hash map[string]*list.Element
}

func NewLRU(cap int) *LRU {
	return &LRU{Cap: cap, List: list.New(), Hash: make(map[string]*list.Element)}
}

func (lru *LRU) Put(key string, val interface{}) {
	if e, ok := lru.Hash[key]; ok {
		lru.List.Remove(e)
	}
	e := lru.List.PushBack(&Data{Key: key, Val: val})
	lru.Hash[key] = e
	if lru.List.Len() > lru.Cap {
		f := lru.List.Front()
		lru.List.Remove(f)
		delete(lru.Hash, f.Value.(*Data).Key)
	}
}

func (lru *LRU) Get(key string) (val interface{}) {
	if e, ok := lru.Hash[key]; ok {
        lru.List.MoveToBack(e)
		return e.Value.(*Data).Val
	}
	return nil
}