BSD license compatible hash algorithm?

[Dag-Erling Smørgrav]

"Aryeh M. Friedman" <aryeh.friedman at gmail.com> writes:
> Dag-Erling Smørgrav <des at des.no> writes:
> > "Aryeh M. Friedman" <aryeh.friedman at gmail.com> writes:
> > > All hashs have issues with pooling.... see
> > > http://www.burtleburtle.net/bob/hash/index.html... btw it is a
> > > old wives tale that the number of buckets should be prime (mostly
> > > based on the very weak implementation Knuth offered)
> > Not an "old wives' tale", but rather an easy way to implement a
> > hash algorithm that is good enough for most simple uses: metric
> > modulo table size, where metric is a number derived from the item
> > in such a manner as to give a good spread.
> Sorry for taking a while to reply.... but the above only applies if
> your using a very primitive hash like Knuth's multiplication one....

You are overlooking a very common case: the use of a hash table to
implement an in-memory dictionary (aka associative array) where the key
is an integer with poor variability in the high-order bits.  K % N where
K is the key and N is the size of the table requires very little code,
is reasonably efficient, and, provided that N is prime, gives a
reasonably good spread (excpet in pathological cases where the values of
K are clustered around multiples of N).

> every modern hash I know of should have 2^k buckets actually for some
> k<2^32 [in almost all cases <2^16 except for algorithms like the one I
> mentioned I am working on which sets k=n where n=the bit count of the
> key].

I certainly hope not.  2^(2^32) is several of billion orders of
magnitude more than the number of elementary particles in the known
universe (currently estimated at 10^80).  Even 2^(2^16) is too big by
about sixty thousand orders of magnitude.

DES
-- 
Dag-Erling Smørgrav - des at des.no