home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / lang / c / 18329 < prev    next >
Encoding:
Text File  |  1992-12-14  |  3.4 KB  |  170 lines
  1. Newsgroups: comp.lang.c
  2. Path: sparky!uunet!utcsri!torn!newshub.ccs.yorku.ca!newshub.ccs.yorku.ca!oz
  3. From: oz@ursa.sis.yorku.ca (Ozan Yigit)
  4. Subject: Re: Need good hashing functions
  5. In-Reply-To: sjs@netcom.com's message of Wed, 9 Dec 1992 21: 30:41 GMT
  6. Message-ID: <OZ.92Dec14124433@ursa.sis.yorku.ca>
  7. Sender: news@newshub.ccs.yorku.ca (USENET News System)
  8. Organization: York U. Student Information Systems Project
  9. References: <1992Dec9.213041.16259@netcom.com>
  10. Date: Mon, 14 Dec 1992 17:44:33 GMT
  11. Lines: 157
  12.  
  13. Stephen Schow writes:
  14.  
  15.    I am looking for hashing functions for a school project.  If anyone has any
  16.    ideas and/or book suggestions that can help me find some good hashing
  17.    functions to use in my project, I would appreciate it.
  18.  
  19.    Note - We are hashing single english words.
  20.  
  21. The following is required reading:
  22.  
  23.     B. J. McKenzie, R. Harries, T. Bell.
  24.     Selecting a Hashing Algorithm
  25.     Software - Practice and Experience,
  26.     20(2):209-224, Feb 1990.
  27.  
  28. Here are the functions used in that paper, from a posting by
  29. raghu@norway.fishkill.ibm.com (Raghu Hudli) to comp.programming,
  30. slightly re-formatted by me.
  31.  
  32. enjoy...    oz
  33. ---
  34. With diligence, it is possible to | electric: oz@sis.yorku.ca
  35. make anything run slowly. -T.Duff | ph:[416] 736 2100 x 33976
  36.  
  37. --- cut here ---
  38.  
  39. /*
  40.  * return the least significant n bits of h
  41.  */
  42. static unsigned int
  43. BITS(unsigned int h, unsigned int n)
  44. {
  45.     register int bits = 0;
  46.     while (n--) {
  47.         bits = bits << 1;
  48.         bits += 1;
  49.     }
  50.     return (bits & h);
  51. }
  52.  
  53. /*
  54.  * ETH Modula-2 Cross Compiler
  55.  * Recommended table length = 1699
  56.  */
  57. unsigned int
  58. hasheth(const char *key)
  59. {
  60.     int tableLength = 1699;
  61.     register unsigned int h = 0;
  62.     register const char *c = key;
  63.  
  64.     while (*c)
  65.         h = BITS(*c++, 8) * (h % 257) + 1;
  66.     return (h % tableLength);
  67. }
  68.  
  69. /*
  70.  * GNU C preprocessor
  71.  * Recomended table length=1403
  72.  */
  73. unsigned int
  74. hashgnuccpp(const char *key)
  75. {
  76.     int tableLength = 1403;
  77.     register unsigned int h = 0;
  78.     register const char *c = key;
  79.  
  80.     while (*c)
  81.         h = 4 * h + *c++;
  82.     return (BITS(h, 31) % tableLength);
  83. }
  84.  
  85. /*
  86.  * GNU C compiler front end
  87.  * Recomended table length=1008
  88.  */
  89. unsigned int
  90. hashgnucc1(const char *key)
  91. {
  92.     int tableLength = 1008;
  93.     register unsigned int h = 0;
  94.     register const char *c = key;
  95.  
  96.     while (*c)
  97.         h = 613 * h + *c++;
  98.     return (BITS(h, 30) % tableLength);
  99. }
  100.  
  101. /*
  102.  * Portable C Compiler
  103.  * Recomended table length=1013
  104.  */
  105. unsigned int
  106. hashpcc(const char *key)
  107. {
  108.  
  109.     int tableLength = 1013;
  110.     register int h = 0;
  111.     register const char *c = key;
  112.  
  113.     while (*c)
  114.         h = 2 * h + *c++;
  115.     return (((unsigned int) BITS(h, 15)) % tableLength);
  116. }
  117.  
  118. /*
  119.  * Unix 4.3BSD C preprocessor based
  120.  * Recomended table length=2000
  121.  */
  122. unsigned int
  123. hashcpp(const char *key)
  124. {
  125.     int tableLength = 2000;
  126.     register int h = 0;
  127.     register const char *c = key;
  128.     register unsigned int index;
  129.  
  130.     while (*c)
  131.         h = 2 * h + *c++;
  132.  
  133.     if ((index = h % 2000) >= 0)
  134.         return (index % tableLength);
  135.     else
  136.         return (index % tableLength + 2000);
  137. }
  138.  
  139. /*
  140.  * AT&T C++ compiler based.
  141.  * Recomended table length=257
  142.  */
  143. unsigned int
  144. hashcplusplus(const char *key)
  145. {
  146.     int tableLength = 257;
  147.     register unsigned int h = 0;
  148.     register const char *c = key;
  149.  
  150.     while (*c)
  151.         h = 2 * h + *c++;
  152.     return (h % tableLength);
  153. }
  154.  
  155. /*
  156.  * ICON translator
  157.  * Recommended table length = 257
  158.  */
  159. unsigned int
  160. hashicon(const char *key)
  161. {
  162.     int tableLength = 257;
  163.     register unsigned int h = 0;
  164.     register const char *c = key;
  165.  
  166.     while (*c)
  167.         h += BITS(*c++, 8);
  168.     return (h % tableLength);
  169. }
  170.