# Minimal perfect hashing: check the key, not just the slot

A minimal perfect hash function can return an occupied slot for a key that was
never inserted. BBHash documents this behavior. This small executable replay
checks that accepting an in-range result as membership gives false matches,
while comparing the full stored key rejects the selected absent queries.

## Reproduce

Download replay.py and replay.cpp from this directory, then run:

```sh
python3 replay.py --output receipt.json
```

Requires Python 3, g++, and network access to the pinned upstream header.
The script verifies the header SHA-256 before compiling, uses a temporary
directory, runs the executable three times, and requires identical results.
Use --header /path/to/BooPHF.h for an offline run with the same verified bytes.

## Method and interpretation

Stored keys are the 4096 even integers from 0 through 8190. Queries are the 4096
odd integers from 1 through 8191. BBHash uses one thread and gamma=2.0.
Every stored key must map to a unique index in [0,4096). A separate array stores
the exact original key at that index. Each absent query is classified as the
ULLONG_MAX sentinel or an in-range result. Exact-key comparison follows only
after checking the index, so the sentinel is never used to access the array.

[receipt.json](receipt.json) contains the measured counts and an actual
absent-key/index/stored-key counterexample. [replay.cpp](replay.cpp) is the native
fixture; [replay.py](replay.py) records versions and hashes.

This is an exhaustive check of one chosen synthetic query set. The counts are
not a false-positive probability for arbitrary workloads. It does not reproduce
the paper's throughput or memory benchmarks, test updates, or assess adversarial
hash security. A finite fingerprint can collide; it is not the full-key equality
test used here.

## Sources

- Limasset, Rizk, Chikhi and Peterlongo, SEA 2017,
  https://doi.org/10.4230/LIPIcs.SEA.2017.25, method section 2.
- BBHash README and lookup implementation, commit
  be4220c8f8580299b212a0c6c6c867528a0f07ac:
  https://github.com/rizkg/BBHash/tree/be4220c8f8580299b212a0c6c6c867528a0f07ac.
  The downloaded header is MIT-licensed, copyright 2015 Guillaume Rizk.
  It is not redistributed in this directory.
- Lehmann et al., Modern Minimal Perfect Hashing: A Survey, v3:
  https://arxiv.org/abs/2506.06536v3, sections 1-2.

The replay code is original Hesela code, made available under the MIT license.