To store a large number of data values and associated keys in a structure that allows values to be retrieved quickly by key, one approach is to use a hash table. A hash table can be represented in Scheme as a vector of lists. A hash function maps any possible key to the index of one of the components of the vector (that is, to an integer in the range from 0 [inclusive] to the size of the vector [exclusive]). The list located at the position in the vector serves as a bucket to which key-value pairs are added when additions are made to the hash table and within which values are sought during retrieval.
The make-hash-table procedure shown here takes two arguments,
a size (number of buckets) for the hash table and an appropriate hash
function mapping keys to vector indices. It returns another procedure, one
which is capable either of adding a new entry to the hash table (if called
with two arguments, the new key and the new value) or of recovering the
value associated with a given key in an already existing entry (if called
with one argument, the key). If the hash table does not contain an entry
for a key provided in a retrieval, the procedure returns the symbol
*hash-table-search-failed*.
(define make-hash-table
(lambda (size hash-function)
(let ((table (make-vector size '())))
(lambda (key . opt)
(let* ((index (hash-function key))
(bucket (vector-ref table index)))
(if (null? opt)
(cond ((assoc key bucket) => cdr)
(else '*hash-table-search-failed*))
(vector-set! table
index
(cons (cons key (car opt)) bucket))))))))
This implementation makes no provision for removing an entry from the hash
table, but it's not difficult to adapt the code. Instead of distinguishing
the various hash-table operations by the number of arguments to the
dynamically constructed procedure, the following implementation requires
the caller to provide, as the first argument, one of the symbols
add-entry!, retrieve, delete-entry!,
display, and clear! (which empties the table).
Optional arguments then provide any additional information that is needed
for the selected operation.
(define make-hash-table
(lambda (size hash-function)
(let ((table (make-vector size '())))
(lambda (message . args)
(case message
((add-entry!)
(let* ((key (car args))
(index (hash-function key)))
(vector-set! table
index
(cons (cons key (cadr args))
(vector-ref table index)))))
((retrieve)
(let* ((key (car args))
(index (hash-function key)))
(cond ((assoc key (vector-ref table index)) => cdr)
(else '*hash-table-search-failed*))))
((delete-entry!)
(let* ((key (car args))
(index (hash-function key)))
(let loop ((bucket (vector-ref table index))
(so-far '()))
(cond ((null? bucket)
(vector-set! table index (reverse so-far)))
((equal? key (caar bucket))
(loop (cdr bucket) so-far))
(else
(loop (cdr bucket)
(cons (car bucket) so-far)))))))
((display)
(do ((index 0 (+ index 1)))
((= index size))
(let ((bucket (vector-ref table index)))
(if (not (null? bucket))
(begin
(display "Bucket #")
(display index)
(display ": ")
(display bucket)
(newline))))))
((clear!)
(do ((index 0 (+ index 1)))
((= index size))
(vector-set! table index '()))))))))
This document is available on the World Wide Web as
http://www.math.grin.edu/~stone/events/scheme-workshop/hash-tables.html