ehcache缓存原理_mysql缓存机制

ehcache缓存原理_mysql缓存机制运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。实现 LRUCache 类:LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类:

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作?

示例:

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示:

1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 104
最多调用 3 * 104 次 get 和 put

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解
用unoredered_map和双向链表

class LRUCache { 
   
private:
    struct LinkNode{ 
   
        LinkNode *next,*pre;
        int val;
        int key;
        LinkNode(int key,int val,LinkNode *pre,LinkNode *next):key(key),val(val),pre(pre),next(next){ 
   };
        LinkNode(int key,int val):key(key),val(val){ 
   next = NULL;pre = NULL;};
    };
    int capacity;
    LinkNode *T = NULL;
    int num = 0;
    LinkNode *end = NULL;
    unordered_map<int,LinkNode*> Hash;
public:
    LRUCache(int capacity):capacity(capacity) { 
   
        T = new LinkNode(0,0);
        end = T;
        num = 0;
    }
    
    int get(int key) { 
   
        if(Hash.find(key) == Hash.end())return -1;
        LinkNode * t = Hash[key];
        if(end == t && num > 1)end = t->pre;
        t->pre->next = t->next;
        if(t->next != NULL)t->next->pre = t->pre;
        t->next = T->next;
        t->pre = T;
        if(T->next != NULL)T->next->pre = t;
        T->next = t;
        return t->val;
    }
    
    void put(int key, int value) { 
   
        if(Hash.find(key) != Hash.end()){ 
   
            LinkNode * t = Hash[key];
            t->pre->next = t->next;
            if(end == t && num > 1)end = t->pre;
            if(t->next != NULL)t->next->pre = t->pre;
            t->next = T->next;
            t->pre = T;
            if(T->next != NULL)T->next->pre = t;
            T->next = t;
            t->val = value;
        }else if(num < capacity){ 
   
            num ++;
            LinkNode *t = new LinkNode(key,value,T,T->next);
            Hash[key] = t;
            if(T->next != NULL)T->next->pre = t;
            T->next = t;
            if(num == 1)end = t;
        }else{ 
   
            end = end->pre;
            LinkNode *tt = end->next;
            end->next = NULL;
            Hash.erase(tt->key);
            delete tt;
            LinkNode *t = new LinkNode(key,value,T,T->next);
            Hash[key] = t;
            if(T->next != NULL)T->next->pre = t;
            T->next = t;
        }
    }
};

/** * 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); */
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168851.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号