Next: Object Hashing, Previous: The Association Table, Up: Associations [Contents][Index]
Hash tables are a fast, powerful mechanism for storing large numbers of associations. MIT/GNU Scheme’s hash tables feature automatic resizing, customizable growth parameters, customizable hash procedures, and many options for weak references to keys or data.
The average times for the insertion, deletion, and lookup operations on a hash table are bounded by a constant. The space required by the table is proportional to the number of associations in the table; the constant of proportionality is described below (see Resizing of Hash Tables).
The hash table interface described below is a superset of SRFI 69: “Basic hash tables”. The reason for supporting the extra functionality is that SRFI 69 fails to specify certain optimization-enabling exceptions to its semantics, forcing a correct implementation to pay the non-negligible performance cost of completely safe behavior. 13 The MIT/GNU Scheme native hash table interface, in contrast, specifies the minor exceptions it needs, and is therefore implemented more efficiently.
We do not describe the SRFI 69-compliant interface here, as that would be redundant with the SRFI document.
SRFI 69 does not give hash functions the flexibility to return new hash values after a garbage collection, which prevents a system whose garbage collector may relocate objects from hashing based on the addresses of objects in memory (see Address Hashing). SRFI 69 also does not specify circumstances when procedures passed as arguments to hash table operations may not themselves modify the hash table, which requires defensive copying and defensive repetitions of lookups.