算法-LRU

LRU介绍

LRU（Least Recently Used）最近最少使用算法，通常在缓存策略中使用。操作系统在内存管理中，对页的置换有应用这一算法。

通常缓存空间有限，因此当空间满的时候，需要淘汰掉部分缓存使得新内容放进来。LRU算法就是其中的一个淘汰策略，即把最近最少使用的缓存置换掉。

LRU的数据结构

朴素的想法

顾名思义，最近最少使用完全可以使用一个链表来实现。

当访问元素来了，先判断它是否在链表，在则移到队首，不在则插入到队首，如果超过链表最大长度（即缓存容量）则删除队尾元素。这里我们使用双向链表，队列通常是队尾进，队首出。我们这里是反过来。

进阶想法

单个链表的数据结构实现上有个问题，在于查找元素的时候，链表要O(n)的整个遍历一遍，这在缓存容量较大的情况下性能很差。有没有别的数据结构帮一把？哈希表，查找性能很高。

这就是LRU的常见实现的数据结构，哈希表+双向链表：

链表中的元素存储缓存的item（key=>value），哈希表中的key是队列item的key，值就是item指针。这样在查找元素的时候，我们去map定位；插入修改元素操作链表。

这里为什么哈希表存了key，链表中还要存key呢？ 这是因为在删除队尾元素的时候，也要删map。如果链表中没有key，就找不到map对应的值了。

LRU 代码实现

Go实现

理解了LRU使用的数据结构 双向链表、哈希表，就很好理解算法的实现。代码我们可以参考simplelru。

Go的标准库中已经有一个双向链表的完整实现，container/list 我们不用再造轮子，可以直接使用它。当然我们这里还是非线程安全的lru。

package mylru

import (
  "container/list"
)

type sdLru struct {
  length uint
  llist  *list.List
  // map的value存放list元素的指针
  mmap map[interface{}]*list.Element
}

// 队列存放的item
type item struct {
  key interface{}
  val interface{}
}

func NewsdLru(len uint) *sdLru {
  return &sdLru{
    length: len,
    mmap:   make(map[interface{}]*list.Element),
    llist:  list.New(),
  }
}

// Add
// map是否有
// Y -> 链表move front; 替换最新值
// N -> 放到front、map;
// 是否满了
// Y -> 剔除队尾+map
func (s *sdLru) Add(key, val interface{}) {
  if ele, ok := s.mmap[key]; ok {
    s.llist.MoveToFront(ele)
    ele.Value.(*item).val = val
    return
  }
  ele := s.llist.PushFront(&item{key, val})
  s.mmap[key] = ele
  // 超长，删除队尾
  if uint(s.llist.Len()) > s.length {
    // 删除队尾元素
    removeEle := s.llist.Remove(s.llist.Back())
    // 别忘了还要删map中的元素，这里要利用到队列返回的key
    delete(s.mmap, removeEle.(*item).key)
  }
  return
}

// Get
// map找到，并移到队首
func (s *sdLru) Get(key interface{}) (val interface{}, ok bool) {
  if ret, ok := s.mmap[key]; ok {
    // 移到front
    s.llist.MoveToFront(ret)
    if ret.Value.(*item) != nil {
      return ret.Value.(*item).val, true
    }
    return nil, true
  }
  return nil, false
}

// Remove
// map查找，删除掉map和list元素
func (s *sdLru) Remove(key interface{}) bool {
  if ret, ok := s.mmap[key]; ok {
    delete(s.mmap, key)
    s.llist.Remove(ret)
    return true
  }
  return false
}

// Keys_Shuffle
// keys顺序随机 从map取
func (s *sdLru) Keys_Shuffle() []interface{} {
  keys := make([]interface{}, len(s.mmap))
  var i int
  for key := range s.mmap {
    keys[i] = key
    i++
  }
  return keys
}

// Keys slice
// Keys 按list从最新到最老的顺序 从首部到尾部
func (s *sdLru) Keys() []interface{} {
  keys := make([]interface{}, s.llist.Len())
  var i int
  for ele := s.llist.Front(); ele != nil; ele = ele.Next() {
    keys[i] = ele.Value.(*item).key
    i++
  }
  return keys
}

// Len
// 当前长度
func (s *sdLru) Len() (len uint) {
  return uint(s.llist.Len())
}

测试

package main

import (
  "fmt"
  "lru/mylru"
)

func main() {

  l := mylru.NewsdLru(10)
  for i := 0; i <= 20; i++ {
    l.Add(i, i)
  }

  fmt.Println(l.Len()) // 10

  fmt.Println(l.Keys()) // [20 19 18 17 16 15 14 13 12 11]

}

Java

Java比Go有优势的一点出来了，Java语言自身提供了太多现成好用的工具。就如LinkedHashMap，就是HashMap和链表的结合，支持LRU算法实现。

public class Lru<K, V> {
    private Map<K, V> map;

    public Lru(int capacity) {
        /**
         * LinkedHashMap 构造函数包含 accessOrder 可以维护访问顺序
         * 当容量超过时，执行删除老元素
         */
        map = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > capacity;
            }
        };
    }

    public static void main(String[] args) {
        Lru<String, Long> lruCache = new Lru<>(3);

        lruCache.map.put("x", 1L);
        lruCache.map.put("y", 2L);
        lruCache.map.put("z", 3L);
        lruCache.map.put("a", 4L);
        lruCache.map.put("b", 3L);

        System.out.println(lruCache.map);
    }
}

参考