[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
doco hash tables
From: |
Kevin Ryde |
Subject: |
doco hash tables |
Date: |
Thu, 31 Jul 2003 09:02:34 +1000 |
User-agent: |
Gnus/5.090019 (Oort Gnus v0.19) Emacs/21.2 (gnu/linux) |
This is a proposed revision for the hash tables node. The main aim is
to cut down the duplication between the function descriptions, to try
to the basic operations clearer. I've tried to spruce up the
introductory words too.
An example of using the hashx functions might be nice, maybe
case-insensitive string keys like already mentioned, if someone's got
a nice hash function along those lines.
I noticed there's no hashx-remove!, is that merely an omission (in the
code that is), or am I missing something?
Is it true that modifying the hash table while hash-fold is iterating
over it will have unpredicatable results? (As far as the elements
seen or not seen go.) Probably worth a warning about that.
Hash Table Reference
....................
A hash table stores key/value pairs, designed for fast lookups by key.
Keys and values can be any Scheme objects.
A hash table is similar to an association list in the way it holds
keys and values (*note Association Lists::), but an association list
requires a linear search to locate an element, which can be slow when
the list is long. A hash table instead uses arithmetic to make a array
index from a key, so lookups take a more or less fixed time no matter
how big the table.
Like the association list functions, the hash table functions come in
several varieties, according to the equality test used for the keys.
Plain `hash-' functions use `equal?', `hashq-' functions use `eq?',
`hashv-' functions use `eqv?', and the `hashx-' functions use an
application supplied test (for instance to implement case insensitive
strings).
A single `make-hash-table' creates a hash table suitable for use
with any set of functions, but it's imperative that just one set is
then used consistently, or results will be unpredictable.
Hash tables are implemented as a vector indexed by an integer formed
from the key, and a association list of key/value pairs for each bucket
in case distinct keys hash together. Direct access to the pairs in
those lists is provided by the `-handle-' functions.
For the `hashx-' "extended" routines, an application supplies a HASH
function producing an integer index (as per `hashq' etc below), and an
ASSOC alist search function (as per `assq' etc, *Note Retrieving Alist
Entries::.). The aim in the HASH function is to have different keys
spread out across the vector, so the bucket lists don't become long,
but the exact values generated are otherwise arbitrary.
- Scheme Procedure: make-hash-table size
Create a new hash table of SIZE slots. Note that the number of
slots does not limit the size of the table, it just tells how large
the underlying vector will be. The SIZE should be similar to the
expected number of elements which will be added to the table, but
they need not match. For good performance, it might be a good
idea to use a prime number as the SIZE.
- Scheme Procedure: hash-ref table key [dflt]
- Scheme Procedure: hashq-ref table key [dflt]
- Scheme Procedure: hashv-ref table key [dflt]
- Scheme Procedure: hashx-ref hash assoc table key [dflt]
- C Function: scm_hash_ref (table, key, dflt)
- C Function: scm_hashq_ref (table, key, dflt)
- C Function: scm_hashv_ref (table, key, dflt)
- C Function: scm_hashx_ref (hash, assoc, table, key, dflt)
Lookup KEY in the given hash TABLE, and return the associated
value. If KEY is not found, return DFLT, or `#f' if DFLT is not
given. (For the C functions, DFLT must be given.)
- Scheme Procedure: hash-set! table key val
- Scheme Procedure: hashq-set! table key val
- Scheme Procedure: hashv-set! table key val
- Scheme Procedure: hashx-set! hash assoc table key val
- C Function: scm_hash_set_x (table, key, val)
- C Function: scm_hashq_set_x (table, key, val)
- C Function: scm_hashv_set_x (table, key, val)
- C Function: scm_hashx_set_x (hash, assoc, table, key, val)
Associate VAL with KEY in the given hash TABLE. If KEY is already
present then it's associated value is changed. If it's not
present then a new entry is created.
- Scheme Procedure: hash-remove! table key
- Scheme Procedure: hashq-remove! table key
- Scheme Procedure: hashv-remove! table key
- C Function: scm_hash_remove_x (table, key)
- C Function: scm_hashq_remove_x (table, key)
- C Function: scm_hashv_remove_x (table, key)
Remove any association for KEY in the given hash TABLE. If KEY is
not in TABLE then nothing is done.
- Scheme Procedure: hash key size
- Scheme Procedure: hashq key size
- Scheme Procedure: hashv key size
- C Function: scm_hash (key, size)
- C Function: scm_hashq (key, size)
- C Function: scm_hashv (key, size)
Return a hash value for KEY. This is a number in the range 0 to
SIZE - 1, which is suitable for use in a hash table of the given
SIZE.
Note that `hashq' and `hashv' may use internal addresses of
objects, so if an object is garbage collected and re-created it can
have a different hash value, even when the two are notionally
`eq?'. For instance with symbols,
(hashq 'something 123) => 19
(gc)
(hashq 'something 123) => 62
In normal use this is not a problem, since an object entered into a
hash table won't be garbage collected until removed. It's only if
hashing calculations are somehow separated from normal references
to an object that its lifetime needs to be considered.
- Scheme Procedure: hash-get-handle table key
- Scheme Procedure: hashq-get-handle table key
- Scheme Procedure: hashv-get-handle table key
- Scheme Procedure: hashx-get-handle hash assoc table key
- C Function: scm_hash_get_handle (table, key)
- C Function: scm_hashq_get_handle (table, key)
- C Function: scm_hashv_get_handle (table, key)
- C Function: scm_hashx_get_handle (hash, assoc, table, key)
Return the `(KEY . VALUE)' pair for KEY in the given hash TABLE,
or `#f' if KEY is not in TABLE.
- Scheme Procedure: hash-create-handle! table key init
- Scheme Procedure: hashq-create-handle! table key init
- Scheme Procedure: hashv-create-handle! table key init
- Scheme Procedure: hashx-create-handle! hash assoc table key init
- C Function: scm_hash_create_handle_x (table, key, init)
- C Function: scm_hashq_create_handle_x (table, key, init)
- C Function: scm_hashv_create_handle_x (table, key, init)
- C Function: scm_hashx_create_handle_x (hash, assoc, table, key, init)
Return the `(KEY . VALUE)' pair for KEY in the given hash TABLE.
If KEY is not in TABLE then create an entry for it with INIT as
the value, and return that pair.
- Scheme Procedure: hash-fold proc init table
- C Function: scm_hash_fold (proc, init, table)
Accumulate a result by applying PROC to the elements of the given
hash TABLE.
Each call is `(PROC KEY VALUE PRIOR-RESULT)', where KEY and VALUE
are from the TABLE and PRIOR-RESULT is the return from the previous
PROC call. For the first call, PRIOR-RESULT is the given INIT
value. Calls are made over the elements in an unspecified order.
For example, the following returns an alist comprising all the
entries from a hash table `mytable',
(hash-fold acons '() mytable)
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- doco hash tables,
Kevin Ryde <=