![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ch17.n CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps2 / 09.lisp|
Return to ch17.n CVS log | Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps2 / 09.lisp |
1.1 root 1: .\" Copyright (c) 1980 Regents of the University of California.
2: .\" All rights reserved. The Berkeley software License Agreement
3: .\" specifies the terms and conditions for redistribution.
4: .\"
5: .\" @(#)ch17.n 6.2 (Berkeley) 5/14/86
6: .\"
7: ." $Header: ch17.n,v 40.1 84/08/08 21:36:08 layer Exp $
8: ." (c) Copyright 1984, Franz Inc., Berkeley California
9: .Lc Hash\ Tables 17
10: .sh 2 Overview \n(ch 1
11: .pp
12: A hash table is an object that can efficiently map a given object to another.
13: Each hash table is a collection of entries,
14: each of which associates a unique \fIkey\fP with a \fIvalue\fP.
15: There are elemental functions to add, delete, and find entries
16: based on a particular key.
17: Finding a value in a hash table is relatively fast compared to
18: looking up values in, for example, an assoc list or property list.
19: .pp
20: Adding a key to a hash table modifies the hash table, and so
21: it is a descructive operation.
22: .pp
23: There are two different kinds of hash tables: those that use the
24: function \fIequal\fP for the comparing of keys, and those that
25: use \fIeq\fP, the default.
26: If a key is "eq" to another object, then a match is assumed.
27: Likewise with "equal".
28: .sh 2 Functions
29: .Lf makeht "'x_size ['s_test]"
30: .Re
31: A hash table of x_size hash buckets.
32: If present, s_test is used as the test to compare keys in the
33: hash table, the default being \fBeq\fP.
34: \fIEqual\fP might be used to create a hash table where the
35: keys are to be lists (or any lisp object).
36: .No
37: At this time, hash tables are implemented on top of vectors.
38: .Lf hash-table-p "'H_arg"
39: .Re
40: t if H_arg is a hash table.
41: .No
42: Since hash tables are really vectors, the lisp type of a hash table
43: is a vector, so that given a vector, this function will return t.
44: .Lf gethash "'g_key 'H_htable ['g_default]"
45: .Re
46: the value associated the key g_key in hash table H_htable.
47: If there is not an entry given by the key and g_default is specified,
48: then g_default is returned, otherwise, a symbol that is unbound
49: is returned.
50: This is so that \fBnil\fP can be a associated with a key.
51: .No
52: \fIsetf\fP may be used to set the value assocaited with a key.
53: .Lf remhash "'g_key 'H_htable"
54: .Re
55: t if there was an entry for g_key in the hash table
56: H_htable, nil otherwise. In the case of a match, the
57: entry and associated object are removed from the hash
58: table.
59: .Lf maphash "'u_func 'H_htable"
60: .Re
61: nil.
62: .No
63: The function u_func is applied to every element in the
64: hash table H_htable. The function is called with two arguments:
65: the key and value of an element.
66: The mapped function should not add or delete object from the
67: table because the results would be unpredicable.
68: .Lf clrhash "'H_htable"
69: .Re
70: the hash table cleared of all entries.
71: .Lf hash-table-count "'H_htable"
72: .Re
73: the number of entries in H_htable. Given a new hash table
74: with no entries, this function returns zero.
75: .Eb
76: ; make a vanilla hash table using "eq" to compare items...
77: \-> (setq black-box (makeht 20))
78: hash-table[26]
79: \-> (hash-table-p black-box)
80: t
81: \-> (hash-table-count black-box)
82: 0
83: \-> (setf (gethash 'key black-box) '(the value associated with the key))
84: key
85: \-> (gethash 'key black-box)
86: (the value associated with the key)
87: \-> (hash-table-count black-box)
88: 1
89: \-> (addhash 'composer black-box 'franz)
90: composer
91: \-> (gethash 'composer black-box)
92: franz
93: \-> (maphash '(lambda (key val) (msg "key " key " value " val N)) black-box)
94: key composer value franz
95: key key value (the value associated with the key)
96: nil
97: \-> (clrhash black-box)
98: hash-table[26]
99: \-> (hash-table-count black-box)
100: 0
101: \-> (maphash '(lambda (key val) (msg "key " key " value " val N)) black-box)
102: nil
103:
104: ; here is an example using "equal" as the comparator
105: \-> (setq ht (makeht 10 'equal))
106: hash-table[16]
107: \-> (setf (gethash '(this is a key) ht) '(and this is the value))
108: (this is a key)
109: \-> (gethash '(this is a key) ht)
110: (and this is the value)
111: ; the reader makes a new list each time you type it...
112: \-> (setq x '(this is a key))
113: (this is a key)
114: \-> (setq y '(this is a key))
115: (this is a key)
116: ; so these two lists are really different lists that compare "equal"
117: ; not "eq"
118: \-> (eq x y)
119: nil
120: ; but since we are using "equal" to compare keys, we are OK...
121: \-> (gethash x ht)
122: (and this is the value)
123: \-> (gethash y ht)
124: (and this is the value)
125: .Ee
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.