2 ms·

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 https://news.y

• leiroigh 8y ago
  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.
  • HenryR 8y ago
    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.