LRU Cache: ابنِ كاش بيرمي الأقل استخدامًا في O(1)
المستوى: متوسط. الافتراض إنك تعرف الـ HashMap والـ Linked List، وتقدر تقرأ كود JavaScript بسيط. لو لسه مبتدئ خالص، المثال اللي تحت هيوصّلك الفكرة قبل الكود.
لو الـ API بتاعك بيضرب الـ database في كل request لنفس البيانات، انت بتدفع زمن استجابة زيادة على الفاضي. الـ LRU Cache بيخزّن أكتر البيانات طلبًا في الذاكرة، ويطرد الأقل استخدامًا أوتوماتيك لما يمتلئ. والكلام ده كله بيحصل في O(1) لكل عملية قراءة أو كتابة.
المشكلة باختصار
عندك endpoint بيرجّع بروفايل مستخدم. كل قراءة من الـ database بتاخد حوالي 12 مللي ثانية. ولو 50 ألف request في الدقيقة بيطلبوا نفس آلاف المستخدمين النشطين، انت بتعيد نفس الـ query آلاف المرات. الحل البديهي: خزّن النتيجة في الذاكرة. المشكلة الحقيقية مش "ازاي أخزّن"، هي "ازاي أرمي". الذاكرة محدودة، فلازم سياسة تقرر مين العنصر اللي يطلع لما المكان يخلص. وهنا بييجي دور LRU.
المثال الأول: مكتبك الصغير
تخيّل مكتب صغير يسع 4 ورقات بس. كل ورقة تستخدمها بتحطها فوق الكومة. لما تيجي ورقة جديدة والمكتب مليان، بترمي الورقة اللي تحت خالص — دي اللي عدّى عليها أطول وقت من غير ما تلمسها. ده بالظبط اللي بيعمله LRU: Least Recently Used، يعني "الأقل استخدامًا حديثًا" هو أول واحد يتطرد.
الفكرة الذكية إن "استخدام" العنصر بينقله لأول الصف تاني. يعني العناصر اللي بتتطلب كتير بتفضل عايشة، واللي اتنسي بيغرق لتحت لحد ما يتشال.
الشرح العلمي: ليه HashMap مش كفاية لوحده
عايز عمليتين في O(1): الوصول لأي عنصر بمفتاحه، ومعرفة مين الأقدم علشان تطرده. الـ HashMap بيديك الوصول في O(1)، بس مش بيحفظ ترتيب آخر استخدام. والقائمة المترابطة (Linked List) بتحفظ الترتيب، بس البحث فيها O(n).
الحل إنك تدمج الاتنين: HashMap بيربط المفتاح بالـ node بتاعه، وDoubly Linked List بيحفظ ترتيب الاستخدام. أي get بيوصل للـ node عن طريق الـ HashMap في O(1)، وبيحرّكه لأول القائمة في O(1) كمان لإنك ماسك مؤشراته. الطرد بياخد الـ node اللي في آخر القائمة، وكمان O(1).
الكود: نسخة شغّالة في JavaScript
في JavaScript فيه اختصار جميل: الـ Map بيحفظ ترتيب الإدخال أصلًا. يعني تقدر تستغني عن بناء الـ Doubly Linked List بإيدك، وتحصل على LRU كامل في سطور قليلة. ده شغّال على Node 22.
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map(); // Map بيحافظ على ترتيب الإدخال
}
get(key) {
if (!this.map.has(key)) return -1;
const val = this.map.get(key);
this.map.delete(key); // شيله من مكانه
this.map.set(key, val); // وحطه في الآخر = الأحدث استخدامًا
return val;
}
put(key, val) {
if (this.map.has(key)) {
this.map.delete(key);
} else if (this.map.size >= this.capacity) {
const lru = this.map.keys().next().value; // أقدم مفتاح
this.map.delete(lru); // اطرد الأقل استخدامًا
}
this.map.set(key, val);
}
}
const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
cache.get("a"); // 1 → "a" بقى الأحدث
cache.put("c", 3); // المكان خلص → يطرد "b" (الأقدم)
console.log(cache.get("b")); // -1 (اتطرد)
console.log(cache.get("a")); // 1
console.log(cache.get("c")); // 3