LRU算法介绍

众所周知，操作系统缓存是有限的，当缓存快要耗尽的时候，我们就需要对已经存在的页面进行置换。记得在大二学习操作系统的时候介绍过几个缓存策略，分别是OPT，FIFO，LRU，Clock，LFU。我们本文简单介绍一下LRU算法的实现。

LRU算法实现

实现简介

我在网上搜索LRU算法的时候看到leetcode一道题目，这里我以leetcode 146一套题目为例，讲解LRU算法的实现。我使用的语言是C++，如果你熟悉C++的话用LinkedList+map，Java的话有现成的数据结构即LinkedHashMap。

实现思路

实现主要使用的数据结构是LinkedList + map(即链表+哈希表)。实现主要的函数是init、get和put。init函数负责初始化，其中包括cache大小的设置等；get函数负责获取缓存中的对于的页面。put函数负责将新的页面插入缓存中。下面我具体介绍一下这三个函数的具体实现。

1. 在init函数中，我们初始化一个LinkedList = NULL;，同时初始化这个cache的大小capacity和现在的页面数count。
2. 在get函数中，我们根据key到hash表中去查询有没有对应的节点，如果存在，将这个节点摘出来，放在链表最头部的位置。这里摘出来有个小技巧，我们可以将这个节点和他后面的几点数据互换，然后删除后面的节点。如图

RemoveNode

3. 在put函数中，我们先查询这个节点是不是存在，如果存在，根据value生成新的节点，存在map中，替换原来的节点，并且push到链表的头部。如果不存在，直接生成新节点，存入map，并push到链表头部。

实现代码

//
//  main.cpp
//  LRU_Demo
//
//  Created by 李林 on 2017/9/14.
//  Copyright © 2017年 lee. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#include <iterator>
using namespace std;

/*
 核心思想：map+List。类似于Java中LinkedHashMap。
 map变化和List变化需要同步，查询运用map优势，增减运用List优势。
 */

struct Node {
    int key;
    int val;
    Node *next;
    Node(int k, int v) : key(k), val(v), next(NULL) {
    }
};

class LRUCache {
public:
    LRUCache(int capacity) {
        count = 0;
        size = capacity;
        cacheList = NULL;
    }
    
    int get(int key) {
        if (cacheList == NULL)  return -1;
        
        map<int, Node *>::iterator it = mp.find(key);
        if (it == mp.end()) {
            return -1;
        } else {
            Node *newNode = it->second;
            pushNewNodeToFront(newNode);
            return cacheList->val;
        }
    }
    
    void put(int key, int val) {
        if (cacheList == NULL) {
            cacheList = new Node(key, val);
            cacheList->next = NULL;
            mp[key] = cacheList;
            count++;
        } else {
            map<int, Node *>::iterator it = mp.find(key);
            if (it == mp.end()) {       // 没有这个key
                
                if (count == size) {
                    Node *p = cacheList;
                    Node *pre = p;
                    
                    while (p->next != NULL) {
                        pre = p;
                        p = p->next;
                    }
                    
                    mp.erase(p->key);
                    count--;
                    if (pre == p) {     // 只有一个节点
                        cacheList = NULL;
                    } else {
                        pre->next = NULL;
                    }
                    free(p);
                }
                
                Node *newNode = new Node(key, val);
                newNode->next = cacheList;
                cacheList = newNode;
                mp[key] = cacheList;
                count++;
            } else {                    // 有这个key
                Node *newNode = it->second;
                newNode->val = val;
                pushNewNodeToFront(newNode);
            }
        }
    }
    
    void pushNewNodeToFront(Node *newNode) {
        if (count == 1) return ;
        if (newNode == cacheList) return ;
        
        Node *Next = newNode->next;
        if (Next) {
            newNode->next = Next->next;
            swap(newNode->key, Next->key);
            swap(newNode->val, Next->val);
            Next->next = cacheList;
            cacheList = Next;
            
            // 勿忘map操作
            swap(mp[newNode->key], mp[Next->key]);
        } else {                        // 最后一个节点
            Node *p = cacheList;
            while (p->next != newNode) {
                p = p->next;
            }
            p->next = NULL;
            
            newNode->next = cacheList;
            cacheList = newNode;
        }
    }
    
private:
    int count;
    int size;
    Node *cacheList;
    map<int, Node*> mp;
};

int main(int argc, const char * argv[]) {
    
    LRUCache cache(2);
    
    cache.put(1, 1);
    cache.put(2, 2);
    cout<<cache.get(1)<<endl;       // returns 1
    cache.put(3, 3);    // evicts key 2
    cout<<cache.get(2)<<endl;       // returns -1 (not found)
    cache.put(4, 4);    // evicts key 1
    cout<<cache.get(1)<<endl;       // returns -1 (not found)
    cout<<cache.get(3)<<endl;       // returns 3
    cout<<cache.get(4)<<endl;       // returns 4
    return 0;
}

运行结果

运行的结果是1，-1，-1，3，4。（-1代表未命中）

运行结果

参考文章

LRU wikidepia
CSDN 博客