Return to ch17.r CVS log

Up to [CSRG BSD Unix] / 43BSD / ucb / lisp / lisplib / manual

Annotation of 43BSD/ucb/lisp/lisplib/manual/ch17.r, revision 1.1

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.