should hash function upper bound be exclusive?
Per Bothner 09 Aug 2005 17:31 UTC
Current the 'bound' for hash functions is exclusive: the returned hash h
is such that (and (>= 0 h) (< h bound)). One might want the default
bound to be such that hashes range over the positive fixnums. But in
that case the bound would not be a fixnum: it would have to be one
larger than the largest fixnum.
A hash-table implementation might want to cache hash values, and might
also want to be able to resize the table. In that case you want to
store the "maximal" bound - i.e. a hash value ranging from 0 to
the maximum positive fixnum - inclusive. The modulo operation is
the performed on the "maximal" hashcode - so you never call a hash
function with a non-default bound.
For implementations that support static typing, its nice if the
'bound' parameter and the resulting hash value can be specified as
a fixnum. That means the bound needs to be inclusive.
--
--Per Bothner
xxxxxx@bothner.com http://per.bothner.com/