算法-LRU

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

缓存淘汰算法

双向链表 + 哈希表

import java.util.HashMap;
import java.util.Map;

class LRUCache {
  // 双向节点定义
  class DoubleLinkNode {
    DoubleLinkNode pre;
    DoubleLinkNode next;
    int key;
    int value;

    public DoubleLinkNode() {
    }

    public DoubleLinkNode(int _key, int _value) {
      key = _key;
      value = _value;
    }
  }

  private Map<Integer, DoubleLinkNode> cache = new HashMap<Integer, DoubleLinkNode>();//哈希表
  private int size;
  private int capacity;
  private DoubleLinkNode head, tail;//一个头结点， 一个尾结点

  //双向链表+哈希表
  public LRUCache(int capacity) {
    this.capacity = capacity;
    this.head = new DoubleLinkNode();
    this.tail = new DoubleLinkNode();
    this.head.next = this.tail;
    this.tail.pre = this.head;
    this.size = 0;
  }

  // 获取节点
  public int get(int key) {
    // 从缓存中获取节点
    DoubleLinkNode node = cache.get(key);
    if (node == null) {
      return -1;
    }
    // 将当前要访问的node移动到最前面
    moveToHead(node);
    return node.value;
  }


  public void put(int key, int value) {
    DoubleLinkNode node = this.cache.get(key);
    if (node == null) {
      //如果key不存在， 创建一个新的节点
      DoubleLinkNode newNode = new DoubleLinkNode(key, value);
      cache.put(key, newNode);
      addToHead(newNode);
      ++size;
      if (size > capacity) {
        DoubleLinkNode rTail = removeTail();
        cache.remove(rTail.key);
        --size;
      }
    } else {
      node.value = value;
      moveToHead(node);
    }
  }

  public void moveToHead(DoubleLinkNode node) {
    removeNode(node);
    addToHead(node);
  }

  public void addToHead(DoubleLinkNode node) {
    node.pre = head;
    node.next = head.next;
    head.next.pre = node;
    head.next = node;
  }

  public void removeNode(DoubleLinkNode node) {
    node.pre.next = node.next;
    node.next.pre = node.pre;
  }

  public DoubleLinkNode removeTail() {
    DoubleLinkNode nTailNode = tail.pre;
    removeNode(nTailNode);
    return nTailNode;
  }


  @Override
  public String toString() {
    StringBuffer string = new StringBuffer();
    DoubleLinkNode node = this.head;

    while (node != this.tail) {
      string.append(String.valueOf(node.value) + "->");
      node = node.next;
    }

    //最后加上tail
    string.append(String.valueOf(node.value));
    node = node.next;

    return string.toString();
  }
}

class Demo {
  public static void main(String[] args) {
    LRUCache cache = new LRUCache(2);
    cache.put(1,1);
    cache.put(2,2);
    cache.put(3,3);
    cache.get(1);
    cache.put(2,2);
    cache.put(2,4);
    System.out.println(cache.toString());
  }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

打印结果

0->4->3->0