3 ms·

The OP seems to be confusing terminology. What they construct is a permutation. Everything they say is relevant to permutations, not perfect hashing. In partic

The OP seems to be confusing terminology. What they construct is a permutation. Everything they say is relevant to permutations, not perfect hashing. In particular: > A perfect hash function is one that is collision-free. By implication, the hash must be at least as many bytes as the key This is just false. Perfect hashing is often if not always performed on subsets of the full domain, e.g. the keywords in a programming language.

jandrewrogers 8y ago
It should be obvious here that the domain is e.g. integral types on computers. The term is used in many places to denote collision-free quasi-randomization, which technically is a strict subset of perfect hash functions, and I chose it to align with that common usage.
ot 8y ago
Yeah the terminology is a bit misleading, it would be better to call this a "bijective" or "invertible" integer hash function, or mixer. It's really nice work though! Invertible mixers are usually building blocks for more general hash function, for example MurmurHash3 uses this 64-bit mixer https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp#L81 https://github.com/aappleby/smhasher/blob/master/src/MurmurH... Using this trick could produce a faster murmurhash-type function.
- jandrewrogers 8y ago
  A difference is that most common mixers are not collision-free. For some applications of runtime hashing using ordinary hash functions, where pseudo-randomness is important regardless, being able to prove the hash function is collision-free enables useful optimizations without any prior knowledge of the keys to be hashed. The genesis of this was database internals, which have many use cases for strongly randomized bijective function for integral types. It is used in places where most people would use an ordinary hash function. This particular hash is not trivially invertible, since internal AES state necessary to reverse it is discarded.
  - ot 8y ago
    > A difference is that most common mixers are not collision-free. That is not true, most modern hash implementations use invertible mixers. See Bob Jenkins' notes on hash function design: http://burtleburtle.net/bob/hash/evahash.html#funneling http://burtleburtle.net/bob/hash/evahash.html#funneling

jandrewrogers 8y ago

It should be obvious here that the domain is e.g. integral types on computers. The term is used in many places to denote collision-free quasi-randomization, which technically is a strict subset of perfect hash functions, and I chose it to align with that common usage.

ot 8y ago

Yeah the terminology is a bit misleading, it would be better to call this a "bijective" or "invertible" integer hash function, or mixer. It's really nice work though! Invertible mixers are usually building blocks for more general hash function, for example MurmurHash3 uses this 64-bit mixer https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp#L81 https://github.com/aappleby/smhasher/blob/master/src/MurmurH... Using this trick could produce a faster murmurhash-type function.

jandrewrogers 8y ago
A difference is that most common mixers are not collision-free. For some applications of runtime hashing using ordinary hash functions, where pseudo-randomness is important regardless, being able to prove the hash function is collision-free enables useful optimizations without any prior knowledge of the keys to be hashed. The genesis of this was database internals, which have many use cases for strongly randomized bijective function for integral types. It is used in places where most people would use an ordinary hash function. This particular hash is not trivially invertible, since internal AES state necessary to reverse it is discarded.
- ot 8y ago
  > A difference is that most common mixers are not collision-free. That is not true, most modern hash implementations use invertible mixers. See Bob Jenkins' notes on hash function design: http://burtleburtle.net/bob/hash/evahash.html#funneling http://burtleburtle.net/bob/hash/evahash.html#funneling