首页 > 代码库 > 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实现