Email list hosting service & mailing list manager

should hash function upper bound be exclusive? Per Bothner (09 Aug 2005 17:31 UTC)
Re: should hash function upper bound be exclusive? Per Bothner (10 Aug 2005 04:52 UTC)
Re: should hash function upper bound be exclusive? Panu Kalliokoski (10 Aug 2005 06:36 UTC)

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/