首页 > 代码库 > O(1)读写时间复杂度的LRU策略Cache实现
O(1)读写时间复杂度的LRU策略Cache实现
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace Algorithms{ public class LRUImplementation { internal class CacheNode { internal CacheNode Next = null; internal CacheNode Previous = null; internal object value; internal string key; internal CacheNode(string key, object val) { this.key = key; this.value=http://www.mamicode.com/val; } } private Dictionary<string, CacheNode> values = null; private int size = 0; private CacheNode first; private CacheNode last; public LRUImplementation(int size) { this.size = size; this.values = new Dictionary<string, CacheNode>(size); this.first = this.last = null; } public int ValueCount { get { return this.values.Count; } } public string[] Keys { get { if (this.first != null) { List<string> keyList = new List<string>(); CacheNode node=this.first; do { keyList.Add(node.key); node = node.Next; } while (node != null); return keyList.ToArray(); } return null; } } private void RemoveLRUNode() { if (this.last != null) { this.values.Remove(this.last.key); this.last = this.last.Previous ; this.last.Next = null; } } public void AddValue(string key, object value) { CacheNode node = null; if (this.values.ContainsKey(key)) { node = this.values[key]; node.value = value; if (node != this.first) { if (node.Next != null) { node.Next.Previous = node.Previous; } if (node.Previous != null) { node.Previous.Next = node.Next; } } } else { node = new CacheNode(key, value); if (this.values.Count >= this.size) { this.RemoveLRUNode(); } this.values.Add(key, node); } if (this.first != null && this.first != node) { node.Next = this.first; this.first.Previous = node; } this.first = node; if (this.last == null) { this.last = node; } } public object TryGetValue(string key) { if (this.values.ContainsKey(key)) { CacheNode node = this.values[key]; if (node != this.first) { if (node.Previous != null) { node.Previous.Next = node.Next; } if (node.Next != null) { node.Next.Previous = node.Previous; } this.first.Previous = node; node.Next = this.first; this.first = node; } return this.first.value; } return null; } public string GetBufferContent() { return string.Join(",", this.Keys); } }}
主要使用Hashtable(Dictionary)和链表实现,能达到O(1)的读写时间复杂度。
测试代码:
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace Algorithms{ class Program { static void Main(string[] args) { do { int cacheSize = 0; bool isValid = true; do { Console.WriteLine("Input cache size:"); isValid = int.TryParse(Console.ReadLine(), out cacheSize); if (cacheSize <= 0) { isValid = false; } if (!isValid) { Console.WriteLine("Invalid value."); } } while (!isValid); LRUImplementation lru = new LRUImplementation(cacheSize); Random rand=new Random(); do { Console.WriteLine("Input key:"); string key = Console.ReadLine(); Console.WriteLine("Input value:"); string val = Console.ReadLine(); lru.AddValue(key, val); Console.WriteLine("Cache content:"); Console.ForegroundColor = ConsoleColor.Green; Console.WriteLine(lru.GetBufferContent()); Console.ResetColor(); int randIndex = rand.Next(0, lru.ValueCount - 1); Console.WriteLine("Try to query the {0}th value.", randIndex); lru.TryGetValue(lru.Keys[randIndex]); Console.WriteLine("Cache content:"); Console.ForegroundColor = ConsoleColor.Green; Console.WriteLine(lru.GetBufferContent()); Console.ResetColor(); } while (true); } while (true); } }}
O(1)读写时间复杂度的LRU策略Cache实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。