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-tabledoes not hold its keys and data strongly, this is a conservative upper bound that may count some associations whose keys or data 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 useful when there is no sensible default
value for `hash-table/get`

and the caller must choose between
different actions depending on whether there is a datum associated
with the key.

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

— procedure: **hash-table/modify!**` hash-table key default procedure`

Proceduremust be a procedure of one argument. Appliesprocedureto the datum associated withkeyinhash-tableor todefaultif there is no association forkey, associates the result withkey, and returns that same result.Proceduremust not usehash-table. The average time required by this operation is bounded by a constant.

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

Get-defaultmust be a procedure of no arguments. Ensures thathash-tablehas an association forkeyand returns the associated datum. Ifhash-tabledid not have a datum associated withkey,`hash-table/intern!`

appliesget-defaultto zero arguments to generate one. As with`hash-table/modify!`

,get-defaultmust not usehash-table. The average time required by this operation is bounded by a constant.