home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / C / HASH.ZIP / HASH.DOC < prev   
Encoding:
Text File  |  1988-10-07  |  8.5 KB  |  196 lines
  1.  
  2.    This text is from an article and program from The C Gazette, March 1988,
  3. Volume 2, No.4. Both were written by Howard Lowndes.
  4. ---------------------------------------------------------------------------
  5.  
  6.                      USING HASH TABLES
  7.  
  8.    Hashing and hash tables need not be mysterious tools used only by the pro-
  9. fessional programmer. This article will discuss the construction and use of 
  10. two different types of hash tables that share common algorithms. Hash tables 
  11. are useful when an unknown number of data items needs to be stored and then 
  12. repeatedly accessed. For example, compiler symbol tables are almost always 
  13. implemented as hash tables.
  14.    Hashing begins with the concept of a hash table, which is simply a regular
  15. in-memory table. However, entries are made into the table on the basis of a 
  16. hashing function rather than in the more traditional sequential manner. A good 
  17. hashing function attempts to analyze a table entry and find a way of assigning 
  18. it a unique slot in the table. The algorithm must generate the same hashing 
  19. key when applied to the same data, so that an item inserted into the hash 
  20. table can subsequently be located. The function must be fast and must generate 
  21. a reasonably good distribution of elements across the table, so that entries 
  22. are made fairly evenly across the table.
  23.    One simple method of hashing adds the ASCII values of the characters in
  24. the data item and divides the sum by the number of slots in the table. In a 
  25. string n of length s for insertion into a table of t slots, this hashing 
  26. function, h(n), is:
  27.  
  28. Figure 1
  29. h(n) = (  sum s[n-1]  mod  t(1->n))
  30.  
  31. In C:
  32.  
  33. Figure 2
  34. int hash (string, slots)
  35. char *s;
  36. int slots;
  37. {
  38.    int i, key;
  39.    for (i = 0, key = 0; s[i]; i++)
  40.       key += s[i];
  41.    return (key % slots);
  42. }
  43.  
  44.    This function will work acceptably well as long as there are few strings
  45. with the same series of letters. For example, lora and oral would generate the 
  46. same hashing key. The hashing of different data to the same key is termed a 
  47. collision. It is clear from the preceding example that knowledge of the data 
  48. to be hashed is required to design a function that will minimize collisions.
  49.    Equally important is the construction of the hash table: it should be
  50. large (with many extra slots) and should have a prime number of slots. The 
  51. latter requirement permits a greater scattering of hash values [Knuth, 1973] 
  52. when the modulo function is applied.
  53.    Further examples of hash functions can be analyzed, but without knowing the 
  54. context in which they will be used, assesment of their effectiveness is 
  55. difficult. Suffice it to say the algorithm must be fast and create a wide 
  56. scattering of values. Empirical methods are best in the final selection of the 
  57. hashing function. 
  58.    Once a key has been computed, the problem of storing the data arises. In
  59. the accompanying code, two different storage techniques have been implemented: 
  60. a simple closed hash table with a fixed number of slots and a more complex 
  61. open hash table, where each slot represents the head of a linked list.
  62.    In the fixed-size hash table, an array of pointers to data items is allo-
  63. cated. If the FIXED model is selected in the accompanying code, the data item 
  64. is struct entry. This structure contains only a pointer to a string although 
  65. other data could, of course, be added. The hash table is then defined as an 
  66. array of pointers to structures of type entry. To look up or store data in the 
  67. array one first computes the hash value of the data and then reduces it modulo 
  68. table size.
  69.    Suppose you allocate a table with three slots choosing the hash function
  70. key = strlen(s);  Initially the table looks like Figure III:
  71.  
  72. (Figure III)
  73.  
  74. key = 0: [empty]
  75. key = 1: [empty]
  76. key = 2: [empty]
  77.  
  78. Now add the string "ab" to the table. Its key is 2, so the result is Figure 
  79. IV:
  80.  
  81. (Figure IV)
  82.  
  83. key = 0: [empty]
  84. key = 1: [empty]
  85. key = 2: ["ab"]
  86.  
  87.    Now add the string "abcd". Its key is 4, but reduce this modulo 3 to get
  88. a final key of 1 (i.e., key computed as key_final = key_initial % 
  89. table_size";). (The modulo operator % computes the remainder after the integer 
  90. division of key_initial by table_size). Thus the table becomes Figure V:
  91.  
  92. (Figure V)
  93.  
  94. key = 0: [empty]
  95. key = 1: ["abcd"]
  96. key = 2: ["ab"]
  97.  
  98.    Now add the string "z". A problem appears immediately. The key for "z" is
  99. 1 and colides with the key for "abcd". All implementations of hash tables must 
  100. deal with collision resolution. An easy solution is simply to start a forward 
  101. search until an empty slot is found. Slot 2 is full; a loop back to the top 
  102. reveals that slot 0 is free. Thus the table becomes Figure VI:
  103.  
  104. (Figure VI)
  105.  
  106. key = 0: ["z"]
  107. key = 1: ["abcd"]
  108. key = 2: ["ab"]
  109.  
  110.    This is a fairly typical resolution scheme for closed (i.e. fixed-size 
  111. hash) tables. When searching the table, if the element at the hashed location 
  112. is not the desired element, one need only read sequentially through the table 
  113. until 1) the key is found ; 2) an empty slot is found; or 3) the emtire table 
  114. has been read. The last two cases indicate an unsuccessful search. This 
  115. technique has two drawbacks: it does not permit deletion of table entries 
  116. (since the vacant slots cannot easily be disambiguated from unused slots in 
  117. the sequential search through the table) and searching the table is costly if 
  118. the table is close to full.
  119.    For some applications, a fixed capacity table might work well but for
  120. occasions when an essentially unlimited table is needed, a slightly different 
  121. technique can be used: the open hashing table. This is done by converting each 
  122. slot from a pointer to a single data item to a pointer to a list of data 
  123. items. As Figure VII shows, the data structure goes from
  124.  
  125. (Figure VII)
  126.  
  127. struct entry {
  128.    char *data;
  129. };
  130.  
  131. to
  132.  
  133. struct entry {
  134.    char *data;
  135.    struct entry *next;
  136. };
  137.  
  138.    With this new model in mind, the original example can be reworked. First
  139. insert the string "ab" (which has a key of 2) as in Figure VIII:
  140.  
  141. Figure VIII:
  142.  
  143. key = 0: [empty]
  144. key = 1: [empty]
  145. key = 2: ["ab"]
  146.  
  147.    Next the string "abcd" (which has a key of 1) is added as in Figure IX:
  148.  
  149. (Figure IX)
  150.  
  151. key = 0: [empty]
  152. key = 1: ["abcd"]
  153. key = 2: ["ab"]
  154.  
  155.    Now insert "z" again. It's key is the same as the "abcd" key, but instead
  156. of searching for an empty slot, they can both be put into the same slot as in 
  157. Figure X:
  158.  
  159. (Figure X)
  160.  
  161. key = 0: [empty]
  162. key = 1: ["z"] -> ["abcd"]
  163. key = 2: ["ab"]
  164.  
  165.    Thus, it should be clear that this type of table has no fixed limit to
  166. it's capacity. However, there are some potential drawbacks. First, the code 
  167. required to handle the linked lists is slightly more complex than that needed 
  168. to search a simple array and thus might take longer to execute. Second, the 
  169. linked list associated with each slot could become quite a jumble unless even 
  170. more code was added to keep it in some sort of order. The search of a slot's 
  171. list of entries is effectively a random search unless, for example, the 
  172. entries are kept in alphabetical order. Even then, the search for an entry 
  173. beginning with "z" is often slower than for an entry starting with "a". An 
  174. alternative approach (and the one that is implemented in the accompanying 
  175. code) is to let the list become a jumble but always to move the most recently 
  176. used item to the top of the list. This might make sense for a compiler, as 
  177. variable names do tend to be used in clusters. For example, in parsing the 
  178. code a[i] = b[i]; the variable i is used twice.
  179.    How efficient is all of this? The efficiency of the program depends on a
  180. variety of factors. A bad hash function (or a set of data that is bad for a 
  181. particular hash function) can certainly slow things. A table that is too small 
  182. is also a problem. If 50 items are stored in a 51-slot fixed-size table, there 
  183. are bound to be more collisions than if the same data were stored in a 100-
  184. slot table. A similar consideration is true for the linked list model. Even 
  185. though collisions are not a problem, if the data is distributed throughout a 
  186. larger table, the linked lists associated with each slot should, in general, 
  187. be shorter. The typical measure of efficiency is to count the number of 
  188. incorrect items to be traversed before finding the target item. The 
  189. accompanying code has a sample driver that also includes a search counter. It 
  190. is interesting to try different ranges of data and table sizes while keeping 
  191. an eye on the search counter.
  192.  
  193.                         END OF TEXT
  194. -----------------------------------------------------------------------------
  195.  
  196.