Re:Fast Perfect Hashing
by da_chicken on Wednesday February 13, 2019 @02:34PM
(#19156039)
> 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
by gumby on Wednesday February 13, 2019 @04:27PM
(#19157211)
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.
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.