Posted By

pckujawa on 02/26/07

Hash functions

/ Published in: Other

This is just a collection of hash functions and information that I've gleaned from books, the web, other programmers, etc... Feel free to add your own.

`A hash table is an associative abstract data type. Google it if you're curious.  If the key is a string, one algorithm is to start with n = 0, multiply 8 by the index of the next character in the string, and add the ASCII value of the new character. The result could be negative, due to overflow, so check and return the positive value, after dividing by a large prime number (to provide further randomization of integer values; you could use 2 049 982 463). Example (pseudocodish):key = "and"unsigned int n = 0n = (0 * 8) + 97 = 97    // ASCII value of 'a' is 97n = (1 * 8) + 110 = 886  // ASCII value of 'n' is 110n = (2 * 8) + 100 = 7188 //                'd' is 100 Example (C++):class hFstring{  public:    unsigned int operator() (const string& item) const    {      unsigned int prime = 2049982463;      int n = 0, i;      for (i = 0; i < item.length(); i++) {        n = n*8 + item[i];      }      return (n > 0) ? (n % prime) : (-n % prime); // tertiary operator to account for possible overflow creating a negative number    }} main{  hFstring h;  h("and"); // = 7188} -- This function taken from Ford, William and Topp, William; Data Structures with C++ Using STL, 2ed. 2002 Prentice Hall; p658`