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.

STK 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.

Note: Hash table manipulation procedures are built upon the efficient Tcl hash table package.





`=̀13`(ndexfile(index-entry "make-hash-table" "tt" main )make-hash-table)
procedure
`=̀13`(ndexfile(index-entry "make-hash-table" "tt" main )make-hash-tablecomparison)
procedure
`=̀13`(ndexfile(index-entry "make-hash-table" "tt" main )make-hash-tablecomparison hash)
procedure
ndexfile(index-entry "Make-hash-table" "tt" aux )Make-hash-table admits three different forms. The most general form admit two arguments. The first argument is a comparison function which determine 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,

Consequently, $\Longrightarrow$
$\Longrightarrow$ unspecified error makeotherˆ`=̀13`


          gobblecr(define h (make-hash-table))
is equivalent to $\Longrightarrow$
$\Longrightarrow$ unspecified error makeotherˆ`=̀13`

          gobblecr(define h (make-hash-table eq? hash-table-hash))
Another interesting example is $\Longrightarrow$
$\Longrightarrow$ unspecified error makeotherˆ`=̀13`

          gobblecr(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: $\Longrightarrow$
$\Longrightarrow$ unspecified error makeotherˆ`=̀13`

          gobblecr(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 ndexfile(index-entry "eq?" "tt" aux )eq? or string=? are handled in an more efficient way (in fact, they don't use the ndexfile(index-entry "hash-table-hash" "tt" aux )hash-table-hash fucntion to speed up hash table retrievals).





`=̀13`(ndexfile(index-entry "hash-table?" "tt" main )hash-table?obj)
procedure
Returns #t if obj is a hash table, returns #f otherwise.





`=̀13`(ndexfile(index-entry "hash-table-hash" "tt" main )hash-table-hashobj)
procedure
ndexfile(index-entry "hash-table-hash" "tt" aux )hash-table-hash computes a hash code for an object and returns the hash code as a non negative integer. A property of hash-table-hash is that

(equal? x y) implies (equal? (hash-table-hash x) (hash-table-hash y)
as the the Common Lisp sxhash function from which this procedure is modeled.





`=̀13`(ndexfile(index-entry "hash-table-put!" "tt" main )hash-table-put!hash key value)
procedure
ndexfile(index-entry "Hash-table-put!" "tt" aux )Hash-table-put! enters an association between key and value in the hash table. The value returned by ndexfile(index-entry "hash-table-put!" "tt" aux )hash-table-put! is undefined.





`=̀13`(ndexfile(index-entry "hash-table-get" "tt" main )hash-table-gethash key)
procedure
`=̀13`(ndexfile(index-entry "hash-table-get" "tt" main )hash-table-gethash key default)
procedure
ndexfile(index-entry "Hash-table-get" "tt" aux )Hash-table-get 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 error is raised. $\Longrightarrow$
$\Longrightarrow$ unspecified error makeotherˆ`=̀13`


          gobblecr(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) (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






`=̀13`(ndexfile(index-entry "hash-table-remove!" "tt" main )hash-table-remove!hash key)
procedure
hash must be a hash table containing an entry for key. ndexfile(index-entry "Hash-table-remove!" "tt" aux )Hash-table-remove! deletes the entry for key in hash, if it exists. Result of Hash-table-remove! is unspecified.

$\Longrightarrow$
$\Longrightarrow$ unspecified error makeotherˆ`=̀13`


          gobblecr(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





`=̀13`(ndexfile(index-entry "hash-table-for-each" "tt" main )hash-table-for-eachhash proc)
procedure
Proc must be a procedure taking two arguments. ndexfile(index-entry "Hash-table-for-each" "tt" aux )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 ndexfile(index-entry "hash-table-for-each" "tt" aux )hash-table-for-each is undefined.
Note: The order of application of proc is unspecified. $\Longrightarrow$
$\Longrightarrow$ unspecified error makeotherˆ`=̀13`


          gobblecr(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





`=̀13`(ndexfile(index-entry "hash-table-map" "tt" main )hash-table-maphash proc)
procedure
Proc must be a procedure taking two arguments. ndexfile(index-entry "Hash-table-map" "tt" aux )Hash-table-map calls proc on each entry in hash, with the entry's key as the first argument and the entry's value as the second. The result of ndexfile(index-entry "hash-table-map" "tt" aux )hash-table-map is a list of the values returned by proc, in unspecified order.
Note: The order of application of proc is unspecified. $\Longrightarrow$
$\Longrightarrow$ unspecified error makeotherˆ`=̀13`


          gobblecr(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)))) ((0 . "0") (3 . "3") (2 . "2") (1 . "1") (4 . "4"))





`=̀13`(ndexfile(index-entry "hash-table->list" "tt" main )hash-table->listhash)
procedure
ndexfile(index-entry "hash-table->list" "tt" aux )hash-table->list 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. $\Longrightarrow$
$\Longrightarrow$ unspecified error makeotherˆ`=̀13`


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





`=̀13`(ndexfile(index-entry "hash-table-stats" "tt" main )hash-table-statshash)
procedure
ndexfile(index-entry "Hash-table-stats" "tt" aux )Hash-table-stats returns a string with 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.