美文网首页
LRU缓存算法

LRU缓存算法

作者: boyiis | 来源:发表于2018-11-07 11:00 被阅读0次

1. LRU缓存可使用一个HashMap和双向链表实现

1.1定义双向链表的节点:
class Node{
    int key;
    int value;
    Node pre;
    Node next;
 
    public Node(int key, int value){
        this.key = key;
        this.value = value;
    }
}
1.2实现:
public class LRUCache {
    int capacity;
    HashMap<Integer, Node> map = new HashMap<Integer, Node>();
    Node head=null;
    Node end=null;
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
 
    public int get(int key) {
        if(map.containsKey(key)){
            Node n = map.get(key);
            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);
        }
    }
}

相关文章

  • 缓存相关

    cache淘汰算法:LIRS 算法 缓存那些事 Redis缓存淘汰算法,LRU算法,LRU算法讲解

  • 缓存淘汰算法--LRU算法

    缓存淘汰算法--LRU算法 1. LRU 1.1 原理 LRU(Least recently used,)算法根据...

  • Algorithm进阶计划 -- LRU 与 LFU 算法

    LRU 与 LFU 算法LRU 算法LFU 算法 1. LRU 算法 LRU 算法是一种缓存淘汰策略,是 Leas...

  • LinkedHashMap源码浅析

    这是LRU算法的核心,比如Glide里无论是内存缓存还是硬盘缓存,其实核心都是用到了LRU算法,而LRU算法核心是...

  • 缓存过期算法相关点

    常用缓存过期算法 LRU 最近最少使用 LRU缓存过期算法 最近最少使用的对象最先被删除 原理在Android中,...

  • LRU简单实现-了解一下?

    LRU 算法 LRU 是一种作为缓存的算法,像 CPU 缓存,数据库缓存,浏览器缓存。以及在移动端开发时的图片安缓...

  • LRU算法

    LRU是最近最少使用的算法,它的核心思想是当缓存满时,会优先淘汰那些最近最少使用的缓存对象。采用LRU算法的缓存有...

  • 缓存算法-LRU

    +++Categories = ["iOS",]Tags = ["缓存算法","LRU",]date = "201...

  • glide缓存之ActiveResources

    glide 缓存分为内存缓存和硬盘缓存,内存缓存是用Lru算法缓存和弱引用缓存(ActiveResources),...

  • Android缓存实践2019-11-27

    LRU缓存原理 LRU(Least Recently Used),近期最少使用的算法,它的核心思想是当缓存满时,会...

网友评论

      本文标题:LRU缓存算法

      本文链接:https://www.haomeiwen.com/subject/gpbmxqtx.html