While very useful, you can only construct a collision-free hash function if you know all possible inputs. Otherwise perfect hash functions can only give guaran

While very useful, you can only construct a collision-free hash function if you know all possible inputs. Otherwise perfect hash functions can only give guarantees over the frequency of collisions. In the more general case, for a hash function with n bits output, the pigeon hole principle demands that we have a collision at least every 2^n inputs.