What's a performant data-structure to retrieve the most-commonly-retrieved value, from a small set of values, very fast?

user_31897 0
Viewed 22

I need to cache a map of "seen version IDs" -> "MD5 of that version-id."

For instance,

{
   "version/20220531-0200-1822-g296fa0290a3": "933cbfc50909025f57d6434ec593461c",
   "version/20211215-0200-1900-99046b102fdb": "2aa036d04e42086e9f7d7a7f0bdfe812"
}

This list should only ever contain a few entries; a very small data-structure — but retrieving the most-commonly-accessed entry should be absolutely blazing-fast.

Obviously the past of least resistance is using a standard-library Hashtbl or just an array and string-comparison; but I'm hoping I can do better than that — and learn a little about data-structures in the process.

Is there some sort of self-sorting-by-access-frequency data-structure that would be ideal for this?

data-structures hashtable
1 Answers

Try using a heap keyed on the number of times an element has been looked up. It's designed for O(constant) lookup time, O(log n) deletion and insertion. It has great memory locality and is about the fastest you can get.

In general though, with small N the asymptotic runtime of a data structure becomes less relevant compared to various overheads of the specific implementations of the data structures or its use case.

user_72910510
Related