Perfect hashing for Py

[bearophileHUGS]

Following links from this thread:
http://groups.google.com/group/comp....e1a45485ab36a#

I have found this perfect hash (minimal too) implementation:
http://burtleburtle.net/bob/hash/perfect.html

I have already translated part of it to D, and it seems to work well
enough. As discussed in the PyConDue, I think this may be used in
frozenset (and frozendict) to build a (minimal too?) perfect hash on
the fly, to allow (hopefully) faster retrieval of items that don't
change.
That code is C and I think it's public domain, so if experiments show
it gives enough speed up, it may be added to CPython 2.6/3.

Bye,
bearophile

[Casey]

On Jul 11, 8:01*am, [e-mail] wrote:

Following links from this thread:http://groups.google.com/group/comp....thread/thread/...

I have found this perfect hash (minimal too) implementation:http://burtleburtle.net/bob/hash/perfect.html

I have already translated part of it to D, and it seems to work well
enough. As discussed in the PyConDue, I think this may be used in
frozenset (and frozendict) to build a (minimal too?) perfect hash on
the fly, to allow (hopefully) faster retrieval of items that don't
change.
That code is C and I think it's public domain, so if experiments show
it gives enough speed up, it may be added to CPython 2.6/3.

Bye,
bearophile

It would be interesting to see if such an algorithm could actually
provide any significant performance improvements for the size of sets
that I suspect are most often used in practice. The chance of a hash
collision for a good 32-bit general is fairly low even for a set of
1,000,000 unique elements, which seems to me to be a pretty large
memory-based set. Compare that with the cost of determining a perfect
hash (O(n**2)?).

From my perspective, a perfect hash would certainly be a welcome
addition to the Python library or even as an optional algorithm
supporting
hash-based collections.

[Raymond Hettinger]

On Jul 12, 10:13*am, Raymond Hettinger <[e-mail]:

On Jul 11, 3:01*pm, [e-mail] wrote:

I have found this perfect hash (minimal too) implementation:http://burtleburtle.net/bob/hash/perfect.html

I have already translated part of it to D, and it seems to work well
enough. As discussed in the PyConDue, I think this may be used in
frozenset (and frozendict) to build a (minimal too?) perfect hash on
the fly, to allow (hopefully) faster retrieval of items that don't
change.

I played around with the idea and have a rough implementation sketch:

class PerfectSet(collections.Set):
__slots__ = ['len', 'hashvalue', 'hashfunc', 'hashtable']
DUMMY = object()
def __init__(self, keys, sparseness=0.5):
keys = frozenset(keys)
self.len = len(keys)
self.hashvalue = hash(keys)
n = (len(keys) / sparseness) + 1
assert n self.len
self.hashfunc = make_perfect_hash_function(keys, n)
self.hashtable = [self.DUMMY] * n
for k in keys:
self.hashtable[self.hashfunc(k)] = k
del __len__(self, k):
return self.len
def __iter__(self, k)
return (k for k in self.hashtable if k is not self.DUMMY)
def __contains__(self, k):
return self.table[self.hashfunc(k)] is not self.DUMMY

The perfect hash function will need to use the regular hash(obj) as a
starting point. This helps with non-string types and it preserves
existing relationships between __hash__ and __eq__.

The construction is more expensive than with regular frozensets so it
is only useful when lookups are very common.

Playing around with the idea suggests that a sparseness variable for
frozensets would largely accomplish the same goal without the overhead
of creating and applying a perfect hash function. Sparse hash tables
rarely collide.
Raymond