0

I work in hardware/electronics where everything is power of 2.

To avoid storing the key along with the value, I can find a perfect hash function for the known-in-advance keys.

Nevertheless, the PHF doesn't tell me if a key is invalid (not part of the keys the PHF has been generated with).

Example:

  • Input space: 32bits (int) values
    • 5 are known: 2,7,12,61,187
  • Output space: 3bits=8 values

The known values are all mapped uniquely to the output space via the PHF: $f(2), f(7), f(12), f(61), f(187)$

Nevertheless, $f(1), f(3), ..., f(6), ..., f(8), ...$ obviously creates collisions.

  • Is there a way to detect these values?

If not, I need to store the key along with the value. If I can detect them, I don't need to store the key with the value and save memory.

I could for example reserve the key 0 (or any key the algorithm used to generate the PHF gives me), to detect such invalid key.

None
  • 101
  • 2
  • So your perfect hash function has $f(2)=00, f(7)=01, f(12)=10, f(61)=11$. One can certainly define that $f(anythingelse)=NAN$. That is a fine function that does what you ask. I suspect you have more restrictions on the hash function than you have said and this is unacceptable. If you really have $2^n$ acceptable keys and store $n$ bits, you don't have any codes left over for other entries. Please clarify. – Ross Millikan May 30 '21 at 02:20
  • Sorry, this isn't a Minimal perfect hash function, the output space is bigger than the known values. The mapping is unknown for now, it can be $f(61)=000$, $f(2)=010$ ... – None May 30 '21 at 02:32
  • Then you simply reserve one code for invalid entry. The hash function sends all invalid entries to $000$ and all valid entries to a different code. That is a fine hash function as long as you do not restrict the algebraic properties of the function. In that case I do not understand what the question is here. – Ross Millikan May 30 '21 at 03:20
  • It's a preliminary question before I start developing anything. It's for optimized hardware code, using add, sub, mult and logic gates. Avoiding mod and other more advanced functions. I'll come back here once I have a better question. Thanks! – None May 30 '21 at 06:23
  • I plan to use gperf to generate the hash function. I don't see any option to detect invalid keys. – None May 30 '21 at 15:23

0 Answers0