Lessons from Hash Table Merging • Hacker News Board

Re: Lessons from Hash Table Merging

#21

Post by jesse__ » Thu, Jan 08, 2026, 10:43 PM UTC

tialaramex wrote: post #20

jesse__ wrote: post #18

Earlier quoted context omitted.

> the people who made your HashMap type are much better equipped to optimize ... Who's to say I'm not the one making the hashtable? There are plenty of real-world reasons the standard library hashtable may be either inaccessible or unsuitable. Furthermore, the idea that "oh, honey, it's too hard, smart people did it for you" is insufferable and needs to die. When I'm the one making something, I have dramatically more…

If you made your own type, you should implement Extend. It seems you agree that in this case you are best placed to do a good job. And indeed if you have your own custom operation you want, it may well make sense for you to implement it on both your own types and stdlib types.

Great, we can agree on those :)

Re: Lessons from Hash Table Merging

#22

Post by tialaramex » Thu, Jan 08, 2026, 11:56 PM UTC

khuey wrote: post #15

tialaramex wrote: post #4

In Rust, don't do this, it's more work and it'll tend to be slower, often much slower. HashMap implements Extend, so just h0.extend(h1) and you're done, the people who made your HashMap type are much better equipped to optimize this common operation. In a new enough C++ in theory you might find the same functionality supported, but Quality of Implementation tends to be pretty frightful.

From skimming the source code it looks like the merge operation here adds the values for duplicated keys rather than replacing the first value with the second value so using HashMaps's Extend impl won't work.

Thanks, I missed that

Re: Lessons from Hash Table Merging

#23

Post by AlotOfReading » Fri, Jan 09, 2026, 1:41 AM UTC

This easier to solve if you use a permutation instead of hash functions.

Let h0 be the larger table, and h1 the smaller. N = len(h0), M = len(h1). Pretend the elements of the tables are sequentially indexed. Element[0] is h0[0], Element[N] is h1[0], etc.

     h0' = Resize(h0, (N+M)*capacity_factor)

    for x in 0...(range):
      y = permute(x, 0, (N+M)*capacity_factor)
      if(y >= N) move_to(h0'[y], element[x])

One allocation and you move the minimum number of elements needed to eliminate primary clustering. Elements in h0 that aren't moved would presumably remain correctly indexed. You have to move the remaining elements of h1 as well, but that cluttered things.

Any randomish permutation works, from basic ones up to cryptographic. If your permutation only works on certain powers of two, iterate it until the result is in range.