CODEWITHSUNDEEP
cachingindexingdata-structureslru
GorgMish
GorgMish

Reputation: 55

How to implement dynamic indexes?

I know, Maybe the title is a little confusing. however, my actual question is basic I think. I'm working on a brand new LRU implementation for that I use an Index Table which maps the name of the incoming packet to index of where the content of packet stored in CS. As illustrated below each incoming packet store in the CS and can be addressed by Index Table. enter image description here

Now suppose new packet arrived, as we know, regarding LRU, its index must set to top of CS (zero) and it needs to upgrade other indexes, they need to be incremented as a result. enter image description here One obvious solution is to loop over all entries in the Index Table and increment them. Is there any solution or structure that is using for such a problem?

Upvotes: 1

Views: 616

Answers (1)

Ayoub Omari
Ayoub Omari

Reputation: 906

I don't see how you are establishing the order of your cache in the description. But to answer your question, it's possible to reduce the LRU store method to O(1) time complexity.

The classical way to do it is to have these two data structures:

  • Doubly Linked List : for order in the cache. Each node stores a data element (it plays the role of your content store).

  • HashMap that associates each key to the pointer to the node in the linked list. (it plays the role of your index table)

So when you access already stored data in your cache, it must be at the top of the list, so you delete the corresponding node from the linked list (in O(1) time because you have access to its previous and next nodes) and store it at the head.

For new data it is simpler, only store it at the head of the list and store your (key, value) in the hashmap.

Upvotes: 2

Related Questions