perfection — Perfect hashing utilities

A module that creates perfect hash functions for a known set of integer inputs.

>>> import perfection
>>> l = (0, 3, 4, 7 ,10, 13, 15, 18, 19, 21, 22, 24, 26, 29, 30, 34)
>>> hf = perfection.make_hash(l)
>>> hf(19)
1

Install

pip install perfection

Main features

• make_hash() that generates an honest-to-goodness perfect hash function for the given keys.
• make_dict() creates a dictionary subclass that implements the MutableMapping interface (thus, acts exactly like a dict), and uses the hash function created in the equivalent call to make_hash().

Additionally, hash_parameters() may be used to output the parameters of making a perfect hash for the given set of input keys. These parameters can then be used to implement a perfect hash function in a language of your choice.

For example, generate t and r parameters using hash_parameters():

>>> import perfection
>>>
>>> l = (0, 3, 4, 7 ,10, 13, 15, 18, 19, 21, 22, 24, 26, 29, 30, 34)
>>> params = perfection.hash_parameters(l)
>>> params.t
6
>>> params.r
(2, 7, 12, 0, 7, 10)
>>> params.offset
0

Then, the hash function, in pseudocode is as follows:

function hash(i):
    static offset = 0
    static r = { 2, 7, 12, 0, 7, 10 }
    static t = 6

    val = i + offset
    x = val mod t
    y = val div t
    return x + r[y]

Note that div stands for floor (integer) division.

Beta Features

Can import a minimal perfect (ordered!) hash function with the same API using:

import perfection.czech

API is not yet finalized!

Credit

Algorithm described by Thomas Gettys.

Python code © 2014, 2016 Eddie Antonio Santos. MIT licensed.

With contributions by Thomas Calmant.