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