2.29.4.6 Hashing

Hashing means the act of taking some value and producing a number from the value. A hash function is a function that does this. Every equivalence predicate E has a set of acceptable hash functions for that predicate; a hash funtion hash is acceptable iff:

(E obj1 obj2) ≡ (= (hash obj1) (hash obj2))

A hash function H is good for a equivalence predicate E if it distributes the result numbers (hash values) for non–equal objects (by E) as uniformly as possible over the numeric range of hash values, especially in the case when some (non–equal) objects resemble each other by e.g. having common subsequences. This definition is vague but should be enough to assert that e.g. a constant function is not a good hash function.

When the definition of make-hash-table above talks about an “appropriate” hashing function for E, it means a hashing function that gives decent performance (for the hashing operation) while being both acceptable and good for E. This definition, too, is intentionally vague.

Function: hash object

Function: hash object bound

Produce a hash value for object in the range [0, bound). If bound is not given, the implementation is free to choose any bound, given that the default bound is greater than the size of any imaginable hash table in a normal application. (This is so that the implementation may choose some very big value in fixnum range for the default bound.) This hash function is acceptable for equal?.

Function: string-hash string

Function: string-hash string bound

The same as hash, except that the argument string must be a string.

Function: string-ci-hash string

Function: string-ci-hash string bound

The same as string-hash, except that the case of characters in string does not affect the hash value produced.

Function: hash-by-identity object

Function: hash-by-identity object bound

The same as hash, except that this function is only guaranteed to be acceptable for eq?. The reason for providing this function is that it might be implemented significantly more efficiently than hash. Implementations are encouraged to provide this function as a builtin.