Skip to main content
Help us improve PyPI by participating in user testing. All experience levels needed!

Perfect hashing utilities for Python

Project description

https://travis-ci.org/eddieantonio/perfection.svg?branch=master

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():

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

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

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

    x = i mod t
    y = i 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.

Project details


Release history Release notifications

This version
History Node

2.0.0

History Node

2.0.0-beta

History Node

1.0.2

History Node

1.0.0

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, size & hash SHA256 hash help File type Python version Upload date
perfection-2.0.0.tar.gz (11.1 kB) Copy SHA256 hash SHA256 Source None Nov 18, 2016

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging CloudAMQP CloudAMQP RabbitMQ AWS AWS Cloud computing Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page