home *** CD-ROM | disk | FTP | other *** search
/ Gold Fish 3 / goldfish_volume_3.bin / files / dev / e / amigae / src / class / hash / hash.doc next >
Text File  |  1992-09-02  |  6KB  |  176 lines
  1. HASH.M: flexible and fast hashing functions.
  2.  
  3. note: if you have no clue what hashing is, you might want to read a little
  4.       explanation I gave at the end of this doc first.
  5.  
  6. why use these hashing functions?
  7. --------------------------------
  8. simple:   one does not need to know anything about how hashing to make
  9.           good use of this module.
  10. flexible: the functions do not make _any_ assumptions upon the nature
  11.           of the data, the size of it, or anything else. you may therefore
  12.           use it to hash strings, graphical data, etc.
  13. fast:     not only does this module use a high performance hashing function,
  14.           but also the most time-consuming function, hash_find() has been
  15.           written in optimised inline assembly.
  16.  
  17. the object
  18. ----------
  19.  
  20. OBJECT hashtable
  21.   hashtable(tablesize)
  22.   end()
  23.   find(ptr,len)
  24.   add(link,hashvalue,ptr,len)
  25.   iterate(do_proc)
  26.   calc_hash_spread()
  27. ENDOBJECT
  28.  
  29. methods
  30. -------
  31.  
  32.     hastable(tablesize)
  33.  
  34. This constructor initialises an empty hashtable. tablesize is the size of
  35. the hashtable, predifined are some usefull values:
  36.  
  37.         tablesize    size in kb
  38. HASH_NORMAL    211*        1
  39. HASH_MEDIUM    941        4
  40. HASH_HEAVY    3911        16
  41. HASH_HEAVIER    16267        64
  42.  
  43. (*) the tablesizes above are primes close to 2 to the power
  44.     of 8,10,12,14,16 (for performance reasons)
  45.  
  46. The larger the table, the faster the search.
  47. instead of these constanst, you can also use your own size,
  48. if you wish. the size should however be between 2 and 65535,
  49. and a prime for best performance.
  50.  
  51. example:
  52.  
  53. DEF t:PTR TO hashtable
  54. NEW t.hashtable(HASH_HEAVY)
  55.  
  56. may raise: "MEM"
  57.  
  58.  
  59.     end()
  60.  
  61. frees table. memory is also deallocated automatically at the end of
  62. the program. example:
  63.  
  64. END t
  65.  
  66.  
  67.     hashlink,hashvalue:=t.find(data,len)
  68.  
  69. Tries to find data with length len in hash table. When data is not present
  70. in the table, hashlink will NIL. You'll need to store hashvalue only if you
  71. wish to call add() next, and hashlink only if you wish to access the data
  72. related to whatever you hashed next (see below).
  73.  
  74.  
  75.     add(link:PTR TO hashlink,hashvalue,data,len)
  76.  
  77.  
  78. adds data to table. you'll need to call find() before this one,
  79. not only to know the hashvalue this function needs, but also to be
  80. sure data isn't already in the table. link must be a subclass of
  81. 'hashlink':
  82.  
  83. OBJECT hashlink
  84. ENDOBJECT     /* SIZEOF=12 */
  85.  
  86. the hashtable uses this object to store data in the table. if you wish
  87. to associate data with whatever you're hashing, make a subclass:
  88.  
  89. OBJECT mylink OF hashlink
  90.   type:INT            -> extra field
  91. ENDOBJECT
  92.  
  93. these objects are also the ones return by find if data is already present in
  94. table. example:
  95.  
  96. t.add(NEW linkptr,hashv,ptr,len)
  97.  
  98. ptr and len are the same ones you passed to find(). note that add() does
  99. not copy the 'ptr'.
  100.  
  101.  
  102.     total,num:=t.iterate(proc)
  103.  
  104. walks through the whole hashtable, calling proc for every link.
  105. proc must be something like:
  106.  
  107. PROC it(link:PTR TO hashlink,depth)
  108.  
  109. depth is how deep the link hangs in a chain, i.e. minimally 1.
  110. returned from iterate() is the sum of all returnvalues from
  111. calling proc, and the number of links visited.
  112.  
  113.     calc_hash_spread()
  114.  
  115. makes use of iterate() to calculate the average number of StrCmp's
  116. needed to find some data in this table. see hashtest.e for example use.
  117.  
  118.  
  119. example use
  120. -----------
  121.  
  122. Imagine we're programming a compiler, like EC. To keep things simple,
  123. we only do global variables. first, set up the table:
  124.  
  125. DEF t:PTR TO hashtable, identinfo:PTR TO mylink        -> see above
  126. NEW t.hashtable(HASH_MEDIUM)
  127.  
  128. now the following piece of code would be entered when we've read
  129. an identifier. in 'ident' and 'len' we have the identifier,
  130. and 'status' says wether we are currently in the scope of a DEF or not:
  131.  
  132. -> see if ident is already there
  133. identinfo,hashvalue:=t.find(ident,len:=EstrLen(ident))
  134.  
  135. IF identinfo
  136.   IF status=DEFINITION THEN Raise('double declaration!')
  137.   -> do something with identinfo.type here, for example
  138. ELSE
  139.   IF status=USE THEN Raise('unknown variable!')
  140.   t.add(NEW identinfo,hashvalue,ident,len)
  141.   -> assign here to identinfo.type, for example
  142. ENDIF
  143.  
  144.  
  145. for those who don't know: what is hashing?
  146. ------------------------------------------
  147. Assume the task of having to store identifiers like the ones used
  148. for variables in E, and later finding them again (this could be any
  149. kind of data, but for now just strings). We could put all these strings
  150. in a linked list, and when a new identifier arrives, simply walk down
  151. the list and see if it's there. While this may seem a nice and easy
  152. way of doing it, this becomes unacceptably slow when storing, say,
  153. 2000 identifiers: we would, on average, perform 1000 StrCmp()s just
  154. to find one identifier!
  155.  
  156. then comes hashing, which is a simple and fast technique to dramatically
  157. reduce search times:
  158.  
  159. take a table of n entries (say, n=256), and take a function which for
  160. every ident can compute a number 0..n-1 (this is called the hashvalue,
  161. and such a function might be: add all ascii values MOD n). when you
  162. now put the idents in n linked list hanging from the n entries in the
  163. table, you only have to compute the hashvalue to theorethically wipe
  164. out 255 of each 256 possibilities. searchtime for our example becomes
  165. 2000/256/2 => 4 StrCmp, without any costly computations.
  166. and imagine what happens if you take a larger n, say 4096, then for most
  167. compilations, you reduce to 1 StrCmp (!).
  168.  
  169. This is an ideal situation, since strangely enough, in reality lot's of
  170. strings end up in the same entry. To make a good distribution of strings
  171. over entries, this module uses several techniques, among them a better
  172. hashing function, primes for n, and others. While in reality you may
  173. end up doing 8 StrCmp()s instead of 4 as in the ideal case, this is
  174. still a huge improvement over the 1000 we started with.
  175.  
  176.