![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ch17.r CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / ucb / lisp / lisplib / manual|
Return to ch17.r CVS log | Up to [CSRG BSD Unix] / 43BSD / ucb / lisp / lisplib / manual |
1.1 root 1:
2:
3:
4:
5:
6:
7:
8: CHAPTER 17
9:
10:
11: Hash Tables
12:
13:
14:
15:
16:
17:
18: 1.1. Overview
19:
20: A hash table is an object that can efficiently
21: map a given object to another. Each hash table is a
22: collection of entries, each of which associates a
23: unique _k_e_y with a _v_a_l_u_e. There are elemental func-
24: tions to add, delete, and find entries based on a par-
25: ticular key. Finding a value in a hash table is rela-
26: tively fast compared to looking up values in, for
27: example, an assoc list or property list.
28:
29: Adding a key to a hash table modifies the hash
30: table, and so it is a descructive operation.
31:
32: There are two different kinds of hash tables:
33: those that use the function _e_q_u_a_l for the comparing of
34: keys, and those that use _e_q, the default. If a key is
35: "eq" to another object, then a match is assumed.
36: Likewise with "equal".
37:
38:
39:
40: 1.2. Functions
41:
42: (makeht 'x_size ['s_test])
43:
44: RETURNS: A hash table of x_size hash buckets. If
45: present, s_test is used as the test to compare
46: keys in the hash table, the default being eq.
47: _E_q_u_a_l might be used to create a hash table
48: where the keys are to be lists (or any lisp
49: object).
50:
51: NOTE: At this time, hash tables are implemented on top
52: of vectors.
53:
54:
55:
56:
57:
58:
59:
60: 9
61:
62: 9Hash Tables 17-1
63:
64:
65:
66:
67:
68:
69:
70: Hash Tables 17-2
71:
72:
73: (hash-table-p 'H_arg)
74:
75: RETURNS: t if H_arg is a hash table.
76:
77: NOTE: Since hash tables are really vectors, the lisp
78: type of a hash table is a vector, so that given a
79: vector, this function will return t.
80:
81: (gethash 'g_key 'H_htable ['g_default])
82:
83: RETURNS: the value associated the key g_key in hash
84: table H_htable. If there is not an entry
85: given by the key and g_default is specified,
86: then g_default is returned, otherwise, a sym-
87: bol that is unbound is returned. This is so
88: that nil can be a associated with a key.
89:
90: NOTE: _s_e_t_f may be used to set the value assocaited with
91: a key.
92:
93: (remhash 'g_key 'H_htable)
94:
95: RETURNS: t if there was an entry for g_key in the hash
96: table H_htable, nil otherwise. In the case of
97: a match, the entry and associated object are
98: removed from the hash table.
99:
100: (maphash 'u_func 'H_htable)
101:
102: RETURNS: nil.
103:
104: NOTE: The function u_func is applied to every element
105: in the hash table H_htable. The function is
106: called with two arguments: the key and value of
107: an element. The mapped function should not add
108: or delete object from the table because the
109: results would be unpredicable.
110:
111: (clrhash 'H_htable)
112:
113: RETURNS: the hash table cleared of all entries.
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125: 9
126:
127: 9 Printed: May 22, 1985
128:
129:
130:
131:
132:
133:
134:
135: Hash Tables 17-3
136:
137:
138: (hash-table-count 'H_htable)
139:
140: RETURNS: the number of entries in H_htable. Given a
141: new hash table with no entries, this function
142: returns zero.
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190: 9
191:
192: 9 Printed: May 22, 1985
193:
194:
195:
196:
197:
198:
199:
200: Hash Tables 17-4
201:
202:
203:
204: ____________________________________________________
205:
206: ; make a vanilla hash table using "eq" to compare items...
207: -> (setq black-box (makeht 20))
208: hash-table[26]
209: -> (hash-table-p black-box)
210: t
211: -> (hash-table-count black-box)
212: 0
213: -> (setf (gethash 'key black-box) '(the value associated with the key))
214: key
215: -> (gethash 'key black-box)
216: (the value associated with the key)
217: -> (hash-table-count black-box)
218: 1
219: -> (addhash 'composer black-box 'franz)
220: composer
221: -> (gethash 'composer black-box)
222: franz
223: -> (maphash '(lambda (key val) (msg "key " key " value " val N)) black-box)
224: key composer value franz
225: key key value (the value associated with the key)
226: nil
227: -> (clrhash black-box)
228: hash-table[26]
229: -> (hash-table-count black-box)
230: 0
231: -> (maphash '(lambda (key val) (msg "key " key " value " val N)) black-box)
232: nil
233:
234: ; here is an example using "equal" as the comparator
235: -> (setq ht (makeht 10 'equal))
236: hash-table[16]
237: -> (setf (gethash '(this is a key) ht) '(and this is the value))
238: (this is a key)
239: -> (gethash '(this is a key) ht)
240: (and this is the value)
241: ; the reader makes a new list each time you type it...
242: -> (setq x '(this is a key))
243: (this is a key)
244: -> (setq y '(this is a key))
245: (this is a key)
246: ; so these two lists are really different lists that compare "equal"
247: ; not "eq"
248: -> (eq x y)
249: nil
250: ; but since we are using "equal" to compare keys, we are OK...
251: -> (gethash x ht)
252: (and this is the value)
253: -> (gethash y ht)
254: (and this is the value)
255: ____________________________________________________
256:
257:
258: Printed: May 22, 1985
259:
260:
261:
262:
263:
264:
265:
266: Hash Tables 17-5
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321: 9
322:
323: 9 Printed: May 22, 1985
324:
325:
326:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.