[r6rs-discuss] Hash function return value constraints

[David Rush]

2009/4/4 Lynn Winebarger <owinebar at gmail.com>:
> The problem is that the situation is actually reversed.  The user may be
> writing the hash table implementation, but wants to use the Scheme
> implementation's  hash functions to get hashes on arbitrary Scheme objects
> for efficiency.  Obviously the tables the implementation provides can do
> whatever they want under the hood, but the hash functions provided by the
> implementation to the public should conform to the user's expectations.

And *that* is the clear reason for the R6RS restriction. It makes user
written hash table code more portable.

And you *do* have to write your own hash-tables if you want good
performance. Many moons ago, I did some serious side-by-side
benchmarking, and found that under identical test runs, variation in
any of the variables (underlying vector size, rehashing algorithm,
growth increments, hash-function, collision resolution algorithms...)
involved in a real hash-table implementation correlates chaotically
with the bench-mark run-times.

Hash tables are not O(1)! They need to be carefully tuned.

david rush
-- 
GPG Public key at http://cyber-rush.org/drr/gpg-public-key.txt