首页 > 代码库 > 面试题:实现LRUCache::Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法

面试题:实现LRUCache::Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

  • 题目大意:为LRU Cache设计一个数据结构,它支持两个操作:

   1)get(key):如果key在cache中,则返回对应的value值,否则返回-1

   2)set(key,value):如果key不在cache中,则将该(key,value)插入cache中(注意,如果cache已满,则必须把最近最久未使用的元素从cache中删除);如果key在cache中,则重置value的值。

  • 解题思路:题目让设计一个LRU Cache,即根据LRU算法设计一个缓存。在这之前需要弄清楚LRU算法的核心思想,LRU全称是Least

Recently Used,即最近最久未使用的意思。在操作系统的内存管理中,有一类很重要的算法就是内存页面置换算法(包括FIFO,LRU,LFU等几种常见页面置换算法)。事实上,Cache算法和内存页面置换算法的核心思想是一样的:都是在给定一个限定大小的空间的前提下,设计一个原则如何来更新和访问其中的元素。下面说一下LRU算法的核心思想,LRU算法的设计原则是:如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。也就是说,当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。

  而用什么数据结构来实现LRU算法呢?可能大多数人都会想到:用一个数组来存储数据,给每一个数据项标记一个访问时间戳,每次插入新数据项的时候,先把数组中存在的数据项的时间戳自增,并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候,将被访问的数据项的时间戳置为0。当数组空间已满时,将时间戳最大的数据项淘汰。

  这种实现思路很简单,但是有什么缺陷呢?需要不停地维护数据项的访问时间戳,另外,在插入数据、删除数据以及访问数据时,时间复杂度都是O(n)。

  那么有没有更好的实现办法呢?

  那就是利用链表和hashmap。当需要插入新的数据项的时候,如果新数据项在链表中存在(一般称为命中),则把该节点移到链表头部,如果不存在,则新建一个节点,放到链表头部,若缓存满了,则把链表最后一个节点删除即可。在访问数据的时候,如果数据项在链表中存在,则把该节点移到链表头部,否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。

  总结一下:根据题目的要求,LRU Cache具备的操作:

  1)set(key,value):如果key在hashmap中存在,则先重置对应的value值,然后获取对应的节点cur,将cur节点从链表删除,并移动到链表的头部;若果key在hashmap不存在,则新建一个节点,并将节点放到链表的头部。当Cache存满的时候,将链表最后一个节点删除即可。

  2)get(key):如果key在hashmap中存在,则把对应的节点放到链表头部,并返回对应的value值;如果不存在,则返回-1。

 

package com.Netesay.interview;import java.util.HashMap;import java.util.Map;/** * @Author: weblee * @Email: likaiweb@163.com * @Blog: http://www.cnblogs.com/lkzf/ * @Time: 2014年10月24日下午6:29:40 *  *************        function description *************** * **************************************************** */public class LRUCache {    Map<Integer, CacheNode> cacheMap;    CacheNode head, tail;    int capacity;        //使用双向链表和map,map将k对应与链表的节点      //链表里保存k和value      public LRUCache(int capacity) {    this.capacity = capacity;        cacheMap = new HashMap<Integer, CacheNode>(capacity);        head = new CacheNode(-1, -1);    tail = new CacheNode(1, 1);        head.next = tail;    tail.pre = head;    }    public int get(int key) {    if (cacheMap.containsKey(key)) {        CacheNode node = (CacheNode)cacheMap.get(key);                put2Head(node);                return node.value;    } else {        return -1;    }    }    public void set(int key, int value) {    if (cacheMap.containsKey(key)) {        CacheNode p = cacheMap.get(key);                p.value = value;                put2Head(p);    } else if(cacheMap.size() < capacity) {        CacheNode node = new CacheNode(key, value);        put2Head(node);        cacheMap.put(key, node);    } else {        CacheNode p = new CacheNode(key, value);        put2Head(p);        cacheMap.put(key, p);                int tmpKey = removeEnd();        cacheMap.remove(tmpKey);    }    }        private void put2Head(CacheNode p) {    if (p.next != null && p.pre != null) {        p.pre.next = p.next;        p.next.pre = p.pre;    }        p.pre = head;    p.next = head.next;    head.next.pre = p;    head.next = p;    }        private int removeEnd() {    CacheNode p = tail.pre;    tail.pre.pre.next = tail;    tail.pre = p.pre;        p.pre = null;    p.next = null;        return p.key;    }}class CacheNode {    int key;    int value;        CacheNode pre;    CacheNode next;    public CacheNode(int key, int value) {    this.key = key;    this.value =http://www.mamicode.com/ value;    }}

 

面试题:实现LRUCache::Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法