pph

pph generates a minimal order-preserving hash function for a list of keys.

Reference:

Practical perfect hashing GV Cormack, RNS Horspool, M Kaiserswerth - The Computer Journal, 1985

Table of Contents

• License
• Building
• Using

License

This project is licensed under the Apache License, Version 2.0.

Building

pph has no external library dependencies — the only third-party code is header-only and vendored in third_party/ (CLI11 for command-line parsing). A C++20 compiler is required.

pph uses CMake for its build system.

mkdir build
cd build
cmake ..
make
ctest        # run the C++ test suite (unit + codegen end-to-end)

Project layout

include/pph/     public C++ headers (#include "pph/pph.h")
src/             library sources and the CLI entry point (pph_main.cpp)
python/          Python packaging and nanobind bindings (src/pypph.cpp)
tests/python/    pytest suite for the Python module
tests/cpp/       doctest-based C++ test suite (run with ctest)
bench/           nanobench performance benchmarks (see bench/RESULTS.md)
examples/        C++, Rust, and Go usage examples (see examples/README.md)
examples/static/ generated static-initialization examples (pph_codegen)
examples/data/   sample word lists and generated .hash files
third_party/     vendored dependencies
cmake/           CMake modules and the version header template
build-support/   clang-format / clang-tidy helper scripts

See PLAN.md for the modernization roadmap and current progress.

Using

The basic command line to generate a hash function from a file containing a list of strings (one per line) is:

pph -i ./examples/data/file.txt -o ./file.hash

The command line to verify an existing hash function is:

pph --verify ./file.hash

The other command line options can be seen by typing:

pph --help

The default timeout for creating a hash function is 60000 milliseconds (1 minute).

If a hash function is not generated, you can try sorting the input file:

pph -i file.txt --index > file_index.txt
sort --numeric-sort --key=2 file_index.txt > file_sorted_index.txt
awk -F' ' '{print $1}'  file_sorted_index.txt > file_sorted.txt

Code generation (static tables)

pph_codegen emits a self-contained lookup CLI (C++, Rust, or Go) with the hash table statically initialized in the source — no file loading or parsing at startup (~58x faster for one-shot lookups; see bench/RESULTS.md):

pph_codegen table.json.hash --lang cpp -o out/
g++ -std=c++17 -O2 out/pph_static_lookup.cpp -o lookup
./lookup SELECT WHERE          # or --selfcheck / --bench

Legacy-format input files work too. Supported key functions: djb_hash, fnv64a_hash, oat_hash, crc64.

FrozenTable

For read-heavy use, freeze a loaded table into pph::FrozenTable (include/pph/frozen_table.h): an immutable, ~3x smaller representation with const, allocation-free lookups that is safe to share across reader threads. See bench/RESULTS.md for measurements.

#include "pph/frozen_table.h"
...
pph::Table table;
table.unserialize(file);
auto frozen = pph::FrozenTable::freeze(table);   // std::optional
uint64_t v = frozen->find_val("SELECT");

File format

Hash functions are saved as a versioned JSON document (format v2). Legacy v1 text files are still read transparently, and can be converted:

pph --verify old.hash -o new.json.hash

Schema (row arrays are one compact row per line):

{
  "format": "pph",
  "version": 2,
  "key_function": "<uuid of the key hash function>",
  "seed": <uint64>,
  "table": { "n": ..., "p": ..., "s": ..., "multiplier": ...,
             "adjustment": ..., "timeout": ...,
             "header_count": ..., "slot_count": ... },
  "functions": [ [modulus, multiplier, adjustment], ... ],
  "headers":   [ [index, p, i, r], ... ],
  "slots":     [ [index, "key", value, hash_index], ... ]
}

examples/data/*.json.hash are converted copies of the legacy examples.

Note for implementers: the top-level header hash is always djb_hash; key_function names only the second-level slot functions. See examples/README.md for the full lookup algorithm and porting notes (including the sign-extension behavior of the key functions).

Python

The Python bindings are built with nanobind via scikit-build-core (PEP 517/621; see python/pyproject.toml and python/CMakeLists.txt). Install and test:

pip install ./python
python3 -m pytest tests/python/

For iterative development, use an automatically-rebuilding editable install:

pip install nanobind scikit-build-core
pip install --no-build-isolation -e ./python
python3 -m pytest tests/python/

Import the module.

from pph import PphHashTable, PphRandomNumber, PphKeyFunctions

See the tests in tests/python/ for how to generate a hash function using the Python interface.