13.4 IMPLEMENT AN ISBN CACHE

Problem description:

Create a cache for looking up prices of books identified by their ISBN. You implement support lookup, insert, and remove methods. Use the Least Recently Used (LRU) policy for cache eviction. If an ISBN si already present, insert should not change the price, but it should update the entry to be the most recently used entry. Lookup should also update that entry to be the most recently used entry.

Hint: Amortize the cost of deletion. Alternatively, use an auxiliary data structure.

Solution:

Once the cache fills up, to add a new entry we have to find the LRU entry, which will be evicted to make place for the new entry. Finding this entry takes O(n) time, where n is the cache size.

One way to improve performance is to use lazy garbage collection. Specifically, let’s say we want the cache to be size of n. We do not delete any entries from the hash table until it grows to 2n entries. At this point we iterate through the entire hash table, and find the median age of items. Subsequently we discard everything below the median. The worst-case time to delete becomes O(n) but it will happen at most once every n operations. Therefore, the amortized time to delete is O(1). The drawback of this approach is the O(n) time needed for some lookups that miss on a full cache, and the O(n) increase in memory.

An alternative is to maintain a separate queue of keys. In the hash table we store for each key a reference to its location in the queue. Each time an ISBN is looked up and is found in the hash table, it is moved to the front of the queue. (This requires us to use a linked list implementation of the queue, so that items in the middle of the queue can be moved to the head.) When the length of the queue exceeds n, when a new element is added to the cache, the item at the tail of the queue is deleted from the cache, i.e., from the queue and the hash table.