Obvious Internals of Ordered Maps

Internals of the most widely known page replacement policy

Ever wondered how databases retrieve the results for the same query much faster the second time the query was executed compared to the first time? We are limited by the RAM and a little bit of disk for our storing structures in-memory, as a result of which we are forced to evict the elements we deem not necessary anymore. How do we find appropriate elements or cached contents and mark them as not necessary?

A widely used policy for this is LRU aka Least Recently Used page replacement algorithm. Implementing an LRU Cache mandates an ordering of elements. We’ll see why and how to accomplish this.

The Need for Ordering

We have hash-maps for a key-value in-memory storage. But HashMaps do not have any sort of ordering. Though not often, there are scenarios where one might need to retrieve the elements in a certain order.

1) Consider an application where items need to be displayed in the UI in a specific order.

2) Or if you’re implementing a LRU (Least Recently Used) cache, you need to keep an ordering based on how recently an element has been accessed.

How do we accomplish this?

Linked Hash Maps to the…