from Hacker News

This hash table uses less space than the items it stores

by williamkuszmaul on 10/9/22, 4:12 PM with 9 comments

  • by bicsi on 10/10/22, 1:47 AM

    Isn’t this just a trie with only two levels? It seems to me that this technique isn’t particularly unknown, as it’s taught in most elementary CS courses.
  • by omegalulw on 10/10/22, 1:48 AM

    Maybe I'm missing something obvious, but if I insert all 32 bit keys, does that not take 32*2^32 space?
  • by perryizgr8 on 10/10/22, 6:04 PM

    Kind of reminds me of a patricia trie, which is used to store routing tables. Each prefix exists as a path you take from one node to the other.
  • by marginalia_nu on 10/10/22, 8:39 AM

    Neat. I have an order-of-gigabytes hash table I'd love to shrink. Will experiment with this technique.
  • by pshirshov on 10/10/22, 8:37 AM

    This is just a classic combination of trie with hashmap.