I'm currently looking at perfect hash functions. One thing I miss from the texts I've read so far is, how they cope when attempting to look up with a key that is outside of the set from which the perfect hash was generated from.

  • 3
    $\begingroup$ They don't. It's an invalid input. $\endgroup$ – Yuval Filmus Oct 10 '19 at 12:25
  • $\begingroup$ @YuvalFilmus: Is there a way to determine just from the PHF itself if a key is invalid? Or somehow map any value outside the set of keys to a nil value? $\endgroup$ – datenwolf Oct 10 '19 at 14:37
  • $\begingroup$ Depends on the implementation. It may return the image of another key in the domain. If the PHF is not minimal, it may also return a value that doesn't have to a preimage in the set. Some implementations detect foreign keys with a given probability (as bloom filters do) and return a special value. $\endgroup$ – Piezoid Oct 11 '19 at 11:58
  • $\begingroup$ @Piezoid: I already had the idea of prepending a bloom filter in front of the lookup to filter out all keys that are not in the set of the PHF keys. $\endgroup$ – datenwolf Oct 11 '19 at 15:15

Given a set of keys, a “perfect” hash function is one that gives a different hash for each key. As soon as you try to apply it to a key outside that set, it is quite likely not “perfect” anymore.

Let’s say you are writing a compiler, and you found a”perfect” hash function that maps each reserved identifier of your programming language to a different hash code. And I give you a word that is not one of the reserved words of the language. If you apply your “perfect” hash function then the hash code is either not the hash code of a reserved word (you need to check for that case), or it may be the hash code of a reserved word ( you need to check for that as well). The advantage is that at most one check is needed.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.