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
- 5 are known:
- 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.