> If you push a hash table which handles collisions by linear probing that hard, and any non-randomness appears, you can get long runs and are in trouble. I kne

> If you push a hash table which handles collisions by linear probing that hard, and any non-randomness appears, you can get long runs and are in trouble. I knew about Robin Hood hashing, but didn't know it was being used to justify 90% table density. Usually, above 50% full and it's time to double the size of the table. wouldn't non-randomness be an issue for any hash table, regardless of how full it is? doubling it will not make the input more random, theoretically we could have the same slowness whether it's a smaller 90% full table, or a bigger one "just" 45% full - if N things hash to the same loc, we'll have to dig through O(N) spots till we find what we need. i wrote a small hash set for my side project (https://github.com/jbakic/Shielded/blob/master/Shielded/SimpleHashSet.cs https://github.com/jbakic/Shielded/blob/master/Shielded/Simp..., does not need to support removal so it's the dumbest linear probing hash table one could probably imagine), and there i set the limit at 75%, even though i don't use Robin Hood (perhaps i should?), because the lib has to iterate through the whole set at the end of a transaction, at least twice. i know this is not very relevant, a very special use case, but i'm giving it as an example of how a bigger load factor can actually be advantageous. the Shielded lib is overall slower if the load factor limit is set lower. i hope someone more versed in the theory behind all this can add something to this, i'm curious if my thinking really makes sense...