手动实现Redis的LRU缓存机制示例详解

前言

最近在逛博客的时候看到了有关redis方面的面试题，其中提到了redis在内存达到最大限制的时候会使用lru等淘汰机制，然后找了这方面的一些资料与大家分享一下。 lru总体大概是这样的，最近使用的放在前面，最近没用的放在后面，如果来了一个新的数，此时内存满了，就需要把旧的数淘汰，那为了方便移动数据，肯定就得使用链表类似的数据结构，再加上要判断这条数据是不是最新的或者最旧的那么应该也要使用hashmap等key-value形式的数据结构。

第一种实现(使用linkedhashmap)

public class lrucache {

  int capacity;
  map<integer,integer> map;

  public lrucache(int capacity){
    this.capacity = capacity;
    map = new linkedhashmap<>();
  }

  public int get(int key){
    //如果没有找到
    if (!map.containskey(key)){
      return -1;
    }
    //找到了就刷新数据
    integer value = map.remove(key);
    map.put(key,value);
    return value;
  }

  public void put(int key,int value){
    if (map.containskey(key)){
      map.remove(key);
      map.put(key,value);
      return;
    }
    map.put(key,value);
    //超出capacity，删除最久没用的即第一个,或者可以复写removeeldestentry方法
    if (map.size() > capacity){
      map.remove(map.entryset().iterator().next().getkey());
    }
  }

  public static void main(string[] args) {
    lrucache lrucache = new lrucache(10);
    for (int i = 0; i < 10; i++) {
      lrucache.map.put(i,i);
      system.out.println(lrucache.map.size());
    }
    system.out.println(lrucache.map);
    lrucache.put(10,200);
    system.out.println(lrucache.map);
  }

第二种实现(双链表+hashmap)

public class lrucache {  private int capacity;  private map<integer,listnode>map;  private listnode head;  private listnode tail;  public lrucache2(int capacity){    this.capacity = capacity;    map = new hashmap<>();    head = new listnode(-1,-1);    tail = new listnode(-1,-1);    head.next = tail;    tail.pre = head;  }  public int get(int key){    if (!map.containskey(key)){      return -1;    }    listnode node = map.get(key);    node.pre.next = node.next;    node.next.pre = node.pre;    return node.val;  }  public void put(int key,int value){    if (get(key)!=-1){      map.get(key).val = value;      return;    }    listnode node = new listnode(key,value);    map.put(key,node);    movetotail(node);    if (map.size() > capacity){      map.remove(head.next.key);      head.next = head.next.next;      head.next.pre = head;    }  }  //把节点移动到尾巴  private void movetotail(listnode node) {    node.pre = tail.pre;    tail.pre = node;    node.pre.next = node;    node.next = tail;  }  //定义双向链表节点  private class listnode{    int key;    int val;    listnode pre;    listnode next;    //初始化双向链表    public listnode(int key,int val){      this.key = key;      this.val = val;      pre = null;      next = null;    }  }}

像第一种方式，如果复写removeeldestentry会更简单，这里简单的展示一下

public class lrucache extends linkedhashmap<integer,integer> {
  private int capacity;
  
  @override
  protected boolean removeeldestentry(map.entry<integer, integer> eldest) {
    return size() > capacity;
  }
}

到此这篇关于手动实现redis的lru缓存机制的文章就介绍到这了,更多相关redis的lru缓存机制内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com！