This article is about integer permutations, not perfect hashing. That said, integer permutations have many nice applications. One is in hash tables with integer keys: one can store the "hash code" in lieu of the key, since permutations are reversible.
Fast Perfect Hashing
41–43 of 43 posts
Re: Fast Perfect Hashing
#42As pointed out by some of you, this looks more like permutation of sequences. Also, since a symmetric cipher is used, I'm surprised the author didn't mention Black and Rogaway [1].
Their algorithm is a permutation (int -> int) that works on a domain of any size up to a limit. A typical application for this is encrypting credit card numbers so that the ciphertext still looks like a credit card number (non-trivial because the size of domain isn't a power of two) or efficiently shuffling sequences, randomly in appearance but repeatably if you know the seed.
For instance, this is used by Masscan to randomize the order in which IP addresses and ports are scanned [2]. I've built a Python package that could help you use this algorithm [3] (mostly for fun, but maybe that's useful, let me know :)).
[1]: https://en.wikipedia.org/wiki/Format-preserving_encryption#T... [2]: https://github.com/robertdavidgraham/masscan/blob/6c15edc280... [3]: https://github.com/bbc2/shuffled
Re: Fast Perfect Hashing
#43Earlier quoted context omitted.
> 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 t…
It's the lemma I challenge, not the common case on certain of today's architectures. The use of the word "must" implies ∀, which is plainly not the case.
If it is not the case, can you present a counter-example? Can you code it up in say Python?