3 ms·

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

by 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