Next: , Previous: Topological Sort, Up: Sorting and Searching


7.2.6 Hashing

(require 'hash) These hashing functions are for use in quickly classifying objects. Hash tables use these functions.

— Function: hashq obj k
— Function: hashv obj k
— Function: hash obj k

Returns an exact non-negative integer less than k. For each non-negative integer less than k there are arguments obj for which the hashing functions applied to obj and k returns that integer.

For hashq, (eq? obj1 obj2) implies (= (hashq obj1 k) (hashq obj2)).

For hashv, (eqv? obj1 obj2) implies (= (hashv obj1 k) (hashv obj2)).

For hash, (equal? obj1 obj2) implies (= (hash obj1 k) (hash obj2)).

hash, hashv, and hashq return in time bounded by a constant. Notice that items having the same hash implies the items have the same hashv implies the items have the same hashq.