Tag Info

New answers tagged

2

The expected effort to find $k$ distinct collisions on an ideal hash function of output size $n$ is about $\sqrt{2k} \cdot 2^{n/2} = \sqrt{k2^{n+1}}$ (for $k << 2^{n/2}$). One way to see this is to look at the probability of the outputs of two distinct inputs colliding, which is $2^{-n}$; if we generate outputs for $\sqrt{2k} \cdot 2^{n/2}$ distinct ...


2

Yes they are called Perfect hash functions on wiki. If you follow the link at the bottom of the page there are links to articles and source code. Logically they do not have fixed length output.


0

Yes they are called Perfect hash functions on wiki iv also seen them being called collision free hash functions. If you follow the link at the bottom of the page there are links to articles and source code.


8

This is impossible for any generally useful hash: a hash must map all inputs to a fixed-length output, but you normally want to be able to take variable (and fairly long) inputs. The problem is that there are more inputs than outputs: you normally want to be able to hash any string up to a fairly big length, but the hash itself should not be too long, and ...



Top 50 recent answers are included