cryptographic hash^
Fast Perfect Hashing
21–30 of 43 posts
Re: Fast Perfect Hashing
#22The 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 programm…
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/MurmurH... Using this trick could produce a faster murmurhash-type function…
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.
Re: Fast Perfect Hashing
#23This article is interesting but... weird. It seems to assume a bunch of things, and then states some conclusions based on that, but then also assumes the value of the conclusions is obvious. > A perfect hash function is one that is collision-free. By implication, the hash must be at least as many bytes as the key and the function is theoretically reversible, though not always tractably so. This is true because of the…
The identity function is a perfect hash function, no quotes needed. Several programming languages uses it as the default function for hashing integers. But it doesn't have a good avalanche which is important for some use cases. You could, for example, use it to make guessing urls harder.
Re: Fast Perfect Hashing
#24> A perfect hash function is one that is collision-free. By implication, the hash must be at least as many bytes as the key I don't understand this lemma. An indexed array is a degenerate example in which the "hash" (pointer) is presumably a lot smaller than the key (index). BTW for those not familiar with a perfect hash function they are great for things like symbol tables that are immutable at runtime. You can make…
> An indexed array is a degenerate example in which the "hash" (pointer) is presumably a lot smaller than the key (index).
No, it isn't.
The "0" in arr[0] is (in most cases) a 32-bit signed integer. If you're using a signed 32-bit int to index your array, you're using a hash length of 32-bits. You won't be able to index more than 2.1 billion unique items without changing your data type. Even if you're not using all those bits, you're still using 32-bits to index them. The fact that you're storing something that may have more than 32 bits of information is irrelevant, because your array (a naive hash) doesn't consider them real values.
If you want to store a set of N elements in an array or perfectly hash a set of N elements, then the set of all possible indexes or hashes must have at least N elements.
Re: Fast Perfect Hashing
#25This article is interesting but... weird. It seems to assume a bunch of things, and then states some conclusions based on that, but then also assumes the value of the conclusions is obvious. > A perfect hash function is one that is collision-free. By implication, the hash must be at least as many bytes as the key and the function is theoretically reversible, though not always tractably so. This is true because of the…
> The author assumes the reader knows the value of randomizing your integer keys. I'm not sure what that value is in cases where you know you don't have collisions anyway.
If you're going to be doing writes of your data in order of an integer sequence number, and you're writing to a multi-node storage system that partitions/shards by primary-key range, then you're going to get worst-case performance if you use your integer sequence numbers directly as the primary keys, since you're queuing all your writes onto one shard.
Instead, you want to permute your integer sequence numbers so that successive integers become evenly spread across the range partitions. This (along with some write duplication and verify-on-read) is the foundation of Dynamo-based "scale-free" storage systems (DynamoDB+S3, Riak+CS, etc.)
Re: Fast Perfect Hashing
#26Earlier quoted context omitted.
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/MurmurH... Using this trick could produce a faster murmurhash-type function…
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 bi…
> 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:
Re: Fast Perfect Hashing
#27A good blog post about xor-shift-multiply reversible hash functions: https://nullprogram.com/blog/2018/07/31/
The inverse functions are easily found by computing the modular inverses of the odd multiplicative factors.
Real perfect hashing is more about hashing a non contiguous set of elements with no collisions, unlike the set of all integers that fit in n bits.
A different problem is Minimal Perfect Hashing. In addition to being injective, the function should have a minimal image of the input set: the set of keys is mapped to consecutive integers without vacant slots.
The implementations in optimal space are non-practical but some libraries construct such functions with a bit more memory (2-3bits/key), like emphf or BBhash (both on github). The latter use a series of 1-hash bloom filters where keys having collision on one layer are removed to be handled by deeper layers. The overall rank() of the bit where a key ultimately lands gives its hash.
Re: Fast Perfect Hashing
#28Seems to accomplish the same purpose as Fibonacci Hashing[0], but with more steps.
[0] https://probablydance.com/2018/06/16/fibonacci-hashing-the-o...
Re: Fast Perfect Hashing
#29This is a nice simple mixing function on newer Intel chips.
But since the XOR doesn't increase entropy, I think you can save a cacheline load of the 0xDEADBEEF constant by passing _mm_setzero_si128() instead of _mm_set1_epi32(0xDEADBEEF).
Re: Fast Perfect Hashing
#30this..seems extremely cool (?) does someone have a reference or pointer for further study about how this is 'perfect' and not just 'really good'
I really dislike posts like this one. For technical stuff like this people should start out with definition so everyone know what the author means by, for example, "perfect hashing".
> By implication, the hash must be at least as many bytes as the key and the function is theoretically reversible
No. At least not by the standard definition[1]. In standard context, the problem of constructing a perfect hash function is, given (ahead of time) a list of items, you find a hash function that can map them to a smaller "range" without collision.