做兼职的设计网站有哪些工作内容,工作流程管理系统说明书,石家庄企业网站网页设计,企业官网和小程序的商城版本的区别文章目录 LRU算法LRU 如何实现LinkedHashMap来实现的LRU算法的缓存HashMap实现LRU算法的缓存 LRU算法
LRU#xff08;Least Recently Used#xff09;算法可以使用哈希表和双向链表来实现。哈希表用于快速查找数据#xff0c;双向链表用于记录数据的访问顺序。以下是LRU算法… 文章目录 LRU算法LRU 如何实现LinkedHashMap来实现的LRU算法的缓存HashMap实现LRU算法的缓存 LRU算法
LRULeast Recently Used算法可以使用哈希表和双向链表来实现。哈希表用于快速查找数据双向链表用于记录数据的访问顺序。以下是LRU算法的具体实现
使用一个哈希表和一个双向链表来实现缓存。哈希表中的key是数据的键值value是对应节点在双向链表中的位置。双向链表中头部是最近访问过的数据尾部是最久未被访问的数据。当需要获取缓存数据时先通过哈希表查找是否存在缓存数据。如果存在则将对应节点移动到链表头部否则返回null。当需要插入新的数据到缓存时先检查缓存是否已满。如果已满则删除双向链表的尾部节点并从哈希表中删除该节点然后再将新数据插入到链表头部并在哈希表中添加新节点。当需要删除缓存数据时先通过哈希表查找节点位置然后从链表中删除该节点并同时从哈希表中删除对应项。 总之LRU算法通过维护一个哈希表和一个双向链表来实现缓存淘汰策略。当缓存满时将最久未被访问的数据从缓存中删除保留最近访问过的数据。这样可以有效减少缓存命中率的损失提高系统性能
LRU 如何实现
最近最少使用策略 LRULeast Recently Used是一种缓存淘汰算法是一种缓存淘汰机制。 使用双向链表实现的队列队列的最大容量为缓存的大小。在使用过程中把最近使用的页面移动到队列头最近没有使用的页面将被放在队列尾的位置 使用一个哈希表把页号作为键把缓存在队列中的节点的地址作为值只需要把这个页 对应的节点移动到队列的前面如果需要的页面在内存中此时需要把这个页面加载到内 存中简单的说就是将一个新节点添加到队列前面并在哈希表中跟新相应的节点地 址如果队列是满的那么就从队尾移除一个节点并将新节点添加到队列的前面。
1、概念其实解释起来很简单LRU就 是Least Recently Used的缩写翻译过来就是“最近最少使用”。也就是说LRU算法会将最近最少用的缓存移除让给最新使⽤的缓存。⽽往往最常读取的也就是读取次数最多的所以利⽤好LRU算法我们能够提供对热点数据的缓存效率能够提⾼缓存服务的内存使⽤率。 2、实现 1、思路 i. 限制缓存大小 ii. 查询出最近最晚⽤的缓存 iii. 给最近最少⽤的缓存做⼀个标识 2、代码
LinkedHashMap来实现的LRU算法的缓存
package com.lc.lru;import java.util.LinkedHashMap;
import java.util.Map;public class LRUCacheK, V extends LinkedHashMapK, V {private int capacity;public LRUCache(int capacity) {super(capacity, 0.75f, true);this.capacity capacity;}Overrideprotected boolean removeEldestEntry(Map.EntryK, V eldest) {return size() capacity;}public static void main(String[] args) {LRUCacheInteger, String cache new LRUCache(2);cache.put(1, One);cache.put(2, Two);System.out.println(cache); // 输出{1One, 2Two}cache.put(3, Three);System.out.println(cache); // 输出{2Two, 3Three}cache.get(2);System.out.println(cache); // 输出{3Three, 2Two}}}HashMap实现LRU算法的缓存
import java.util.HashMap;
import java.util.Map;/*** Desc 采用LRU置换算法的缓存* Author lc* Date 2022/4/3 19:44*/
public class LRUCacheK, V {// 静态内部类双向链表中的节点类key理解为页面号val理解为页面内容static class EntryK, V {public EntryK, V prev;public EntryK, V next;public K key;public V val;public Entry() {}public Entry(K key, V val) { this.key key; this.val val; }}private EntryK, V head, tail; // 虚拟头节点和虚拟尾节点private final int capacity; // 缓存容量private int size; // 缓存占用量MapK, EntryK, V cache; // 哈希表记录双向列表节点的地址值public LRUCache(int capacity) {this.capacity capacity;initCache();}// 初始化LRU缓存private void initCache() {head new Entry();tail new Entry();head.next tail;tail.prev head;size 0;cache new HashMap(this.capacity);}private V get(K key) {EntryK, V entry cache.get(key);if(entry ! null) {moveToTail(entry);return entry.val;} else {return null;}}private void put(K key, V val) {EntryK, V entry cache.get(key);if(entry ! null) {// 缓存命中entry.val val;moveToTail(entry);} else {// 缓存未命中if(size capacity) {// 缓存已满删除链表头部节点EntryK, V h head.next;deleteEntry(h);cache.remove(h.key);size--;}// 添加新页面到链表尾部EntryK, V newEntry new Entry(key, val);addToTail(newEntry);cache.put(key, newEntry);size;}}private void moveToTail(EntryK, V entry) {deleteEntry(entry);addToTail(entry);}private void addToTail(EntryK, V entry) {if(entry ! null) {entry.next tail;entry.prev tail.prev;tail.prev.next entry;tail.prev entry;}}private void deleteEntry(EntryK, V entry) {if(entry ! null) {entry.prev.next entry.next;entry.next.prev entry.prev;}}public static void main(String[] args) {LRUCacheInteger, String cache new LRUCache(2);cache.put(1,可口可乐);cache.put(2,雪碧);System.out.println(页面1的内容 cache.get(1));cache.put(3,果粒橙); // 此时缓存已满且页面2最久未被使用因为cache.get(1)访问了页面1页面2被置换成页面3System.out.println(页面2的内容 cache.get(2)); // 页面2已被换出访问不到}}
