文档章节

实现一个LRU 算法

暗中观察
 暗中观察
发布于 06/30 20:14
字数 367
阅读 22
收藏 0

lru 这种算法一般用于缓存过期策略,这里用一个hashmap和node这两种数据结构实现,代码如下

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

public class LRU {
    private Node head;//记录下一个要移除的node
    private Node end;//记录插入的尾巴节点
    private Map<String, Node> map=new HashMap<>();//加快查找速度,不用遍历链表,时间复杂度为O(1)
    private int limit;//最大容量

    public LRU(int limit) {
        this.limit = limit;
    }

    public void add(String key , String val) {
        Node node = map.get(key);
        if(node == null){
            if(map.size() >= limit){
                map.remove(head.key);
                removeNode(head);
            }
            Node newNode = new Node(key, val);
            map.put(key,newNode);
            addNode(newNode);
        }else {
            reflush(node);
        }
    }

    @Override
    public String toString() {
        return "LRU{" +
                "map=" + map +
                ", limit=" + limit +
                '}';
    }

    public void remove(String key) {
        Node node = map.remove(key);
        removeNode(node);
    }
    public String get(String key) {
        Node node = map.get(key);
        if(node == null){
            return null;
        }
        reflush(node);
        return node.val;
    }
    private void reflush(Node node) {
        if(node == end){
            return;
        }
        removeNode(node);
        addNode(node);
    }

    private void removeNode(Node node) {
        boolean isHeadOrEnd=false;
        if(node == end){
            end=end.pre;
            isHeadOrEnd=true;
        }
        if(node == head){
            head=head.next;
            isHeadOrEnd=true;
        }
        if(isHeadOrEnd){
            return;
        }
        if(node.next != null){
            node.next.pre=node.pre;
        }
        if(node.pre != null){
            node.pre.next=node.next;
        }
    }

    private void addNode(Node newNode) {
        if(end != null){
            end.next=newNode;
            newNode.pre=end;
        }
        end=newNode;
        if(head == null){
            head=end;
        }
    }
}
/*这里用双向队列,在移除时需要改变node的指向,如果不是双端队列,会比较麻烦*/
class Node{
    public String key;
    public String val;
    public Node pre;
    public Node next;

    public Node(String key, String val) {
        this.key = key;
        this.val = val;
    }
}

参考

本文转载自:https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653195947&idx=1&sn=2954871ed1195dd3ebab0c9...

暗中观察

暗中观察

粉丝 7
博文 128
码字总数 45846
作品 0
惠州
私信 提问
LRU-最近最少使用算法

LRU是Least Recently Used 近期最少使用算法 1.1. 原理 LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来...

zh_iOS
2016/11/03
128
0
LRU 缓存置换算法

1.LRU 1.1. 原理 LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。 1.2. 实现 最...

满小茂
2016/01/13
694
0
设计实现一个LRU Cache

1 什么是LRU Cache 在LeetCode上有一个LRU Cache实现的题目 Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: g......

芥末无疆
2018/04/13
0
0
年薪六十万的Python程序员第一道面试题就是算法!看我如何破解?

LRU算法在Python这种后端工程师面试中,是必出题。如果你不能够彻底理解,那么就是一道坎!此文带你快速理解LRU算法,然后仅用16行Python代码轻松实现一个基于LRU算法的缓存。 LRU:Least r...

Python资料
2018/03/09
0
0
配置Redis作为缓存

将 Redis 用作缓存时, 如果内存空间用满, 就会自动驱逐老的数据。 默认情况下 memcached 就是这种方式, 大部分开发者都比较熟悉。 LRU是Redis唯一支持的回收算法. 本文详细介绍用于限制最大内...

renfufei
2017/08/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
6分钟前
3
0
java数据类型

基本类型: 整型:Byte,short,int,long 浮点型:float,double 字符型:char 布尔型:boolean 引用类型: 类类型: 接口类型: 数组类型: Byte 1字节 八位 -128 -------- 127 short 2字节...

audience_1
52分钟前
7
0
太全了|万字详解Docker架构原理、功能及使用

一、简介 1、了解Docker的前生LXC LXC为Linux Container的简写。可以提供轻量级的虚拟化,以便隔离进程和资源,而且不需要提供指令解释机制以及全虚拟化的其他复杂性。相当于C++中的NameSpa...

Java技术剑
53分钟前
11
0
Wifiphisher —— 非常非常非常流氓的 WIFI 网络钓鱼框架

编者注:这是一个非常流氓的 WIFI 网络钓鱼工具,甚至可能是非法的工具(取决于你的使用场景)。在没有事先获得许可的情况下使用 Wifiphisher 攻击基础网络设施将被视为非法活动。使用时请遵...

红薯
今天
52
1
MongoDB 4 on CentOS 7安装指南

本教程为CentOS x86_64 7.x操作系统下,MongoDB Community x86_64 4.2(GA)安装指南。 安装方式一:yum repo在线安装 [此方式较为简单,官方推荐] Step1:新建MongDB社区版Yum镜像源。 # vim ...

王焱君
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部