CHAPTER  17


                        Hash Tables






   1.1.  Overview

           A hash table is an object  that  can  efficiently
      map  a  given object to another.  Each hash table is a
      collection of entries,  each  of  which  associates  a
      unique  _k_e_y  with  a _v_a_l_u_e.  There are elemental func-
      tions to add, delete, and find entries based on a par-
      ticular key.  Finding a value in a hash table is rela-
      tively fast compared to  looking  up  values  in,  for
      example, an assoc list or property list.

           Adding a key to a hash table  modifies  the  hash
      table, and so it is a descructive operation.

           There are two different  kinds  of  hash  tables:
      those that use the function _e_q_u_a_l for the comparing of
      keys, and those that use _e_q, the default.  If a key is
      "eq"  to  another  object,  then  a  match is assumed.
      Likewise with "equal".



   1.2.  Functions

(makeht 'x_size ['s_test])

     RETURNS: A hash  table  of  x_size  hash  buckets.   If
              present, s_test is used as the test to compare
              keys in the hash table, the default being  eq.
              _E_q_u_a_l  might  be  used  to create a hash table
              where the keys are to be lists  (or  any  lisp
              object).

     NOTE: At this time, hash tables are implemented on  top
           of vectors.







9

9Hash Tables                                             17-1







Hash Tables                                             17-2


(hash-table-p 'H_arg)

     RETURNS: t if H_arg is a hash table.

     NOTE: Since hash tables are really  vectors,  the  lisp
           type of a hash table is a vector, so that given a
           vector, this function will return t.

(gethash 'g_key 'H_htable ['g_default])

     RETURNS: the value associated the  key  g_key  in  hash
              table  H_htable.   If  there  is  not an entry
              given by the key and g_default  is  specified,
              then  g_default is returned, otherwise, a sym-
              bol that is unbound is returned.  This  is  so
              that nil can be a associated with a key.

     NOTE: _s_e_t_f may be used to set the value assocaited with
           a key.

(remhash 'g_key 'H_htable)

     RETURNS: t if there was an entry for g_key in the  hash
              table H_htable, nil otherwise.  In the case of
              a match, the entry and associated  object  are
              removed from the hash table.

(maphash 'u_func 'H_htable)

     RETURNS: nil.

     NOTE: The function u_func is applied to  every  element
           in  the  hash  table  H_htable.   The function is
           called with two arguments: the key and  value  of
           an  element.   The mapped function should not add
           or delete  object  from  the  table  because  the
           results would be unpredicable.

(clrhash 'H_htable)

     RETURNS: the hash table cleared of all entries.











9

9                                       Printed: May 22, 1985







Hash Tables                                             17-3


(hash-table-count 'H_htable)

     RETURNS: the number of entries in  H_htable.   Given  a
              new  hash table with no entries, this function
              returns zero.















































9

9                                       Printed: May 22, 1985







Hash Tables                                             17-4



    ____________________________________________________

    ; make a vanilla hash table using "eq" to compare items...
    -> (setq black-box (makeht 20))
    hash-table[26]
    -> (hash-table-p black-box)
    t
    -> (hash-table-count black-box)
    0
    -> (setf (gethash 'key black-box) '(the value associated with the key))
    key
    -> (gethash 'key black-box)
    (the value associated with the key)
    -> (hash-table-count black-box)
    1
    -> (addhash 'composer black-box 'franz)
    composer
    -> (gethash 'composer black-box)
    franz
    -> (maphash '(lambda (key val) (msg "key " key " value " val N)) black-box)
    key composer value franz
    key key value (the value associated with the key)
    nil
    -> (clrhash black-box)
    hash-table[26]
    -> (hash-table-count black-box)
    0
    -> (maphash '(lambda (key val) (msg "key " key " value " val N)) black-box)
    nil

    ; here is an example using "equal" as the comparator
    -> (setq ht (makeht 10 'equal))
    hash-table[16]
    -> (setf (gethash '(this is a key) ht) '(and this is the value))
    (this is a key)
    -> (gethash '(this is a key) ht)
    (and this is the value)
    ; the reader makes a new list each time you type it...
    -> (setq x '(this is a key))
    (this is a key)
    -> (setq y '(this is a key))
    (this is a key)
    ; so these two lists are really different lists that compare "equal"
    ; not "eq"
    -> (eq x y)
    nil
    ; but since we are using "equal" to compare keys, we are OK...
    -> (gethash x ht)
    (and this is the value)
    -> (gethash y ht)
    (and this is the value)
    ____________________________________________________


                                       Printed: May 22, 1985







Hash Tables                                             17-5






















































9

9                                       Printed: May 22, 1985