LRU Cache Tasarımı

LRU (Least Recently Used) cache, en az son kullanılan öğeleri saklayarak bellek kullanımını optimize eden bir veri yapısıdır. Aşağıda LRU cache tasarımının temel bileşenleri ve adımları yer almaktadır.

Bileşenler

• Hash Map: Anahtar-değer çiftlerini hızlıca bulmak için kullanılır.
• Doubly Linked List: Kullanılan öğelerin hangi sırayla kullanıldığını izlemek için gereklidir.

Adımlar

• İlk Oluşturma: Belirli bir kapasite ile bir hash map ve bir doubly linked list oluşturulur.
• Cache\'e Ekleme: Yeni bir öğe eklendiğinde, hash map\'e eklenir ve linked list\'in başına yerleştirilir.
• Cache\'den Silme: Kapasite aşıldığında, linked list\'in sonundaki en eski öğe silinerek hem hash map\'ten hem de linked list\'ten çıkarılır.
• Erişim: Bir öğeye erişildiğinde, öğe linked list\'te başa taşınır ve böylece en çok kullanılan öğeler önde yer alır.

Örnek Algoritma

• put(key, value): Eğer anahtar yoksa ve kapasite doluysa en eski anahtarı sil.
• get(key): Anahtar varsa değerini döndür ve öğeyi en üstteki sona taşı.

Bu temel yapı ile LRU cache; verimlilik ve hız açısından etkili bir şekilde çalışır.