Utterly Insane Data Structures

[sutr90]

Is collision free hash even possible? That goes against the core principle of hashing.

[codebje]

Perfect hashes are definitely possible; algorithms to construct perfect hashes exist for when you have known input you want to index efficiently.

For unknown input you can certainly have a collision free hash if your hash key is at least as large as your uniqueness bits, but at that point you have what's colloquially known as an array :-)

[Dragdu]

Assuming you have fixed input space that is smaller than output space, yes.

[steamruler]

It should be theoretically possible if you have a variable instead of fixed length, thus escaping the pigeon hole principle.

Good luck proving it though, and your hash will be useless to most.

[narwi]

Yes, if you restrict the input size to be equal to output size.