4.15 Hash Tables

4.15 Hash Tables
The Racket Reference
Language Model
Notation for Documentation
Syntactic Forms
Datatypes
Structures
Classes and Objects
Units
Contracts
Pattern Matching
10
Control Flow
11
Concurrency and Parallelism
12
Macros
13
Input and Output
14
Reflection and Security
15
Operating System
16
Memory Management
17
Unsafe Operations
18
Running Racket
Bibliography
Index
Datatypes
4.1
Equality
4.2
Booleans
4.3
Numbers
4.4
Strings
4.5
Byte Strings
4.6
Characters
4.7
Symbols
4.8
Regular Expressions
4.9
Keywords
4.10
Pairs and Lists
4.11
Mutable Pairs and Lists
4.12
Vectors
4.13
Stencil Vectors
4.14
Boxes
4.15
Hash Tables
4.16
Treelists
4.17
Sequences and Streams
4.18
Dictionaries
4.19
Sets
4.20
Procedures
4.21
Void
4.22
Undefined
4.15
Hash Tables
4.15.1
Additional Hash Table Functions
On this page:
hash?
hash-
equal?
hash-
equal-
always?
hash-
eqv?
hash-
eq?
hash-
strong?
hash-
weak?
hash-
ephemeron?
hash
hashalw
hasheq
hasheqv
make-
hash
make-
hashalw
make-
hasheqv
make-
hasheq
make-
weak-
hash
make-
weak-
hashalw
make-
weak-
hasheqv
make-
weak-
hasheq
make-
ephemeron-
hash
make-
ephemeron-
hashalw
make-
ephemeron-
hasheqv
make-
ephemeron-
hasheq
make-
immutable-
hash
make-
immutable-
hashalw
make-
immutable-
hasheqv
make-
immutable-
hasheq
hash-
set!
hash-
set*!
hash-
set
hash-
set*
hash-
ref
hash-
ref-
key
hash-
ref!
hash-
has-
key?
hash-
update!
hash-
update
hash-
remove!
hash-
remove
hash-
clear!
hash-
clear
hash-
copy-
clear
hash-
map
hash-
map/
copy
hash-
keys
hash-
values
hash-
>list
hash-
keys-
subset?
hash-
for-
each
hash-
count
hash-
empty?
hash-
iterate-
first
hash-
iterate-
next
hash-
iterate-
key
hash-
iterate-
value
hash-
iterate-
pair
hash-
iterate-
key+
value
hash-
copy
4.15.1
Additional Hash Table Functions
hash-
union
hash-
union!
hash-
intersect
hash-
filter
hash-
filter-
keys
hash-
filter-
values
Racket
top
contents
← prev
up
next →
4.15
Hash Tables
Hash Tables
in
The Racket Guide
introduces hash tables.
hash table
(or simply
hash
) maps each of its
keys to a single value. For a given hash table, keys are equivalent
via
equal?
equal-always?
eqv?
, or
eq?
, and keys are retained either strongly, weakly
(see
Weak Boxes
), or like
ephemerons
A hash table is also either mutable or immutable.
Immutable hash tables support effectively constant-time access and
update, just like mutable hash tables; the constant on immutable
operations is usually larger, but the functional nature of immutable
hash tables can pay off in certain algorithms. Use
immutable?
to check whether a hash table is immutable.
Immutable hash tables actually provide
log N
access and update. Since
is limited by the address space so
that
log N
is limited to less than 30 or 62 (depending on the
platform),
log N
can be treated reasonably as a constant.
For
equal?
-based hashing, the built-in hash functions on
strings
pairs
lists
vectors
prefab
or transparent
structures
, etc
, take time
proportional to the size of the value. The hash code for a compound
data structure, such as a list or vector, depends on hashing each item
of the container, but the depth of such recursive hashing is
limited (to avoid potential problems with cyclic data). For a
non-
list
pair
, both
car
and
cdr
hashing is treated as a deeper hash, but the
cdr
of a
list
is treated as having the same hashing depth as the list.
A hash table can be used as a two-valued
sequence
(see
Sequences
). The keys and values of the hash table serve as
elements of the sequence (i.e., each element is a key and its
associated value). If a mapping is added to or removed from a mutable hash
table during iteration, then an iteration step may fail with
exn:fail:contract
, or the iteration may skip or duplicate
keys and values. See also
in-hash
in-hash-keys
in-hash-values
, and
in-hash-pairs
Two hash tables cannot be
equal?
unless they have the same
mutability, use the same key-comparison procedure (
equal?
equal-always?
eqv?
, or
eq?
), both hold
keys strongly, weakly, or like
ephemerons
Empty immutable hash tables are
eq?
when they are
equal?
Changed in version 7.2.0.9 of package
base
: Made empty immutable hash tables
eq?
when they are
equal?
Caveats concerning concurrent
modification:
A mutable hash table can be manipulated with
hash-ref
hash-set!
, and
hash-remove!
concurrently by multiple threads, and the operations are protected by
a table-specific semaphore as needed. Several caveats apply, however:
If a thread is terminated while applying
hash-ref
hash-ref-key
hash-set!
hash-remove!
hash-ref!
hash-update!
, or
hash-clear!
to a hash table that
uses
equal?
equal-always?
, or
eqv?
key
comparisons, all current and future operations on the hash table may
block indefinitely.
The
hash-map
hash-for-each
, and
hash-clear!
procedures do
not use the table’s semaphore to guard the traversal as a whole
(if a traversal is needed, in the case of
hash-clear!
).
Changes by one thread to a hash table can affect the keys and values
seen by another thread part-way through its traversal of the same
hash table.
The
hash-update!
and
hash-ref!
functions
use a table’s semaphore
independently for the
hash-ref
and
hash-set!
parts
of their functionality, which means that the update as a whole is not
“atomic.”
Adding a mutable hash table as a key in itself is trouble on
the grounds that the key is being mutated (see the caveat below),
but it is also a kind of concurrent use of the hash table: computing
a hash table’s hash code may require waiting on the table’s
semaphore, but the semaphore is already held for modifying the hash
table, so the hash-table addition can block indefinitely.
Caveat concerning mutable
keys:
If a key in an
equal?
-based hash table is mutated
(e.g., a key string is modified with
string-set!
), then the
hash table’s behavior for insertion and lookup operations becomes
unpredictable.
A literal or printed hash table starts with
#hash
#hashalw
#hasheqv
, or
#hasheq
. See
Reading Hash Tables
for information on
read
ing
hash tables and
Printing Hash Tables
for information on
ing hash tables.
procedure
hash?
boolean?
any/c
Returns
#t
if
is a
hash table
#f
otherwise.
See also
immutable-hash?
and
mutable-hash?
procedure
hash-equal?
ht
boolean?
ht
hash?
Returns
#t
if
ht
compares keys with
equal?
#f
if it compares with
eq?
eqv?
, or
equal-always?
procedure
hash-equal-always?
ht
boolean?
ht
hash?
Returns
#t
if
ht
compares keys with
equal-always?
#f
if it compares with
eq?
eqv?
, or
equal?
Added in version 8.5.0.3 of package
base
procedure
hash-eqv?
ht
boolean?
ht
hash?
Returns
#t
if
ht
compares keys with
eqv?
#f
if it compares with
equal?
equal-always?
, or
eq?
procedure
hash-eq?
ht
boolean?
ht
hash?
Returns
#t
if
ht
compares keys with
eq?
#f
if it compares with
equal?
equal-always?
, or
eqv?
procedure
hash-strong?
ht
boolean?
ht
hash?
Returns
#t
if
ht
retains its keys strongly,
#f
if it retains keys weakly or like
ephemerons
Added in version 8.0.0.10 of package
base
procedure
hash-weak?
ht
boolean?
ht
hash?
Returns
#t
if
ht
retains its keys weakly,
#f
if it retains keys strongly or like
ephemerons
procedure
hash-ephemeron?
ht
boolean?
ht
hash?
Returns
#t
if
ht
retains its keys like
ephemerons
#f
if it retains keys strongly or merely
weakly.
Added in version 8.0.0.10 of package
base
procedure
hash
key
val
...
...
and/c
hash?
hash-equal?
immutable?
hash-strong?
key
any/c
val
any/c
procedure
hashalw
key
val
...
...
and/c
hash?
hash-equal-always?
immutable?
hash-strong?
key
any/c
val
any/c
procedure
hasheq
key
val
...
...
and/c
hash?
hash-eq?
immutable?
hash-strong?
key
any/c
val
any/c
procedure
hasheqv
key
val
...
...
and/c
hash?
hash-eqv?
immutable?
hash-strong?
key
any/c
val
any/c
Creates an immutable hash table with each given
key
mapped to
the following
val
; each
key
must have a
val
so the total number of arguments to
hash
must be even.
The
hash
procedure creates a table where keys are compared
with
equal?
hashalw
creates a table where keys are compared with
equal-always?
hasheq
procedure creates a table where
keys are compared with
eq?
hasheqv
procedure
creates a table where keys are compared with
eqv?
The
key
to
val
mappings are added to the table in
the order that they appear in the argument list, so later mappings can
hide earlier mappings if the
key
s are equal.
Changed in version 8.5.0.3 of package
base
: Added
hashalw
procedure
make-hash
assocs
and/c
hash?
hash-equal?
not/c
immutable?
hash-strong?
assocs
listof
pair?
null
procedure
make-hashalw
assocs
and/c
hash?
hash-equal-always?
not/c
immutable?
hash-strong?
assocs
listof
pair?
null
procedure
make-hasheqv
assocs
and/c
hash?
hash-eqv?
not/c
immutable?
hash-strong?
assocs
listof
pair?
null
procedure
make-hasheq
assocs
and/c
hash?
hash-eq?
not/c
immutable?
hash-strong?
assocs
listof
pair?
null
Creates a mutable hash table that holds keys strongly.
The
make-hash
procedure creates a table where keys are
compared with
equal?
make-hasheq
procedure creates
a table where keys are compared with
eq?
make-hasheqv
procedure creates a table where keys are
compared with
eqv?
, and
make-hashalw
creates a table
where keys are compared with
equal-always?
The table is initialized with the content of
assocs
. In each
element of
assocs
, the
car
is a key, and the
cdr
is the corresponding value. The mappings are added to the
table in the order that they appear in
assocs
, so later
mappings can hide earlier mappings.
See also
make-custom-hash
Examples:
make-hash
'#hash()
make-hash
42
"meaning of life"
'#hash((0 . 1) (2 . 3) (42 . "meaning of life"))
make-hash
'#hash((0 . 3) (1 . 2))
make-hash
list
cons
cons
apple
orange
cons
#t
#f
'#hash((#t . #f) (0 . 1) (apple . orange))
make-hash
'#hash((0 . (1)) (1 . (2)) (2 . (3)))
make-hash
list
cons
'#hash((# . #))
Changed in version 8.5.0.3 of package
base
: Added
make-hashalw
procedure
make-weak-hash
assocs
and/c
hash?
hash-equal?
not/c
immutable?
hash-weak?
assocs
listof
pair?
null
procedure
make-weak-hashalw
assocs
and/c
hash?
hash-equal-always?
not/c
immutable?
hash-weak?
assocs
listof
pair?
null
procedure
make-weak-hasheqv
assocs
and/c
hash?
hash-eqv?
not/c
immutable?
hash-weak?
assocs
listof
pair?
null
procedure
make-weak-hasheq
assocs
and/c
hash?
hash-eq?
not/c
immutable?
hash-weak?
assocs
listof
pair?
null
Like
make-hash
make-hasheq
make-hasheqv
, and
make-hashalw
, but creates a
mutable hash table that holds keys weakly.
Beware that values in a weak hash table are retained normally. If a value in
the table refers back to its key, then the table will retain the value
and therefore the key; the mapping will never be removed from the
table even if the key becomes otherwise inaccessible. To avoid that
problem, use an ephemeron hash table as created by
make-ephemeron-hash
make-ephemeron-hashalw
make-ephemeron-hasheqv
, or
make-ephemeron-hasheq
For values that do not refer to keys,
there is a modest extra cost to using an ephemeron hash table instead
of a weak hash table, but prefer an ephemeron hash table when in
doubt.
Changed in version 8.5.0.3 of package
base
: Added
make-weak-hashalw
procedure
make-ephemeron-hash
assocs
and/c
hash?
hash-equal?
not/c
immutable?
hash-ephemeron?
assocs
listof
pair?
null
procedure
make-ephemeron-hashalw
assocs
and/c
hash?
hash-equal-always?
not/c
immutable?
hash-ephemeron?
assocs
listof
pair?
null
procedure
make-ephemeron-hasheqv
assocs
and/c
hash?
hash-eqv?
not/c
immutable?
hash-ephemeron?
assocs
listof
pair?
null
procedure
make-ephemeron-hasheq
assocs
and/c
hash?
hash-eq?
not/c
immutable?
hash-ephemeron?
assocs
listof
pair?
null
Like
make-hash
make-hasheq
make-hasheqv
, and
make-hashalw
but creates a mutable hash table that holds
key-value combinations in the same way as an
ephemeron
Using an ephemeron hash table is like using a weak hash table and
mapping each key to a
ephemeron
that pairs the key and value.
An advantage of an ephemeron hash table is that the value need not be
extracted with
ephemeron-value
from the result of functions
like
hash-ref
. An ephemeron hash table might also be
represented more compactly than a weak hash table with explicit
ephemeron
values.
Added in version 8.0.0.10 of package
base
Changed in version 8.5.0.3: Added
make-ephemeron-hashalw
procedure
make-immutable-hash
assocs
and/c
hash?
hash-equal?
immutable?
hash-strong?
assocs
listof
pair?
null
procedure
make-immutable-hashalw
assocs
and/c
hash?
hash-equal-always?
immutable?
hash-strong?
assocs
listof
pair?
null
procedure
make-immutable-hasheqv
assocs
and/c
hash?
hash-eqv?
immutable?
hash-strong?
assocs
listof
pair?
null
procedure
make-immutable-hasheq
assocs
and/c
hash?
hash-eq?
immutable?
hash-strong?
assocs
listof
pair?
null
Like
hash
hashalw
hasheq
, and
hasheqv
, but accepts
the key–value mapping in association-list form like
make-hash
make-hashalw
make-hasheq
, and
make-hasheqv
Changed in version 8.5.0.3 of package
base
: Added
make-immutable-hashalw
procedure
hash-set!
ht
key
void?
ht
and/c
hash?
not/c
immutable?
key
any/c
any/c
Maps
key
to
in
ht
, overwriting
any existing mapping for
key
See also the
caveats concerning concurrent modification
and the
caveat concerning mutable keys
above.
procedure
hash-set*!
ht
key
...
...
void?
ht
and/c
hash?
not/c
immutable?
key
any/c
any/c
Maps each
key
to each
in
ht
, overwriting
any existing mapping for each
key
. Mappings are added from the left, so
later mappings overwrite earlier mappings.
See also the
caveats concerning concurrent modification
and the
caveat concerning mutable keys
above.
procedure
hash-set
ht
key
and/c
hash?
immutable?
ht
and/c
hash?
immutable?
key
any/c
any/c
Functionally extends
ht
by mapping
key
to
, overwriting any existing mapping for
key
, and
returning the extended hash table.
See also the
caveat concerning mutable keys
above.
procedure
hash-set*
ht
key
...
...
and/c
hash?
immutable?
ht
and/c
hash?
immutable?
key
any/c
any/c
Functionally extends
ht
by mapping each
key
to
, overwriting any existing mapping for each
key
, and
returning the extended hash table. Mappings are added from the left, so
later mappings overwrite earlier mappings.
See also the
caveat concerning mutable keys
above.
procedure
hash-ref
ht
key
failure-result
any
ht
hash?
key
any/c
failure-result
failure-result/c
lambda
raise
make-exn:fail:contract
....
Returns the value for
key
in
ht
. If no value
is found for
key
, then
failure-result
determines the
result:
If
failure-result
is a procedure, it is called
(through a tail call) with no arguments to produce the result.
Otherwise,
failure-result
is returned as the result.
Examples:
hash-ref
hash
"hi"
hash-ref: no value found for key
key: "hi"
hash-ref
hash
"hi"
hash-ref
hash
"hi"
lambda
"flab"
"flab"
hash-ref
hash
"hi"
"bye"
"hi"
"bye"
hash-ref
hash
"hi"
"bye"
"no"
hash-ref: no value found for key
key: "no"
See also the
caveats concerning concurrent modification
and the
caveat concerning mutable keys
above.
procedure
hash-ref-key
ht
key
failure-result
any
ht
hash?
key
any/c
failure-result
failure-result/c
lambda
raise
make-exn:fail:contract
....
Returns the key held by
ht
that is equivalent to
key
according to
ht
’s key-comparison function. If no key is found,
then
failure-result
is used as in
hash-ref
to determine
the result.
If
ht
is not an
impersonator
, then the returned key,
assuming it is found, will be
eq?
-equivalent to the one
actually retained by
ht
Examples:
define
original-key
"hello"
define
key-copy
string-copy
original-key
equal?
original-key
key-copy
#t
eq?
original-key
key-copy
#f
define
table
make-hash
hash-set!
table
original-key
value
eq?
hash-ref-key
table
"hello"
original-key
#t
eq?
hash-ref-key
table
"hello"
key-copy
#f
If a mutable hash is updated multiple times using keys that are
not
eq?
-equivalent but are equivalent according to the
hash’s key-comparison procedure, the hash retains the first one:
Examples:
define
original-key
"hello"
define
key-copy
string-copy
original-key
define
table
make-hash
hash-set!
table
original-key
one
hash-set!
table
key-copy
two
eq?
hash-ref-key
table
"hello"
original-key
#t
eq?
hash-ref-key
table
"hello"
key-copy
#f
Conversely, an immutable hash retains the key that was most-recently
used to update it:
Examples:
define
original-key
"hello"
define
key-copy
string-copy
original-key
define
table0
hash
define
table1
hash-set
table0
original-key
one
define
table2
hash-set
table1
key-copy
two
eq?
hash-ref-key
table2
"hello"
original-key
#f
eq?
hash-ref-key
table2
"hello"
key-copy
#t
If
ht
is an
impersonator
, then the returned key
will be determined as described in the documentation to
impersonate-hash
See also the
caveats concerning concurrent modification
and the
caveat concerning mutable keys
above.
Added in version 7.4.0.3 of package
base
procedure
hash-ref!
ht
key
to-set
any
ht
hash?
key
any/c
to-set
failure-result/c
Returns the value for
key
in
ht
. If no value is
found for
key
, then
to-set
determines the result as
in
hash-ref
(i.e., it is either a thunk that computes a value
or a plain value), and this result is stored in
ht
for the
key
. (Note that if
to-set
is a thunk, it is not
invoked in tail position.)
See also the
caveats concerning concurrent modification
and the
caveat concerning mutable keys
above.
procedure
hash-has-key?
ht
key
boolean?
ht
hash?
key
any/c
Returns
#t
if
ht
contains a value for the given
key
#f
otherwise.
procedure
hash-update!
ht
key
updater
failure-result
void?
ht
and/c
hash?
not/c
immutable?
key
any/c
updater
any/c
->
any/c
failure-result
failure-result/c
lambda
raise
make-exn:fail:contract
....
Updates the value mapped by
key
in
ht
by applying
updater
to the value.
The value returned by
updater
becomes the new mapping for
key
, overwriting the
original value in
ht
Examples:
define
make-hash
hash-set!
hash-update!
add1
'#hash((a . 6))
The optional
failure-result
argument is used when no mapping exists for
key
already, in the same manner as in
hash-ref
Examples:
define
make-hash
hash-update!
add1
hash-update!: no value found for key: 'b
hash-update!
add1
'#hash((b . 1))
See also the
caveats concerning concurrent modification
and the
caveat concerning mutable keys
above.
procedure
hash-update
ht
key
updater
failure-result
and/c
hash?
immutable?
ht
and/c
hash?
immutable?
key
any/c
updater
any/c
->
any/c
failure-result
failure-result/c
lambda
raise
make-exn:fail:contract
....
Functionally updates the value mapped by
key
in
ht
by applying
updater
to the value and returning a new hash table. The value returned by
updater
becomes the new
mapping for
key
in the returned hash table.
Examples:
define
hash
hash-update
add1
'#hash((a . 6))
The optional
failure-result
argument is used when no mapping exists for
key
already, in the same manner as in
hash-ref
Examples:
define
hash
hash-update
add1
hash-update: no value found for key: 'b
hash-update
add1
'#hash((b . 1))
See also the
caveat concerning mutable keys
above.
procedure
hash-remove!
ht
key
void?
ht
and/c
hash?
not/c
immutable?
key
any/c
Removes any existing mapping for
key
in
ht
See also the
caveats concerning concurrent modification
and the
caveat concerning mutable keys
above.
procedure
hash-remove
ht
key
and/c
hash?
immutable?
ht
and/c
hash?
immutable?
key
any/c
Functionally removes any existing mapping for
key
in
ht
, returning
ht
(i.e., a result
eq?
to
ht
) if
key
is not present in
ht
See also the
caveat concerning mutable keys
above.
procedure
hash-clear!
ht
void?
ht
and/c
hash?
not/c
immutable?
Removes all mappings from
ht
If
ht
is not an
impersonator
, then all mappings are
removed in constant time. If
ht
is an
impersonator
then each key is removed one-by-one using
hash-remove!
See also the
caveats concerning concurrent modification
and the
caveat concerning mutable keys
above.
procedure
hash-clear
ht
and/c
hash?
immutable?
ht
and/c
hash?
immutable?
Functionally removes all mappings from
ht
If
ht
is not a
chaperone
, then clearing is
equivalent to creating a new
hash table
, and the operation is
performed in constant time. If
ht
is a
chaperone
then each key is removed one-by-one using
hash-remove
procedure
hash-copy-clear
ht
#:kind
kind
hash?
ht
hash?
kind
or/c
#f
immutable
mutable
weak
ephemeron
#f
Produces an empty
hash table
with the same key-comparison
procedure as
ht
, with either the given
kind
or the same kind as the given
ht
If
kind
is not supplied or
#f
, produces a hash
table of the same kind and mutability as the given
ht
If
kind
is
immutable
mutable
weak
, or
ephemeron
, produces a table that’s
immutable, mutable with strongly-held keys, mutable with
weakly-held keys, or mutable with ephemeron-held keys
respectively.
Changed in version 8.5.0.2 of package
base
: Added the
kind
argument.
procedure
hash-map
ht
proc
try-order?
listof
any/c
ht
hash?
proc
any/c
any/c
->
any/c
try-order?
any/c
#f
Applies the procedure
proc
to each element in
ht
in an unspecified order, accumulating the results
into a list. The procedure
proc
is called each time with a
key and its value, and the procedure’s individual results appear in
order in the result list.
If a hash table is extended with new keys (either through
proc
or by another thread) while a
hash-map
or
hash-for-each
traversal is in process, arbitrary key–value
pairs can be dropped or duplicated in the traversal. Key mappings can
be deleted or remapped (by any thread) with no adverse affects; the
change does not affect a traversal if the key has been seen already,
otherwise the traversal skips a deleted key or uses the remapped key’s
new value.
See also the
caveats concerning concurrent modification
above.
If
try-order?
is true, then the order of keys and values
passed to
proc
is normalized under certain
circumstances—
including when every key is one of the following and
with the following order (earlier bullets before later):
booleans
sorted
#f
before
#t
characters
sorted by
charreal numbers
sorted by
symbols
sorted with
uninterned
symbols before
unreadable symbols
before
interned
symbols,
then sorted by
symbolkeywords
sorted by
keywordstrings
sorted by
stringbyte strings
sorted by
bytesnull
#
; and
eof
Changed in version 6.3 of package
base
: Added the
try-order?
argument.
Changed in version 7.1.0.7: Added guarantees for
try-order?
Examples:
hash-map
make-hash
'(0 1 2)
hash-map
make-hash
'(1 2 3)
procedure
hash-map/copy
ht
proc
#:kind
kind
hash?
ht
hash?
proc
any/c
any/c
->
values
any/c
any/c
kind
or/c
#f
immutable
mutable
weak
ephemeron
#f
Applies the procedure
proc
to each element in
ht
in an unspecified order, accumulating the results
into a new hash with the same key-comparison procedure as
ht
, with either the given
kind
or the same
kind as the given
ht
If
kind
is not supplied or
#f
, produces a hash
table of the same kind and mutability as the given
ht
If
kind
is
immutable
mutable
weak
, or
ephemeron
, produces a table that’s
immutable, mutable with strongly-held keys, mutable with
weakly-held keys, or mutable with ephemeron-held keys
respectively.
Examples:
hash-map/copy
#hash
"apple"
"banana"
lambda
values
string-upcase
'#hash((a . "APPLE") (b . "BANANA"))
define
frozen-capital
hash-map/copy
make-hash
"apple"
"banana"
lambda
values
string-upcase
#:kind
immutable
frozen-capital
'#hash((a . "APPLE") (b . "BANANA"))
immutable?
frozen-capital
#t
Added in version 8.5.0.2 of package
base
procedure
hash-keys
ht
try-order?
listof
any/c
ht
hash?
try-order?
any/c
#f
Returns a list of the keys of
ht
in an unspecified order.
If
try-order?
is true, then the order of keys is normalized under
certain circumstances. See
hash-map
for further explanations on
try-order?
and on information about modifying
ht
during
hash-keys
See also the
caveats concerning concurrent modification
above.
Changed in version 8.3.0.11 of package
base
: Added the
try-order?
argument.
procedure
hash-values
ht
try-order?
listof
any/c
ht
hash?
try-order?
any/c
#f
Returns a list of the values of
ht
in an unspecified order.
If
try-order?
is true, then the order of values is normalized under
certain circumstances, based on the ordering of the associated keys.
See
hash-map
for further explanations on
try-order?
and on
information about modifying
ht
during
hash-values
See also the
caveats concerning concurrent modification
above.
Changed in version 8.3.0.11 of package
base
: Added the
try-order?
argument.
procedure
hash->list
ht
try-order?
listof
cons/c
any/c
any/c
ht
hash?
try-order?
any/c
#f
Returns a list of the key–value pairs of
ht
in an unspecified order.
If
try-order?
is true, then the order of keys and values is normalized
under certain circumstances. See
hash-map
for further explanations on
try-order?
and on information about modifying
ht
during
hash->list
See also the
caveats concerning concurrent modification
above.
Changed in version 8.3.0.11 of package
base
: Added the
try-order?
argument.
procedure
hash-keys-subset?
ht1
ht2
boolean?
ht1
hash?
ht2
hash?
Returns
#t
if the keys of
ht1
are a subset of or
the same as the keys of
ht2
. The hash tables must both use
the same key-comparison function (
equal?
equal-always?
eqv?
, or
eq?
), otherwise the
exn:fail:contract
exception is raised.
Using
hash-keys-subset?
on immutable hash tables can be much
faster than iterating through the keys of
ht1
to make sure
that each is in
ht2
Added in version 6.5.0.8 of package
base
procedure
hash-for-each
ht
proc
try-order?
void?
ht
hash?
proc
any/c
any/c
->
any
try-order?
any/c
#f
Applies
proc
to each element in
ht
(for the
side-effects of
proc
) in an unspecified order. The procedure
proc
is called each time with a key and its value.
See
hash-map
for information about
try-order?
and
about modifying
ht
within
proc
See also the
caveats concerning concurrent modification
above.
Changed in version 6.3 of package
base
: Added the
try-order?
argument.
Changed in version 7.1.0.7: Added guarantees for
try-order?
procedure
hash-count
ht
exact-nonnegative-integer?
ht
hash?
Returns the number of keys mapped by
ht
For the
CS
implementation of Racket, the result is always
computed in constant time and atomically. For the
BC
implementation
of Racket, the result is computed in constant time and atomically only if
ht
does not retain keys weakly or like an
ephemeron
otherwise, a traversal is required to count the keys.
procedure
hash-empty?
ht
boolean?
ht
hash?
Equivalent to
zero?
hash-count
ht
procedure
hash-iterate-first
ht
or/c
#f
exact-nonnegative-integer?
ht
hash?
Returns
#f
if
ht
contains no elements, otherwise
it returns an integer that is an index to the first element in the hash
table; “first” refers to an unspecified ordering of the table
elements, and the index values are not necessarily consecutive
integers.
For a mutable
ht
, this index is guaranteed to refer to the
first item only as long as no items are added to or removed from
ht
. More generally, an index is guaranteed to be a
valid hash index
for a given hash table only as long it
comes from
hash-iterate-first
or
hash-iterate-next
and only as long as the hash table is not modified. In the case of a
hash table with weakly held keys or keys held like
ephemerons
the hash table can be implicitly modified by the garbage collector
(see
Garbage Collection
) when it discovers that the key is not
reachable.
procedure
hash-iterate-next
ht
pos
or/c
#f
exact-nonnegative-integer?
ht
hash?
pos
exact-nonnegative-integer?
Returns either an integer that is an index to the element in
ht
after the element indexed by
pos
(which is not
necessarily one more than
pos
) or
#f
if
pos
refers to the last element in
ht
If
pos
is not a
valid hash index
of
ht
then the result may be
#f
or it may be the next later index
that remains valid. The latter result is guaranteed if a hash table
has been modified only by the removal of keys.
Changed in version 7.0.0.10 of package
base
: Handle an invalid index by returning
#f
instead of raising
exn:fail:contract
procedure
hash-iterate-key
ht
pos
any/c
ht
hash?
pos
exact-nonnegative-integer?
procedure
hash-iterate-key
ht
pos
bad-index-v
any/c
ht
hash?
pos
exact-nonnegative-integer?
bad-index-v
any/c
Returns the key for the element in
ht
at index
pos
If
pos
is not a
valid hash index
for
ht
the result is
bad-index-v
if provided, otherwise the
exn:fail:contract
exception is raised.
Changed in version 7.0.0.10 of package
base
: Added the optional
bad-index-v
argument.
procedure
hash-iterate-value
ht
pos
any/c
ht
hash?
pos
exact-nonnegative-integer?
procedure
hash-iterate-value
ht
pos
bad-index-v
any/c
ht
hash?
pos
exact-nonnegative-integer?
bad-index-v
any/c
Returns the value for the element in
ht
at index
pos
If
pos
is not a
valid hash index
for
ht
the result is
bad-index-v
if provided, otherwise the
exn:fail:contract
exception is raised.
Changed in version 7.0.0.10 of package
base
: Added the optional
bad-index-v
argument.
procedure
hash-iterate-pair
ht
pos
cons/c
any/c
any/c
ht
hash?
pos
exact-nonnegative-integer?
procedure
hash-iterate-pair
ht
pos
bad-index-v
cons/c
any/c
any/c
ht
hash?
pos
exact-nonnegative-integer?
bad-index-v
any/c
Returns a pair containing the key and value for the element
in
ht
at index
pos
If
pos
is not a
valid hash index
for
ht
the result is
cons
bad-index-v
bad-index-v
if
bad-index-v
is provided, otherwise the
exn:fail:contract
exception is raised.
Added in version 6.4.0.5 of package
base
Changed in version 7.0.0.10: Added the optional
bad-index-v
argument.
procedure
hash-iterate-key+value
ht
pos
any/c
any/c
ht
hash?
pos
exact-nonnegative-integer?
procedure
hash-iterate-key+value
ht
pos
bad-index-v
any/c
any/c
ht
hash?
pos
exact-nonnegative-integer?
bad-index-v
any/c
Returns the key and value for the element in
ht
at index
pos
If
pos
is not a
valid hash index
for
ht
the result is
values
bad-index-v
bad-index-v
if
bad-index-v
is provided, otherwise the
exn:fail:contract
exception is raised.
Added in version 6.4.0.5 of package
base
Changed in version 7.0.0.10: Added the optional
bad-index-v
argument.
procedure
hash-copy
ht
and/c
hash?
not/c
immutable?
ht
hash?
Returns a mutable hash table with the same mappings, same
key-comparison mode, and same key-holding strength as
ht
4.15.1
Additional Hash Table Functions
require
racket/hash
package:
base
The bindings documented in this section are provided by the
racket/hash
library, not
racket/base
or
racket
procedure
hash-union
ht0
ht
...
#:combine
combine
#:combine/key
combine/key
and/c
hash?
immutable?
ht0
and/c
hash?
immutable?
ht
hash?
combine
->
any/c
any/c
any/c
lambda
error
hash-union
....
combine/key
->
any/c
any/c
any/c
any/c
lambda
combine
Computes the union of
ht0
with each hash table
ht
by functional
update, adding each element of each
ht
to
ht0
in turn. For each
key
and value
, if a mapping from
to some value
v0
already exists, it is replaced with a mapping from
to
combine/key
v0
Examples:
hash-union
make-immutable-hash
one
make-immutable-hash
two
make-immutable-hash
three
'#hash((1 . one) (2 . two) (3 . three))
hash-union
make-immutable-hash
one
uno
two
dos
make-immutable-hash
eins
un
zwei
deux
#:combine/key
lambda
v1
v2
append
v1
v2
'#hash((1 . (one uno eins un)) (2 . (two dos zwei deux)))
procedure
hash-union!
ht0
ht
...
#:combine
combine
#:combine/key
combine/key
void?
ht0
and/c
hash?
not/c
immutable?
ht
hash?
combine
->
any/c
any/c
any/c
lambda
error
hash-union
....
combine/key
->
any/c
any/c
any/c
any/c
lambda
combine
Computes the union of
ht0
with each hash table
ht
by mutable
update, adding each element of each
ht
to
ht0
in turn. For each
key
and value
, if a mapping from
to some value
v0
already exists, it is replaced with a mapping from
to
combine/key
v0
Examples:
define
make-hash
'#hash()
hash-union!
make-immutable-hash
one
uno
two
dos
'#hash((1 . (one uno)) (2 . (two dos)))
hash-union!
make-immutable-hash
eins
un
zwei
deux
#:combine/key
lambda
v1
v2
append
v1
v2
'#hash((1 . (one uno eins un)) (2 . (two dos zwei deux)))
procedure
hash-intersect
ht0
ht
...
#:combine
combine
#:combine/key
combine/key
and/c
hash?
immutable?
ht0
and/c
hash?
immutable?
ht
hash?
combine
->
any/c
any/c
any/c
lambda
error
hash-intersect
...
combine/key
->
any/c
any/c
any/c
any/c
lambda
combine
Constructs the hash table which is the intersection of
ht0
with every hash table
ht
. In the resulting hash table, a key
is mapped to a combination of the values to which
is mapped in each of the hash tables. The final values are
computed by stepwise combination of the values appearing in each of
the hash tables by applying
combine/key
vi
where
vi
is the value to which
is mapped in the
-th hash table
ht
, and
is the accumulation of the values from the previous steps.
The comparison predicate of the first argument (
eq?
eqv?
equal-always?
equal?
) determines the
one for the result.
Examples:
hash-intersect
make-immutable-hash
make-immutable-hash
#:combine
'#hash((a . 5) (b . 7))
hash-intersect
make-immutable-hash
make-immutable-hash
#:combine/key
lambda
v1
v2
if
eq?
v1
v2
v1
v2
'#hash((a . 5) (b . -3))
Added in version 7.9.0.1 of package
base
procedure
hash-filter
ht
pred
hash?
ht
hash?
pred
->
any/c
any/c
boolean?
Filters the
hash?
ht
based on a predicate
pred
applied to both its keys and values. This function
constructs a new hash table that includes only those key-value pairs
from the input
ht
for which the predicate
pred
returns true when applied simultaneously to the keys and values of
ht
. The output hash table retains the mutability and the key
comparison predicate (e.g.,
eqv?
equal-always?
equal?
) of the input hash table
ht
, ensuring that
the structural and operational properties of the original hash are
preserved in the output.
Examples:
hash-filter
for/hash
num
values
num
num
and
even?
'#hash((1 . 2) (2 . 4))
hash-filter
make-hash
'#hash()
hash-filter
make-hasheq
#f
"false"
#t
"true"
and
eq?
#t
string=?
"true"
'#hasheq((#t . "true"))
hash-filter
hash
list
pair
vector
vector
and
list?
symbol?
'#hash(((1 2) . pair))
hash-filter
hash
"one"
"two"
"three"
and
not
number?
number?
'#hash(("three" . 3))
Added in version 8.13.0.4 of package
base
procedure
hash-filter-keys
ht
pred
hash?
ht
hash?
pred
procedure?
Filters the
hash?
ht
based on a predicate
pred
applied to its keys.
This function constructs a new hash table that includes only those key-value pairs
from the input
ht
for which the predicate
pred
returns true when
applied to the keys. Similar to
hash-filter-values
, the output hash table
maintains the mutability and key comparator of the input hash table, ensuring that
the structural and operational properties of the original hash are retained.
Examples:
hash-filter-keys
for/hash
num
values
num
'#hash((1 . 0) (2 . 0))
hash-filter-keys
make-hash
'#hash()
hash-filter-keys
make-hasheq
#f
"false"
#t
"true"
eq?
#t
'#hasheq((#t . "true"))
hash-filter-keys
hash
list
pair
vector
vector
list?
'#hash(((1 2) . pair))
hash-filter-keys
hash
"one"
"two"
"three"
lambda
number?
'#hash((2 . "two"))
hash-filter-keys
hash
apple
"fruit"
carrot
"vegetable"
"banana"
"fruit"
lambda
symbol?
'#hash((apple . "fruit") (carrot . "vegetable"))
Added in version 8.12.0.9 of package
base
procedure
hash-filter-values
ht
pred
hash?
ht
hash?
pred
procedure?
Filters the
hash?
ht
based on a predicate
pred
applied to its values. This function returns a new hash
table containing only the key-value pairs for which the predicate
pred
returns true when applied to the values of
ht
The resulting hash table retains the mutability and the key comparison
predicate (e.g.,
eq?
eqv?
equal-always?
equal?
) of the input hash table
ht
Examples:
hash-filter-values
for/hash
num
values
num
num
'#hash((1 . 1) (2 . 2))
hash-filter-values
make-hash
'#hash()
hash-filter-values
make-hasheqv
"one"
"two"
eqv?
"two"
'#hasheqv((2 . "two"))
hash-filter-values
hash
one
"1"
two
three
"3"
lambda
string?
'#hash((one . "1") (three . "3"))
hash-filter-values
hash
list
list
vector
string
"hello"
lambda
vector?
'#hash((vector . #(4 5 6)))
hash-filter-values
hash
nested-hash
hash
nested-list
list
lambda
hash?
'#hash((nested-hash . #hash((a . 1) (b . 2))))
Added in version 8.12.0.9 of package
base
top
contents
← prev
up
next →