What data structures are commonly used for LRU caches and quickly locating objects?

Question

I intended to implement a HashTable to locate objects quickly which is important for my application.

However, I don't like the idea of scanning and potentially having to lock the entire table in order to locate which object was last accessed. Tables could be quite large.

What data structures are commonly used to overcome that?

e.g. I thought I could throw objects into a FIFO as well as the cache in order to know how old something is. But that's not going to support an LRU algorithm.

Any ideas? how does squid do it?

Lysimachus

Great question. A frequently needed data structure whose implementation is more tricky than it seems... – Gussi

Answer 1

Linked lists are good for LRU caches. For indexed lookups inside the linked list (to move the entry to the most recently used end of the linked list), use a HashTable. The least recently used entry will always be last in the linked list.

Kamalakamaria

I wouldn't really agree here- traversing the list is gonna be a bitch. – Save

@DeadMG: Do you necessarily need to traverse the list? – Clem

@DeadMG: No need to traverse the list. – Kamalakamaria

@Kamalakamaria If your linked list was double linked, there's no need to traverse it. justUsed->prev->next = justUsed->next; justUsed->next->prev = justUsedPrev; justUsed->next = head; justUsed->prev = null; head = justUsed. However, if your linked list is singly linked, you must traverse the list to find the node just before justUsed to mend the hole when justUsed is moved to the head. – Suffumigate

Answer 2

You might find this article on LRU cache implementation using STL containers (or a boost::bimap-based alternative) interesting. With STL, basically you use a combination of a map (for fast key-value lookup) and a separate list of keys or iterators into that map (for easy maintenance of access history).

Kall