IsItThere - a small tool that generates perfect hash sets
Basile B. via Digitalmars-d-announce
digitalmars-d-announce at puremagic.com
Fri Jan 6 15:27:54 PST 2017
"IsItThere ?" is a small tool that generates perfect hash sets.
Its results are formatted as ready to use D code.
I initially created it for Coedit highlighter. In this version
it's not anymore a simple script but a full command-line tool
that's able to generate D code.
- Why ?
When you have a small and constant set of words it's not useful
to use a hash set that's build at run-time.
- How ?
For a small set of words, probabilities exist that there's a hash
function able to produce different results for each element (i.e
always 0 or 1 element per bucket). IsItThere finds this hash
function, using brute force and a PRNG. To be more exact, it
doesn't find the hash function but rather the coefficients that
produce the same results as this hypothetical function. Using
coefficients is even faster than a real hash function since they
are allocated in a static array.
- Links:
https://code.dlang.org/packages/isitthere
https://github.com/BBasile/IsItThere
https://en.wikipedia.org/wiki/Perfect_hash_function
More information about the Digitalmars-d-announce
mailing list