Hacker News Reader

Author here - if you like this you might also like another paper summary of mine in the same vein:

https://news.ycombinator.com/item?id=18132730

So I was wondering... are there sensible structures that combine hashmap and tree by having a double index?

Reason: Ordered access or range queries need a (radix-)tree.

So insertion and removal need to pay for the comparatively slow tree search and rebalancing.

Lookups or mutations could use a hash table that references the same data, especially if no key compression is used for storage.

I don't know of one, but it's such a natural idea that I'd guess it's been studied. There are standard implementations of LRU caches that use e.g. a hash map and a linked list to get both fast lookup and ordering, but for real performance I think you'd want to try and minimise the number of data structures to avoid having competing cache behaviours.

Reply on news.ycombinator.com