16bit hash
"Martin v. Löwis"
martin at v.loewis.de
Thu Jun 28 06:49:04 CEST 2007
> Is the any way to get an efficient 16bit hash in python?
Unfortunately, that problem is underspecified. The simplest
and most efficient 16-bit hash I can come up with is
def super_efficient_hash(o):
return 0
Now, you say: this gives collisions.
So yes, it does - but you didn't ask for it to be
perfect, just efficient.
But I don't think you are looking for a perfect hash,
but one that distributes the values evenly.
Unfortunately, that *still* would be underspecified:
you need to specify the distribution of the input values
to be able to tell whether the distribution of hash
values is even.
More generally: for most 16-bit hash functions H that
are capable of yielding all 65536 hash values, and for
any number N, there is a set S1 of N objects where
H distributes even, and a set S2 of N objects where
all hash values collide.
(the only exceptions are hash functions which produce
some output values only for a finite number of inputs)
So: what are your input data, and what is the
distribution among them?
Regards,
Martin
More information about the Python-list
mailing list