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 10 Sep 2015 03:46 UTC

Alex Shinn scripsit:

> 1.  Since we give leeway to replace the hash function in special
> cases, and since the function is never exposed, there's no reason
> we can't replace it with 2 or more functions.

I've just posted a new draft to <http://www.ccil.org/~cowan/temp/srfi-125.html>.
In this one, the SRFI 69 reflective functions are back, but the implementation
is free to return #f if it didn't use the user-supplied hash function.

> 2. I realize now that the SRFI-114 hash functions are severely
> underspecified for use in this SRFI - they need to produce values
> suitable for any number of buckets, but the range is unspecified.

Yes, if you have a really vast number of buckets there may be a problem.

> R6RS hash-tables are similarly underspecified, but SRFI-69 does
> not have this problem because it uses an explicit `bound' argument.

You can't rely on that argument actually being the number of hash buckets,
though; it can just always be max-fixnum or something.

> If we don't add a bound argument, we should specify the range of
> hash functions to be at least the largest imaginable number of
> buckets in an application.

Done.

> Another consideration is a "salt" argument to the hash functions
> to be mixed in with the result, which is one way to avoid the
> hash collision DoS attack.  This would also effectively allow an
> arbitrary number of hash functions, which is useful for more
> than just cuckoo hashing (double hashing).

I think the framework is free to do this, since the hash code returned
by the hash function may be used in any way the framework wishes.

Arthur: please pull from the URL above for the next draft.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
        Raffiniert ist der Herrgott, aber boshaft ist er nicht.
                --Albert Einstein