5 ms·
> 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
by gumby 8y ago
> 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 a very fast lookup that requires no probing (bucket size is always one) so you can also eliminate a lot of implementation both of code and data structure.
- bialpio 8y agoIt's smaller than the key, but the size of the domain is the number of items you've put in the array.
- bialpio 8y agoActually, I might have misunderstood you. In your example, the index in the array is treated like the hash of the item you've put in there, why are we suddenly considering pointers?
- foobiekr 8y agoA really common pattern in many programs is to associate metadata with something using a unique key. In cases where you can’t associate that metadata directly using a pointer (by using structures as keys embedding the pointer in the key) or a direct index into a metadata array, a perfect hash generated at build time is about as good as you’re going to get. The other thing is that often this is easy to bolt on after the fact. As an example, in network devices it is common for a syslog mnemonic to be associated with an instance of a rate limiter. A good solution is to compile your log messages using an errmsg definition and compiler tool (which also allows you to build documentation) but this requires a lot of up-front planning and build orchestration and makes the code awkward in sone circumstances. An alternative is that you allow people to declare their mnemonic (and, for example, rate limit) in-place and then allow the logger library to use that to look up other properties that are joined from other sources (if there are any) and glean the structures that need to be created. Since extracting the full set on mnemonics is necessary anyway (for tripwires, for documentation, ...) you can now build the hash function after-the-fact. This definitely simplified the build considerations (and avoids unnecessary rebuilds when, for example, only documentation changes). The after-the-factness-but-with-low-overhead part is what’s nice about it. Yes, it’s better to structure things up front to make the system optimal but it’s nice to be able to get close.
- da_chicken 8y ago> 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.
- gumby 8y agoIt'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.
- da_chicken 8y agoYou're not explaining yourself at all. How do you propose to put 10 pounds of shit in a 5 pound bag?
- bjourne 8y agoIf it is not the case, can you present a counter-example? Can you code it up in say Python?
- Terr_ 8y agoOP just needs to change "key" to "key domain". I mean, you can perfect hash the keys ["foo", "supercalifragilisticexpialidocious"] into a single bit, the string-lengths are irrelevant.