Menu
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?
740
An LRU cache is built by combining two data structures: a doubly linked list and a hash map.
LRU Cache implementation in Java The HashMap will hold the key and the reference to the Node of the Doubly Linked List. HashMap data structure is used for O(1) operations on get(key) and put(key, value) . And Doubly Linked List is chosen because it supports fast insertion and deletion of nodes.
One way to implement an LRU cache in Python is to use a combination of a doubly linked list and a hash map. The head element of the doubly linked list would point to the most recently used entry, and the tail would point to the least recently used entry.
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.
81
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).
34
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
