算法-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);
    }
}

原生写法：

/**
 * LRU缓存实现
 * @param <K> key
 * @param <V> value
 */
public class LRUCache<K, V> {

    // 双向链表节点
    static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> hashMap;
    // 虚拟头、尾哨兵节点，简化边界判断，不用判null
    private final Node<K, V> head;
    private final Node<K, V> tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        hashMap = new HashMap<>();
        head = new Node<>(null, null);
        tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 获取元素
     * @return 不存在返回null
     */
    public V get(K key) {
        Node<K, V> node = hashMap.get(key);
        if (node == null) {
            return null;
        }
        // 访问到节点，移动到链表头部
        moveToHead(node);
        return node.value;
    }

    /**
     * 存入元素
     */
    public void put(K key, V value) {
        Node<K, V> node = hashMap.get(key);
        if (node != null) {
            // key已存在，更新值，并移到头部
            node.value = value;
            moveToHead(node);
        } else {
            // 新建节点
            Node<K, V> newNode = new Node<>(key, value);
            hashMap.put(key, newNode);
            addToHead(newNode);

            // 超过容量，删除尾部节点（最久未使用）
            if (hashMap.size() > capacity) {
                Node<K, V> removeNode = removeTail();
                hashMap.remove(removeNode.key);
            }
        }
    }

    /**
     * 将节点移动到头部：先删除原位置，再插入头部
     */
    private void moveToHead(Node<K, V> node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * 把节点插入head之后（最新位置）
     */
    private void addToHead(Node<K, V> node) {
        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    /**
     * 删除链表中指定节点
     */
    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     * 删除尾节点（tail前面那个，最久未使用）
     */
    private Node<K, V> removeTail() {
        Node<K, V> res = tail.prev;
        removeNode(res);
        return res;
    }
}

参考