해싱 - LRU Cache

LRU cache

LRU cache (Least Recently Used cache) 는 일정한 capacity를 정해두고 최근에 참조(lookup) 나 삽입(insert) 된 것을 Most Recently Used entry 로서 삭제 순위를 가장 후순위로 보내는 캐시를 말한다. 이 캐시로서 dict 등의 해시 테이블 자료구조가 쓰일 수 있다. 왜냐하면 O(1) 시간만에 참조와 변경을 할 수 있기 때문이며, 쓰이지 않는 기록은 자연히 삭제의 선순위로 밀려 새로운 key가 들어올때 쫒겨나기 때문이다.

구현

capacity를 주고 queue를 이용해서 LRUCache를 구현하되 lookup(key) 해도 키가 없으면 -1을, erase(key) 할때 key가 있으면 True 없으면 False를 돌려주며, insert(key, value) 시에는 만일 기존의 값이 있다면 그 값을 업데이트 하지 않고 삭제 큐의 맨 후순위로 보낸다.

class LRUCache:
    def __init__(self, capacity):
        self._capacity = capacity
        self._entry = collections.OrderedDict()   # Hash table with Queue property
    
    def lookup(self, key):
        if key not in self._entry:
            return -1
        # Send the looked up key to the front
        result = self._entry.pop(key)             # Hash table allows pop operation
        self._entry[key] = result
        return result
        
    def insert(self, key, val):
        # If we already have it, we don't update but just move to front
        if key in self._entry:
            val = self._entry.pop(key)
        # In case of overcapacity, evict LRU entry
        elif len(self._entry) >= self._capacity:
            self._entry.popitem(last=False)   # key-value pair, pop the oldest (first) item
        self._entry[key] = val     # Insert the key-value at the rear of queued hash
    
    def erase(self, key):
        if key in self._entry:
            self._entry.pop(key)
            return True
        else:
            return False