6.34.2 Hash table iterators

Ghuloum and Dybvig explain in the paper:

Ghuloum, Dybvig. “Generation–Friendly Eq Hash Tables”. Proceedings of the 2007 Workshop on Scheme and Functional Programming.

why it is not possible to iterate a hash table by visiting the buckets: there’s a problem with rehashing entries that are moved by the garbage collector. The iterators always use hashtable-keys and hashtable-entries, which is slow and memory consuming, but it is safe.

Function: hashtable-map-keys proc table

Build and return a new hash table with the same hash function and equivalence function of table; add associations to the new table by applying proc to every key in table, in unspecified order, and using the returned value as association value.

(let* ((A '((a . 1) (b . 2) (c . 3)))
       (T (alist->hashtable! (make-eq-hashtable) A))
       (M (hashtable-map-keys
              (lambda (key) 123)
            T)))
  (hashtable->alist M (lambda (s1 s2)
                        (string<? (symbol->string s1)
                                  (symbol->string s2)))))
⇒ ((a . 123) (b . 123) (c . 123))

Function: hashtable-map-entries proc table

Build and return a new hash table with the same hash function and equivalence function of table; add associations to the new table by applying proc to every key and value in table, in unspecified order, and using the returned value as association value.

(let* ((A '((a . 1) (b . 2) (c . 3)))
       (T (alist->hashtable! (make-eq-hashtable) A))
       (M (hashtable-map-entries
              (lambda (key val)
                (* 10 val))
            T)))
  (hashtable->alist M (lambda (s1 s2)
                        (string<? (symbol->string s1)
                                  (symbol->string s2)))))
⇒ ((a . 10) (b . 20) (c . 30))

Function: hashtable-for-each-key proc table

Apply proc to every key in table, in unspecified order, and discard the results. It is implemented as follows:

(vector-for-each proc (hashtable-keys table))

Function: hashtable-for-each-entry proc table

Apply proc to every key and value in table, in unspecified order, and discard the results. It is implemented as follows:

(receive (keys vals)
    (hashtable-entries table)
  (vector-for-each proc keys vals))

Function: hashtable-for-all-keys pred table

Apply pred to every key in table, in unspecified order, stopping at the first key for which pred returns #f.

• If pred returns non-false for every key: the return value is the return value of the last call to pred.
• If pred returns #f for a key: the return value is #f.

It is implemented as follows:

(vector-for-all pred (hashtable-keys table))

Function: hashtable-for-all-entries pred table

Apply pred to every key and value in table, in unspecified order, stopping at the first application for which PRED returns #f.

• If pred returns non–false for every key and value: the return value is the return value of the last call to pred.
• If pred returns #f for a key and value: the return value is #f.

It is implemented as follows:

(receive (keys vals)
    (hashtable-entries table)
  (vector-for-all pred keys vals))

Function: hashtable-exists-key proc table

Apply proc to every key in table in unspecified order.

• If proc returns #f for every key: the return value is #f.
• If proc returns non–false for a key: the return value is the value returned by proc.

(vector-exists proc (hashtable-keys table)))

Function: hashtable-exists-entry proc table

Apply proc to every key and value in table in unspecified order.

• If proc returns #f for every key and value: the return value is #f.
• If proc returns non–false for a key and value: the return value is the value returned by proc.

(receive (keys vals)
    (hashtable-entries table)
  (vector-exists proc keys vals))

Function: hashtable-find-key proc table

Apply proc to every key in table in unspecified order.

• If proc returns #f for every key: the return value is #f.
• If proc returns non–false for a key: the return value is that key.

(vector-find pred (hashtable-keys table)))

Function: hashtable-find-entry proc table

Apply proc to every key and value in table in unspecified order.

• If proc returns #f for every key and value: the return value is #f.
• If proc returns non–false for a key and value: the return value is a pair having that key as car and that value as cdr.

Function: hashtable-fold-keys proc nil table

Apply proc to every key in table, in unspecified order; the second argument of the first proc application is nil, then it is the return value of the previous application. Return the return value of the last proc application.

It is implemented as follows:

(vector-fold-right proc nil (hashtable-keys table))

To build an list of keys we do:

(hashtable-fold-keys
    (lambda (key nil)
      (cons key nil))
  '() table)

Function: hashtable-fold-entries proc nil table

Apply proc to every key and value in table, in unspecified order; the third argument of the first proc application is nil, then it is the return value of the previous application. Return the return value of the last proc application.

It is implemented as follows:

(receive (keys vals)
    (hashtable-entries table)
  (vector-fold-right proc nil keys vals))

To build an alist from a table we do:

(hashtable-fold-entries
    (lambda (key val nil)
      (cons (cons key val) nil))
  '() table)

Function: hashtable->alist table

Function: hashtable->alist table compar

Build and return an alist holding the keys and values of table. This function is mostly useful for debugging.

If the optional argument compar is the boolean #f: just return the alist; if it is a procedure: sort the resulting alist with the standard list-sort using compar as comparison predicate for the keys.

Function: alist->hashtable! table al

Fill table with the entries of the alist al. Return table itself.