2 ms·
The O(n) behavior is not even really that 'pathological', lots of normal cases get that behavior. If SwissTable operates as you say, then it sounds like it is p
by veltas 5y ago
The O(n) behavior is not even really that 'pathological', lots of normal cases get that behavior. If SwissTable operates as you say, then it sounds like it is prone to bad performance for lots of normal data with a dumb hash, i.e. as a "Set" on numbers where the hash is the identity function (a valid hash for a closed bucket hash table), and many of the numbers are next to each other.
Therefore, much like the situation I described in my parent post, SwissTable would benefit from being used with a decent pseudo-random hash. Which is no trouble, there are a number of good, fast ones.
- ziml77 5y agoSwiss tables are part of Abseil and Abseil provides its own hashing library. I haven't looked into the details of the implementation, but by default it's not using the identity function for ints. These are the first few hashes it generates for int inputs: 0: 918782482972292171 1: 12294850989704472498 2: 5224175424757160222 3: 16600243932558888071 4: 9529568361303343081 5: 2458892796473463123 6: 13834961304296162488 7: 6764285737197172256 8: 18140354246076836247 9: 11069678680190000369 10: 3999003117507595883
- tialaramex 5y agoYes, Swisstables explicitly require you to use a decent hash. If you insist on using a bad hash, you get terrible performance, so, don't. Google internally (I didn't check Abseil) has diagnostics so they just flag that the problem with your Swisstable is that you used a bad hash and save engineers wasting their time "investigating" this non-problem. Rust's HashMap (which is a Swisstable reimplementation) chooses a SipHash 1-3 by default but you can drop in anything you want, just with the knowledge that if your hash is bad your HashMap will have lousy performance.