Node: Hash Tables, Next: , Previous: Pattern Matching, Up: Standard Procedures



Hash Tables

A hash table consists of zero or more entries, each consisting of a key and a value. Given the key for an entry, the hashing function can very quickly locate the entry, and hence the corresponding value. There may be at most one entry in a hash table with a particular key, but many entries may have the same value.

STKLOS hash tables grow gracefully as the number of entries increases, so that there are always less than three entries per hash bucket, on average. This allows for fast lookups regardless of the number of entries in a table.

make-hash-table STKLOS Procedure
make-hash-table comparison STKLOS Procedure
make-hash-table comparison hash STKLOS Procedure
Make-hash-table admits three different forms. The most general form admit two arguments. The first argument is a comparison function which determines how keys are compared; the second argument is a function which computes a hash code for an object and returns the hash code as a non negative integer. Objets with the same hash code are stored in an A-list registered in the bucket corresponding to the key.

If omitted,

  • hash defaults to the hash-table-hash procedure (see see hash-table-hash).
  • comparison defaults to the eq? procedure (see see eq?).

Consequently,

          (define h (make-hash-table))
          
is equivalent to
          (define h (make-hash-table eq? hash-table-hash))
          

An interesting example is

          (define h (make-hash-table string-ci=? string-length))
          
which defines a new hash table which uses string-ci=? for comparing keys. Here, we use the string-length as a (very simple) hashing function. Of course, a function which gives a key depending of the characters composing the string gives a better repartition and should probably enhance performances. For instance, the following call to make-hash-table should return a more efficient, even if not perfect, hash table:
          (make-hash-table
              string-ci=?
              (lambda (s)
                (let ((len (string-length s)))
                  (do ((h 0)  (i 0 (+ i 1)))
                      ((= i len) h)
                    (set! h (+ h (char->integer
                                   (char-downcase (string-ref s i)))))))))
          

Note: Hash tables with a comparison function equal to eq? or string=? are handled in an more efficient way (in fact, they don't use hash-table-hash function to speed up hash table retrievals).

hash-table? obj STKLOS Procedure
Returns #t if obj is a hash table, returns #f otherwise.

hash-table-hash obj STKLOS Procedure
Computes a hash code for an object and returns this hash code as a non negative integer. A property of hash-table-hash is that
          (equal? x y) => (equal? (hash-table-hash x) (hash-table-hash y)
          

as the the Common Lisp sxhash function from which this procedure is modeled.

hash-table-put! hash key value STKLOS Procedure
Enters an association between key and value in thehash table. The value returned by hash-table-put! is void.

hash-table-get hash key STKLOS Procedure
hash-table-get hash key default STKLOS Procedure
Returns the value associated with key in the given hash table. If no value has been associated with key in hash, the specified default is returned if given; otherwise an eerror is raised.
          (define h1 (make-hash-table))
          (hash-table-put! h1 'foo (list 1 2 3))
          (hash-table-get  h1 'foo)              =>  (1 2 3)
          (hash-table-get  h1 'bar 'absent)      =>  absent
          (hash-table-get  h1 'bar)              =>  error
          (hash-table-put! h1 '(a b c) 'present)
          (hash-table-get  h1 '(a b c) 'absent)  => absent
          
          (define h2 (make-hash-table equal?))
          (hash-table-put! h2 '(a b c) 'present)
          (hash-table-get  h2 '(a b c))          => present
          

hash-table-remove hash key STKLOS Procedure
Deletes the entry for key in hash, if it exists. Result of hash-table-remove! is void.
          (define h (make-hash-table))
          (hash-table-put! h 'foo (list 1 2 3))
          (hash-table-get h 'foo)          => (1 2 3)
          (hash-table-remove! h 'foo)
          (hash-table-get h 'foo 'absent)  => absent
          

hash-table-update! hash key update-fun init-value STKLOS Procedure
Update the value associated to key in table hash if key is already in table with the value (update-fun current-value). If no value is associated to key, a new entry in the table is inserted with the init-value associated to it.
          (let ((h   (make-hash-table))
                (1+  (lambda (n) (+ n 1))))
            (hash-table-update! h 'test 1+ 100)
            (hash-table-update! h 'test 1+ 100)
            (hash-table-get h 'test))             => 101
          

hash-table-for-each hash proc STKLOS Procedure
Proc must be a procedure taking two arguments. Hash-table-for-each calls proc on each key/value association in hash, with the key as the first argument and the value as the second. The value returned by hash-table-for-each is void.

Note: The order of application of proc is unspecified.

          (let ((h   (make-hash-table))
                (sum 0))
            (hash-table-put! h 'foo 2)
            (hash-table-put! h 'bar 3)
            (hash-table-for-each h (lambda (key value)
                                     (set! sum (+ sum value))))
            sum)           =>  5
          

hash-table-map hash proc STKLOS Procedure
Proc must be a procedure taking two arguments. Hash-table-map calls proc on each key/value association in hash, with the key as the first argument and the value as the second. The result of hash-table-map is a list of the values returned by proc, in an unspecified order.

Note: The order of application of proc is unspecified.

          (let ((h (make-hash-table)))
            (dotimes (i 5)
              (hash-table-put! h i (number->string i)))
            (hash-table-map h (lambda (key value)
                                 (cons key value))))
                       => ((3 . "3") (4 . "4") (0 . "0") (1 . "1") (2 . "2"))
          

hash-table->list hash STKLOS Procedure
Returns an "association list" built from the entries in hash. Each entry in hash will be represented as a pair whose car is the entry's key and whose cdr is its value.

Note: the order of pairs in the resulting list is unspecified.

          (let ((h (make-hash-table)))
            (dotimes (i 5)
              (hash-table-put! h i (number->string i)))
            (hash-table->list h))
                 => ((3 . "3") (4 . "4") (0 . "0") (1 . "1") (2 . "2"))
          

hash-table-stats hash STKLOS Procedure
hash-table-stats hash port STKLOS Procedure
Prints overall information about hash, such as the number of entries it contains, the number of buckets in its hash array, and the utilization of the buckets. Informations are printed on port. If no port is given to hash-table-stats, information are printed on the current output port (see see current-output-port).