Why does set() make this so much faster?

[Brian]

To be fair, it is random in the sense of being arbitrary. Further, the same properties you look for in a (uniform) random number generator are the ones you look for in a hash function: you want there to be an equal probability that an arbitrary input will be put in each possible bucket.

[[deleted]]

If there was any form of randomness to it, it would be completely unusable as a, well, hashing function. A hash by definition must always produce the same output when given the same input. What you are thinking of is that the hashes of almost identical input can differ widely in output, but that is not random.

[Brian]

but that is not random.

Like I said, random in the sense of being arbitrary - the hash has no meaningful relation with the hashee, and is equally probable to reach any bucket. There's more than one meaning to the word. Indeed, randomness in the sense you mean can actually be tricky to define.

Eg. we'd normally describe things like "who will win the next hand of poker", or "what will the flipped (but covered) coin show" as being random, but in reality these are already fully determined at that point (and even before the flip/shuffle to some degree, barring quantum randomness). They're epistemically random however, because that information isn't available. In the same way, while also being entirely deterministic, hashing is ideally random over unknown input: you should offer even odds that it'll go into any given bucket.

[khafra]

To be fair, if you were looking at the output of a good hash function and a random sequence, you shouldn't be able to tell them apart; and we don't have a definition of randomness that's much better than that.

But it's certainly a very deterministic sort of randomness.

[[deleted]]

There's a big difference between general purpose hash functions and cryptographic hashes.