Re: hash functions and other comments

*John Cowan*10 Sep 2015 03:46 UTCAlex 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