[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

should hash function upper bound be exclusive?



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
per@xxxxxxxxxxx   http://per.bothner.com/