集册 Java实例教程 基于HashMap的LRU缓存

基于HashMap的LRU缓存

欢马劈雪     最近更新时间:2020-04-29 02:18:59

253

Java 基于HashMap的LRU缓存

LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最少使用的页面予以淘汰。

LRU算法示意图:

nowjava.com


LRU算法代码:


/* 
*来 自
 nowjava.com - 时  代  Java
*/

import java.util.HashMap;


class LRU {

  int capacity;

  HashMap map = new HashMap();

  Node head = null;

  Node end = null;


  public LRU(int capacity) {

    this.capacity = capacity;

  }


  public int get(int key) {

    if (map.containsKey(key)) {

      Node n = map.get(key);
      /**来自 
       时代Java公众号**/

      remove(n);

      setHead(n);

      return n.value;

    }


    return -1;

  }


  public void remove(Node n) {

    if (n.pre != null) {

      n.pre.next = n.next;

    } else {

      head = n.next;

    }


    if (n.next != null) {

      n.next.pre = n.pre;

    } else {

      end = n.pre;

    }


  }


  public void setHead(Node n) {

    n.next = head;

    n.pre = null;


    if (head != null)

      head.pre = n;


    head = n;


    if (end == null)

      end = head;

  }


  public void set(int key, int value) {

    if (map.containsKey(key)) {

      Node old = map.get(key);

      old.value = value;

      remove(old);

      setHead(old);

    } else {

      Node created = new Node(key, value);

      if (map.size() >= capacity) {

        map.remove(end.key);

        remove(end);

        setHead(created);


      } else {

        setHead(created);

      }


      map.put(key, created);

    }

  }


}


class Node {

  int key;

  int value;

  Node pre;

  Node next;


  public Node(int key, int value) {

    this.key = key;

    this.value = value;

  }

}


public&
展开阅读全文