Dictionary: Реализация LRU Cache

Решение

Анализ задачи

LRU Cache — это структура данных, которая хранит последние использованные элементы. Ключевые требования:

1. O(1) для Get и Put — нужна Hash Table (Dictionary)
2. O(1) для удаления самого старого — нужен двусвязный список
3. Отслеживание порядка использования — новые элементы в конец, старые в начало

Идея: Комбинация Dictionary + LinkedList

• Dictionary → быстрый поиск по ключу
• LinkedList → быстрое удаление/перемещение элементов

---

Базовая реализация

using System;
using System.Collections.Generic;

public class LRUCache<TKey, TValue> where TKey : notnull
{
    private readonly int _capacity;
    // Dictionary: ключ -> узел в связном списке
    private readonly Dictionary<TKey, LinkedListNode<(TKey, TValue)>> _cache;
    // Двусвязный список: (ключ, значение)
    // Самый свежий элемент в конце (Last), самый старый в начале (First)
    private readonly LinkedList<(TKey, TValue)> _list;

    public LRUCache(int capacity)
    {
        if (capacity <= 0)
            throw new ArgumentException("Capacity must be greater than 0");

        _capacity = capacity;
        _cache = new Dictionary<TKey, LinkedListNode<(TKey, TValue)>>(capacity);
        _list = new LinkedList<(TKey, TValue)>();
    }

    /// <summary>
    /// Получить значение по ключу (O(1))
    /// </summary>
    public bool TryGet(TKey key, out TValue value)
    {
        if (_cache.TryGetValue(key, out var node))
        {
            // Перемещаем элемент в конец (самый свежий)
            _list.Remove(node);
            var newNode = _list.AddLast(node.Value);
            _cache[key] = newNode;

            value = node.Value.Item2;
            return true;
        }

        value = default;
        return false;
    }

    /// <summary>
    /// Добавить или обновить значение (O(1))
    /// </summary>
    public void Put(TKey key, TValue value)
    {
        // Если ключ уже существует, обновляем его
        if (_cache.TryGetValue(key, out var node))
        {
            // Удаляем старый узел
            _list.Remove(node);
        }

        // Добавляем новый узел в конец (самый свежий)
        var newNode = _list.AddLast((key, value));
        _cache[key] = newNode;

        // Если превышена ёмкость, удаляем самый старый (из начала)
        if (_cache.Count > _capacity)
        {
            var leastRecent = _list.First;
            _list.RemoveFirst();
            _cache.Remove(leastRecent.Value.Item1);
        }
    }

    public int Count => _cache.Count;
    public int Capacity => _capacity;
}

---

Полная реализация с обработкой ошибок

public class LRUCache<TKey, TValue> where TKey : notnull
{
    private readonly int _capacity;
    private readonly Dictionary<TKey, LinkedListNode<CacheItem>> _cache;
    private readonly LinkedList<CacheItem> _list;

    private class CacheItem
    {
        public TKey Key { get; set; }
        public TValue Value { get; set; }

        public CacheItem(TKey key, TValue value)
        {
            Key = key;
            Value = value;
        }
    }

    public LRUCache(int capacity)
    {
        if (capacity <= 0)
            throw new ArgumentException("Capacity must be greater than 0", nameof(capacity));

        _capacity = capacity;
        _cache = new Dictionary<TKey, LinkedListNode<CacheItem>>(capacity);
        _list = new LinkedList<CacheItem>();
    }

    /// <summary>
    /// Получить значение (O(1))
    /// </summary>
    public TValue Get(TKey key)
    {
        if (!TryGet(key, out var value))
            throw new KeyNotFoundException($"Key {key} not found in cache");
        return value;
    }

    /// <summary>
    /// Безопасное получение значения (O(1))
    /// </summary>
    public bool TryGet(TKey key, out TValue value)
    {
        if (key == null)
            throw new ArgumentNullException(nameof(key));

        if (!_cache.TryGetValue(key, out var node))
        {
            value = default;
            return false;
        }

        // Перемещаем элемент в конец (самый свежий)
        _list.Remove(node);
        var newNode = _list.AddLast(node.Value);
        _cache[key] = newNode;

        value = node.Value.Value;
        return true;
    }

    /// <summary>
    /// Добавить или обновить (O(1))
    /// </summary>
    public void Put(TKey key, TValue value)
    {
        if (key == null)
            throw new ArgumentNullException(nameof(key));

        // Если ключ уже существует, обновляем его
        if (_cache.TryGetValue(key, out var existingNode))
        {
            _list.Remove(existingNode);
            _cache.Remove(key);
        }

        // Добавляем новый элемент в конец
        var newItem = new CacheItem(key, value);
        var newNode = _list.AddLast(newItem);
        _cache[key] = newNode;

        // Если превышена ёмкость, удаляем самый старый
        if (_cache.Count > _capacity)
        {
            var leastRecent = _list.First;
            _list.RemoveFirst();
            _cache.Remove(leastRecent.Value.Key);
        }
    }

    /// <summary>
    /// Удалить элемент (O(1))
    /// </summary>
    public bool Remove(TKey key)
    {
        if (key == null)
            throw new ArgumentNullException(nameof(key));

        if (!_cache.TryGetValue(key, out var node))
            return false;

        _list.Remove(node);
        _cache.Remove(key);
        return true;
    }

    /// <summary>
    /// Очистить кэш
    /// </summary>
    public void Clear()
    {
        _cache.Clear();
        _list.Clear();
    }

    /// <summary>
    /// Проверить наличие ключа (O(1))
    /// </summary>
    public bool Contains(TKey key) => _cache.ContainsKey(key);

    public int Count => _cache.Count;
    public int Capacity => _capacity;
}

---

Пример использования

class Program
{
    static void Main()
    {
        var cache = new LRUCache<int, string>(2);

        Console.WriteLine("=== Пример 1: Базовое использование ===");
        cache.Put(1, "one");
        cache.Put(2, "two");
        Console.WriteLine($"Get(1): {cache.Get(1)}");  // "one"
        // Состояние: [2, 1] (1 в конце - самый свежий)

        cache.Put(3, "three");  // Удаляет 2
        Console.WriteLine($"Contains(2): {cache.Contains(2)}");  // false
        Console.WriteLine($"Count: {cache.Count}");  // 2
        // Состояние: [1, 3]

        Console.WriteLine("\n=== Пример 2: Обновление элемента ===");
        cache.Clear();
        cache.Put(1, "one");
        cache.Put(2, "two");
        cache.Put(1, "ONE");  // Обновляем 1
        // Состояние: [2, 1]
        Console.WriteLine($"Get(2): {cache.Get(2)}");  // "two" (2 теперь в конце)
        // Состояние: [1, 2]

        cache.Put(3, "three");  // Удаляет 1 (самый старый)
        Console.WriteLine($"Contains(1): {cache.Contains(1)}");  // false

        Console.WriteLine("\n=== Пример 3: Полный цикл ===");
        cache.Clear();
        cache.Put(1, "a");
        cache.Put(2, "b");
        Console.WriteLine($"Get(1): {cache.Get(1)}");  // "a", 1 теперь в конце
        cache.Put(3, "c");  // Удаляет 2 (самый старый)
        
        if (cache.TryGet(2, out _))
            Console.WriteLine("Get(2): found");
        else
            Console.WriteLine("Get(2): not found");  // "not found"

        Console.WriteLine("\n=== Пример 4: Обработка ошибок ===");
        try
        {
            _ = cache.Get(999);  // KeyNotFoundException
        }
        catch (KeyNotFoundException ex)
        {
            Console.WriteLine($"Exception: {ex.Message}");
        }

        if (cache.TryGet(999, out var value))
            Console.WriteLine($"Value: {value}");
        else
            Console.WriteLine("Key 999 not found (safe way)");
    }
}

Вывод:

=== Пример 1: Базовое использование ===
Get(1): one
Contains(2): False
Count: 2

=== Пример 2: Обновление элемента ===
Get(2): two
Contains(1): False

=== Пример 3: Полный цикл ===
Get(1): a
Get(2): not found

=== Пример 4: Обработка ошибок ===
Exception: Key 999 not found in cache
Key 999 not found (safe way)

---

Анализ сложности

---

Альтернатива: Использование OrderedDictionary

В .NET 6+ можно использовать OrderedDictionary, но это менее прозрачно и медленнее для LRU:

// ❌ Менее эффективно для LRU
var ordered = new OrderedDictionary<TKey, TValue>();
// Проблема: удаление и переинсерт - не O(1)

---

Расширенная реализация: Потокобезопасность

public class ThreadSafeLRUCache<TKey, TValue> where TKey : notnull
{
    private readonly LRUCache<TKey, TValue> _cache;
    private readonly ReaderWriterLockSlim _lock;

    public ThreadSafeLRUCache(int capacity)
    {
        _cache = new LRUCache<TKey, TValue>(capacity);
        _lock = new ReaderWriterLockSlim();
    }

    public bool TryGet(TKey key, out TValue value)
    {
        _lock.EnterReadLock();
        try
        {
            return _cache.TryGet(key, out value);
        }
        finally
        {
            _lock.ExitReadLock();
        }
    }

    public void Put(TKey key, TValue value)
    {
        _lock.EnterWriteLock();
        try
        {
            _cache.Put(key, value);
        }
        finally
        {
            _lock.ExitWriteLock();
        }
    }

    public void Dispose() => _lock?.Dispose();
}

---

Юнит-тесты

using Xunit;

public class LRUCacheTests
{
    [Fact]
    public void Put_And_Get_Returns_Correct_Value()
    {
        var cache = new LRUCache<int, string>(2);
        cache.Put(1, "one");
        Assert.Equal("one", cache.Get(1));
    }

    [Fact]
    public void Exceeding_Capacity_Removes_Least_Recently_Used()
    {
        var cache = new LRUCache<int, string>(2);
        cache.Put(1, "one");
        cache.Put(2, "two");
        cache.Put(3, "three");
        Assert.False(cache.Contains(1));
        Assert.True(cache.Contains(2));
        Assert.True(cache.Contains(3));
    }

    [Fact]
    public void Get_Updates_Recent_Usage()
    {
        var cache = new LRUCache<int, string>(2);
        cache.Put(1, "one");
        cache.Put(2, "two");
        cache.Get(1);  // 1 становится самым свежим
        cache.Put(3, "three");  // Удаляет 2, а не 1
        Assert.False(cache.Contains(2));
        Assert.True(cache.Contains(1));
    }

    [Fact]
    public void Updating_Existing_Key_Moves_To_End()
    {
        var cache = new LRUCache<int, string>(2);
        cache.Put(1, "one");
        cache.Put(2, "two");
        cache.Put(1, "ONE");  // Обновляем 1
        cache.Put(3, "three");  // Удаляет 2, а не 1
        Assert.False(cache.Contains(2));
        Assert.True(cache.Contains(1));
    }

    [Fact]
    public void TryGet_Returns_False_For_Missing_Key()
    {
        var cache = new LRUCache<int, string>(2);
        Assert.False(cache.TryGet(999, out _));
    }
}

---

Выводы

✅ LRU Cache решает:

1. Быстрый доступ к последним использованным данным
2. Ограничение памяти фиксированной ёмкостью
3. Автоматическое вытеснение старых элементов

✅ Использование:

• CPU L1/L2 кэши (hardware)
• Web browser caches
• Database query caches
• Redis (LRU eviction policy)
• CDN кэширование

✅ Комплексность:

• Хорошее знание Dictionary и LinkedList
• Понимание трейдоффов между памятью и скоростью
• Реальный применение в production системах