hash functions and other comments Alex Shinn (08 Sep 2015 06:19 UTC)
Re: hash functions and other comments John Cowan (08 Sep 2015 12:57 UTC)
Re: hash functions and other comments Alex Shinn (08 Sep 2015 13:32 UTC)
Re: hash functions and other comments John Cowan (08 Sep 2015 14:59 UTC)
Re: hash functions and other comments Alex Shinn (09 Sep 2015 04:29 UTC)
Re: hash functions and other comments John Cowan (09 Sep 2015 13:18 UTC)
Re: hash functions and other comments Alex Shinn (10 Sep 2015 02:09 UTC)
Re: hash functions and other comments John Cowan (10 Sep 2015 03:46 UTC)
Re: hash functions and other comments Arthur A. Gleckler (10 Sep 2015 03:56 UTC)
Re: hash functions and other comments Alex Shinn (10 Sep 2015 10:05 UTC)
Re: hash functions and other comments Kevin Wortman (11 Sep 2015 19:01 UTC)
Re: hash functions and other comments John Cowan (11 Sep 2015 19:51 UTC)
Re: hash functions and other comments Alex Shinn (12 Sep 2015 06:29 UTC)
Re: hash functions and other comments John Cowan (12 Sep 2015 22:16 UTC)
Re: hash functions and other comments Alex Shinn (15 Sep 2015 03:23 UTC)
Re: hash functions and other comments John Cowan (15 Sep 2015 11:31 UTC)
Re: hash functions and other comments Alex Shinn (15 Sep 2015 12:57 UTC)
Re: hash functions and other comments Alex Shinn (16 Sep 2015 03:01 UTC)

Re: hash functions and other comments John Cowan 09 Sep 2015 13:18 UTC

Alex Shinn scripsit:

Thanks for the detailed explication.

> But wait, you may ask, what about perfect hashes?

A static perfect hash function of the type people usually think of needs
to know the number of buckets in the hash table, and the framework
does not provide this.  (The second argument optionally passed to hash
functions by an implementation of the SRFI-69 framework, now abandoned
in SRFI 125, does not serve this function reliably.)

> Two dynamic perfect hash algorithms are Dietzfelbinger et al's
> algorithm [1] and the Cuckoo hash [2].  Both of these have
> additional restrictions on the load factor in order to get even
> _expected_ amortized constant time insertions.  This conflicts with
> implementation extensions to specify the load factor explicitly.

I would assume that a cuckoo-based framework (I haven't read D's paper)
would simply ignore such extensions.  But cuckoo hashing needs more
than one hash function in any case, so it doesn't fit the general
69/125/126/R6RS/CL hash framework.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
Andrew Watt on Microsoft:  Never in the field of human computing has so
much been paid by so many to so few! (pace Winston Churchill)