Return to ch17.n CVS log

Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps2 / 09.lisp

Annotation of 43BSDReno/share/doc/ps2/09.lisp/ch17.n, revision 1.1

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.