Hash tables and hash functions

Hash tables

Procedure make-hashtable

(make-hashtable hash-function bucket-searcher size) => hashtable

Returns a newly allocated mutable hash table using hash-function as the hash function and bucket-searcher, e.g. ASSQ, ASSV, ASSOC, to search a bucket with size buckets at first, expanding the number of buckets as needed. The hash-function must accept a key and return a non-negative exact integer.

(make-hashtable hash-function bucket-searcher) => hashtable

Equivalent to (make-hashtable hash-function bucket-searcher n) for some value of n chosen by the implementation.

(make-hashtable hash-function) => hashtable

Equivalent to (make-hashtable hash-function assv).

(make-hashtable) => hashtable

Equivalent to (make-hashtable object-hash assv).

Procedure hashtable-contains

(hashtable-contains? hashtable key) => bool

Returns true iff the hashtable contains an entry for key.

Procedure hashtable-fetch

(hashtable-fetch hashtable key flag) => object

Returns the value associated with key in the hashtable if the hashtable contains key; otherwise returns flag.

Procedure hashtable-get

(hashtable-get hashtable key) => object

Equivalent to (hashtable-fetch #f).

Procedure hashtable-put!

(hashtable-put! hashtable key value) => unspecified

Changes the hashtable to associate key with value, replacing any existing association for key.

Procedure hashtable-remove!

(hashtable-remove! hashtable key) => unspecified

Removes any association for key within the hashtable.

Procedure hashtable-clear!

(hashtable-clear! hashtable) => unspecified

Removes all associations from the hashtable.

Procedure hashtable-size

(hashtable-size hashtable) => integer

Returns the number of keys contained within the hashtable.

Procedure hashtable-for-each

(hashtable-for-each procedure hashtable) => unspecified

The procedure must accept two arguments, a key and the value associated with that key. Calls the procedure once for each key-value association in hashtable. The order of these calls is indeterminate.

Procedure hashtable-map

(hashtable-map procedure hashtable) => unspecified

The procedure must accept two arguments, a key and the value associated with that key. Calls the procedure once for each key-value association in hashtable, and returns a list of the results. The order of the calls is indeterminate.

Procedure hashtable-copy

(hashtable-copy hashtable) => hashtable

Returns a copy of the hashtable.

Hash functions

The hash values returned by these functions are nonnegative exact integer suitable as hash values for the hashtable functions.

Procedure equal-hash

(equal-hash object) => integer

Returns a hash value for object based on its contents.

Procedure object-hash

(object-hash object) => integer

Returns a hash value for object based on its identity.

Procedure string-hash

(string-hash string) => fixnum

Returns a hash value for string based on its content.

Procedure symbol-hash

(symbol-hash symbol) => fixnum

Returns a hash value for symbol based on its print name. Symbol-hash is very fast, because the hash code is cached in the symbol data structure.


$Id: hashtable.html,v 1.2 2000/09/12 02:46:45 lth Exp $
larceny@ccs.neu.edu