NAME
nbperf —
compute a perfect hash
function
SYNOPSIS
nbperf |
[-ps] [-a
algorithm] [-c
utilisation] [-h
hash] [-i
iterations] [-m
map-file] [-n
name] [-o
output] [input] |
DESCRIPTION
nbperf reads a number of keys one per line from standard
input or input. It computes a minimal perfect hash
function and writes it to stdout or output. The default
algorithm is "chm".
The -m argument instructs
nbperf to write the resulting key mapping to
map-file. Each line gives the result of the hash
function for the corresponding input key.
The parameter utilisation determines the space efficiency.
Supported arguments for -a:
- chm
- This results in an order preserving minimal perfect hash function. The utilisation must be at least 2, the default. The number of iterations needed grows if the utilisation is very near to 2.
- chm3
- Similar to chm. The resulting hash function needs three instead of two table lookups when compared to chm. The utilisation must be at least 1.24, the default. This makes the output for chm3 noticeably smaller than the output for chm.
- bpz
- This results in a non-order preserving minimal perfect hash function. Output size is approximately 2.79 bit per key for the default value of utilisation, 1.24. This is also the smallest supported value.
Supported arguments for -h:
- mi_vector_hash
- Platform-independent version of Jenkins parallel hash. See mi_vector_hash(3).
The number of iterations can be limited with
-i. nbperf outputs a
function matching uint32_t
hash(const
void * restrict, size_t) to stdout. The function
expects the key length as second argument, for strings not including the
terminating NUL. It is the responsibility of the caller to pass in only
valid keys or compare the resulting index to the key. The function name can
be changed using -n name. If
the -s flag is specified, it will be static.
After each failing iteration, a dot is written to stderr.
nbperf checks for duplicate keys on the
first iteration that passed basic hash distribution tests. In that case, an
error message is printed and the program terminates.
If the -p flag is specified, the hash
function is seeded in a stable way. This may take longer than the normal
random seed, but ensures that the output is the same for repeated
invocations as long as the input is constant.
EXIT STATUS
The nbperf utility exits 0 on
success, and >0 if an error occurs.
SEE ALSO
AUTHORS
Jörg Sonnenberger