I always take the uniformity of hash output as a given and didn't think much of it. Now I am kind of curious, how does good hash function like sha guarantees output uniformity.
Intuitively, given 1:1 input cardinality to output cardinality, the same amount distribution that has high entropy (uniform) in hash output must be equal to the amount of distribution that has low entropy in hash output.
So that means approximately 50% of the possible input distribution will experience less uniformity after hashing.
This cannot be right, can someone point out where my logic is wrong? And guide me on the how good hash function output uniformity for any random distribution?
Edit:
I realize my question is a bit ambiguous, so I think I should try to clarify.
For simplification assuming sha1 is a function that map Integer 2^64 -> Integer 2^64
My question is that given a stream of n random number where n << 2^62, the uniformity property of good hash function (eg. sha1) will redistribute these n number uniformly on a number line [0, 2^k] such that the space between each number is roughly equal (uniformly distributed on a number line).
My first impression is that its not always possible.
If you conduct this experiment multiples times (say m times) where each experiment is to supply n random number and calculate how uniformly distributed the output is on the number line. You will see approximately 50% (or m/2 ) of the experiment to be less uniform and 50% of experiment to be more uniform.
I think my intuition is wrong, but I don't know where is it wrong.
