Next: Resizing of Hash Tables, Previous: Construction of Hash Tables, Up: Hash Tables

The procedures described in this section are the basic operations on hash tables. They provide the functionality most often needed by programmers. Subsequent sections describe other operations that provide additional functionality needed by some applications.

— procedure: **hash-table/put!**` hash-table key datum`

Associates

datumwithkeyinhash-tableand returns an unspecified result. The average time required by this operation is bounded by a constant.

— procedure: **hash-table/get**` hash-table key default`

Returns the datum associated with

keyinhash-table. If there is no association forkey,defaultis returned. The average time required by this operation is bounded by a constant.

— procedure: **hash-table/remove!**` hash-table key`

If

hash-tablehas an association forkey, removes it. Returns an unspecified result. The average time required by this operation is bounded by a constant.

— procedure: **hash-table/clear!**` hash-table`

Removes all associations in

hash-tableand returns an unspecified result. The average and worst-case times required by this operation are bounded by a constant.

— procedure: **hash-table/count**` hash-table`

Returns the number of associations in

hash-tableas an exact non-negative integer. Ifhash-tableholds its keys weakly, this is a conservative upper bound that may count some associations whose keys have recently been reclaimed by the garbage collector. The average and worst-case times required by this operation are bounded by a constant.

— procedure: **hash-table->alist**` hash-table`

Returns the contents of

hash-tableas a newly allocated alist. Each element of the alist is a pair`(`

key`.`

datum`)`

wherekeyis one of the keys ofhash-table, anddatumis its associated datum. The average and worst-case times required by this operation are linear in the number of associations in the table.

— procedure: **hash-table/key-list**` hash-table`

Returns a newly allocated list of the keys in

hash-table. The average and worst-case times required by this operation are linear in the number of associations in the table.

— procedure: **hash-table/datum-list**` hash-table`

Returns a newly allocated list of the datums in

hash-table. Each element of the list corresponds to one of the associations inhash-table; if the table contains multiple associations with the same datum, so will this list. The average and worst-case times required by this operation are linear in the number of associations in the table.

— procedure: **hash-table/for-each**` hash-table procedure`

Proceduremust be a procedure of two arguments. Invokesprocedureonce for each association inhash-table, passing the association'skeyanddatumas arguments, in that order. Returns an unspecified result.Proceduremust not modifyhash-table, with one exception: it is permitted to call`hash-table/remove!`

to remove the association being processed.

The following procedure is an alternate form of `hash-table/get`

that is useful in some situations. Usually, `hash-table/get`

is
preferable because it is faster.

— procedure: **hash-table/lookup**` hash-table key if-found if-not-found`

If-foundmust be a procedure of one argument, andif-not-foundmust be a procedure of no arguments. Ifhash-tablecontains an association forkey,if-foundis invoked on the datum of the association. Otherwise,if-not-foundis invoked with no arguments. In either case, the result yielded by the invoked procedure is returned as the result of`hash-table/lookup`

(`hash-table/lookup`

reducesinto the invoked procedure, i.e. calls it tail-recursively). The average time required by this operation is bounded by a constant.