[HN Gopher] Lessons from Hash Table Merging
___________________________________________________________________
Lessons from Hash Table Merging
Author : attractivechaos
Score : 73 points
Date : 2026-01-02 12:51 UTC (6 days ago)
(HTM) web link (gist.github.com)
(TXT) w3m dump (gist.github.com)
| willvarfar wrote:
| Kudos, neat digging and writeup that makes us think :)
|
| If you merge linear probed tables by iterating in sorted hash
| order then you are matching the storage order and can congest
| particular parts of the table and cause the linear probing worse
| case behaviour.
|
| By changing the iteration order, or salting the hash, you can
| avoid this.
|
| Of course chained hash tables don't suffer from this particular
| problem.
|
| My quick thought is that hash tables ought keep an internal salt
| hidden away. This seems good to avoid 'attacks' as well as
| speeding up merging etc. The only downside I can think of is that
| the creation of the table needs to fetch a random salt that might
| not be quick, although that can alleviated by allowing it to be
| set externally in the table creation so people who don't care can
| set it to 0 or whatever. What am I missing?
| kzrdude wrote:
| Having a per-table key for the hash function is what siphash
| authors propose and what many do to combat dos attacks right?
| For example Rust's default HashMap.
|
| The keys are hidden/secret to the system external to the
| application.
| oleggromov wrote:
| There's a typo with 'ULL' string suffixes in the hexadecimal
| numbers in the first code example.
| rurban wrote:
| No, 0xd6e8feb86659fd93ULL is a valid unsigned long long number.
| With stdint.h you'd get portable suffix macros, which would
| help on non-Windows, but they do look worse.
| oleggromov wrote:
| Oh wow, my apology - didn't know that and didn't notice the
| length of the hexademical number. TIL.
| tialaramex wrote:
| 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.
| OskarS wrote:
| > 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.
|
| Are you sure? I'm not very used to reading Rust stdlib, but
| this seems to be the implementation of the default HashMap
| extend [1]. It just calls self.base.extend. self.base seems to
| be hashbrown::hash_map, and this is the source for it's extend
| [2]. In other words, does exactly the same thing, just iterates
| through hash map and inserts it.
|
| Maybe I'm misreading something going through the online docs,
| or Rust does the "random seed" thing that abseil does, but just
| blinding assuming something doesn't happen "because Rust" is a
| bit silly.
|
| [1]: https://doc.rust-
| lang.org/src/std/collections/hash/map.rs.ht...
|
| [2]:
| https://docs.rs/hashbrown/latest/src/hashbrown/map.rs.html#4...
| tialaramex wrote:
| Yes, HashMap will by default be randomly seeded in Rust, but
| also the code you linked intelligently reserves capacity. If
| h0 is empty, it reserves enough space for all of h1, and if
| it isn't then it reserves enough extra space for half of h1,
| which turns out to be a good compromise.
|
| Note that the worst case is we ate a single unneeded growth,
| while the best case is that we avoided N - 1 grows where N
| may be quite large.
| attractivechaos wrote:
| First of all, as khuey pointed out, the current
| implementation accumulates values. extend() replaces values
| instead. It wouldn't achieve the same functionality.
|
| I tried extend() anyway. It didn't work well. Based on your
| description, extend() implements a variation of
| preallocation (i.e. Solution II). However, because it
| doesn't always reserve enough space to hold the merged hash
| table, clustering still happens depending on N. I have
| updated the rust implementation (with the help of LLM as I
| am not a good rust programmer). You can try it yourself
| with "ht-merge-rust 1 -e -n14m" or point out if I made
| mistakes.
|
| > _HashMap will by default be randomly seeded in Rust_
|
| Yes, so it is with Abseil. The default rust hash functions,
| siphash in the standard library and foldhash in hashbrown,
| are ~3X as slow in comparison to simple hash functions on
| pure insertion load. When performance matters, we will use
| faster hash functions at least for small keys and will need
| a solution from my post.
|
| > _In a new enough C++ in theory you might find the same
| functionality supported, but Quality of Implementation
| tends to be pretty frightful._
|
| This is not necessary. The rust libraries are a port of
| Abseil, a C++ library. Boost is as fast as Rust.
| Languages/libraries should learn from each other, not fight
| each other.
| tialaramex wrote:
| > First of all, as khuey pointed out, the current
| implementation accumulates values. extend() replaces
| values instead. It wouldn't achieve the same
| functionality.
|
| Ah! Yes, I apologise. I missed the + in += and I'm not
| used to a hash table which defaults initialization for
| unseen entries (as the C++ hash tables all tend to
| because its native container types behave that way) so I
| wasn't looking for it.
|
| The SipHash will be noticeably slower, no question about
| it, and so if you need to and know what you're paying you
| can replace the hash, including with integer_hasher which
| gives you what you'd likely know from many C++ stdlib
| implementations - an identity function presented as a
| hash.
|
| > This is not necessary. The rust libraries are a port of
| Abseil, a C++ library.
|
| More specifically HashBrown is a port [edited: actually a
| re-implementation I think, design->Rust not C++->Rust] of
| Abseil's Swiss Tables, and these days Rust's HashMap (and
| HashSet of course) use HashBrown but that's not what I
| was getting at here
|
| I was thinking about analogues of Extend (because as I
| wrote above, I didn't notice that you're accumulating not
| overwriting) and modern C++ _has_ this kind of feature in
| Ranges::to however it doesn 't quite have Extend and as I
| said QoI is poor, there are often trivial optimisations
| that Rust does but the C++ means the same but isn't
| optimised.
|
| I am interested in a quite different benchmark for hash
| tables, rather than merging I'm interested in very small
| hash tables. Clearly for two items it will be faster to
| try them both, and clearly for a million items trying
| them all is awful, so I measure a VecMap type (same API
| as a hash table but actually just the growable array of
| unordered key->value pairs, searched linearly) against
| HashMap and other implementations of this API.
|
| For N=25 VecMap is still competitive, but even at N=5 if
| we use a very fast hash (such as that identity function)
| instead of SipHash we can beat VecMap for most
| operations. I suspect this sort of benchmark would fare
| very differently on older hardware (faster memory
| relative to ALU operations) and the direction of travel
| is likely to stay the same for the foreseeable future. In
| 1975 if you have six key->value pairs you don't want a
| hash table because it's too slow but in 2025 you probably
| do.
| khuey wrote:
| 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.
| jesse__ wrote:
| > 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
| information about the problem I'm trying to solve than the
| author of a hashtable library, and am therefore much better
| equipped to make design decision tradeoffs.
|
| Please stop perpetuating the idea that 'just use a library' is
| unilaterally the best option. Sometimes, it's not.
| tialaramex wrote:
| 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.
| jesse__ wrote:
| Great, we can agree on those :)
| exDM69 wrote:
| Maybe this would be a suitable application for "Fibonacci
| hashing" [0][1], which is a trick to assign a hash table bucket
| from a hash value. Instead of just taking the modulo with the
| hash table size, it first multiplies the hash with a constant
| value 2^64/phi where phi is the golden ratio, and then takes the
| modulo.
|
| There may be better constants than 2^64/phi, perhaps some large
| prime number with roughly equal number of one and zero bits could
| also work.
|
| This will prevent bucket collisions on hash table resizing that
| may lead to "accidentally quadratic" behavior [2], while not
| requiring rehashing with a different salt.
|
| I didn't do detailed analysis on whether it helps on hash table
| merging too, but I think it would.
|
| [0] https://probablydance.com/2018/06/16/fibonacci-hashing-
| the-o... [1] https://news.ycombinator.com/item?id=43677122 [2]
| https://accidentallyquadratic.tumblr.com/post/153545455987/r...
| SkiFire13 wrote:
| > This will prevent bucket collisions on hash table resizing
|
| Fibonacci hashing is really adding another multiplicative
| hashing step followed by dropping the bottom bits using a shift
| operation instead of the top bits using an and operation. Since
| it still works by dropping bits, items that were near before
| the resize will still be near after the resize and it won't
| really change anything.
| attractivechaos wrote:
| Exactly. And khashl uses Fibonacci hashing. Without salting,
| it has the same problem.
| SkiFire13 wrote:
| > I evaluated the following hash table libraries, all based on
| linear probing.
|
| > Abseil
|
| > Rust standard
|
| > hashbrown
|
| These hash tables are not based on plain linear probing, they use
| something that's essentially quadratic probing done in chunks.
| Not sure about the others but they might be doing something
| similar.
| attractivechaos wrote:
| These three and boost are all based on swiss tables. They are
| indeed more robust than plain linear probing. khashl is the
| only one here using basic linear probing. Without salting, its
| curve is through the roof, much worse than swiss tables.
___________________________________________________________________
(page generated 2026-01-08 23:01 UTC)