I’m reading this article on hashing in Java, and in it it says that
hashing function may lead to collision that is two or more keys are mapped to same value.
In order to avoid this, chain hashing is used.
How come that hashing function can lead to the same value for different keys? I thought that fash function always generates unique value.
>Solution :
A hashing function is just that, a function, taking an input and producing an output. Take any function, for example
H(x) = x mod 10
which is perfectly valid as a function. You’ll notice that for inputs 5, 15, 25 and so on it produces the exact same outputs. The same is true for any other hashing function that produces results from a finite co-domain. In the case of Java, the co-domain is a value from the interval of 32-bit integers: [-2^31, 2^31 - 1].
There are only 2^32 possible outputs, for a potentially infinite number of inputs. And based on the pigeon-hole principle, there are at least two inputs that will produce the same output.