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,
unspecified
error
makeotherˆ`=̀13`
gobblecr(define h (make-hash-table))is equivalent to
gobblecr(define h (make-hash-table eq? hash-table-hash))Another interesting example is
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:
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.
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.
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.
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.
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.
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.