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

should hash function upper bound be exclusive?

This page is part of the web mail archives of SRFI 69 from before July 7th, 2015. The new archives for SRFI 69 contain all messages, not just those from before July 7th, 2015.

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/