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)