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

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 accesse开发者_运维技巧d. 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?

---

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.

---

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).