كيف تصمم ذاكرة تخزين مؤقت LRU مع O(1) للحصول والوضع؟

Question

Accepted Answer

ذاكرة التخزين المؤقت **LRU (الأقل استخدامًا مؤخرًا)** تزيل العنصر الذي لم يتم الوصول إليه لأطول وقت عند الوصول للسعة. يجمع التصميم الكلاسيكي بين **خريطة hash** (بحث O(1)) و**قائمة مرتبطة بشكل مزدوج** (إعادة ترتيب O(1))، مما يعطي **O(1) للحصول والوضع**. ## تصميم البنية الثنائية ```text HashMap: key -> node DLL (recency order): MRU <-> ... <-> LRU get/put: map finds node move touched node to front (MRU) in O(1); DLL splices it evict the tail (LRU) when full to the front in O(1) ``` ## الكود ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cap = capacity self.cache = OrderedDict() # preserves access order def get(self, key): # O(1) if key not in self.cache: return -1 self.cache.move_to_end(key) # mark as most recently used return self.cache[key] def put(self, key, value): # O(1) if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.cap: self.cache.popitem(last=False) # evict least recently used ``` `OrderedDict` هي في حد ذاتها خريطة hash بالإضافة إلى قائمة مرتبطة بشكل مزدوج، بالضبط البنية الموصوفة أعلاه. | العملية | الوقت | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## لماذا القائمة المرتبطة بشكل مزدوج تتيح لك القائمة المرتبطة بشكل مزدوج **فصل عقدة من المنتصف في O(1)** (لديك `prev`/`next`)، وهو مستحيل مع قائمة مرتبطة بشكل واحد أو مصفوفة بدون إزاحة O(n). ## لماذا يأتي الآن تجلس ذاكرات التخزين المؤقت LRU أمام قواعد البيانات وخوادم الويب ووحدات المعالجة المركزية للحفاظ على البيانات الساخنة سريعة والذاكرة محدودة. هذه المشكلة تقليدية في مقابلات كبار المهندسين لأنها تختبر دمج هيكلين بحيث *يغطي كل منهما ضعف الآخر* - مهارة تصميم النظام الرئيسية.