This hash table uses less space than the items it stores

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

  • by bicsi on 10/10/2022, 1:47:18 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/2022, 1:48:22 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/2022, 6:04:13 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/2022, 8:39:30 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/2022, 8:37:06 AM

    This is just a classic combination of trie with hashmap.