Posted By

pckujawa on 02/26/07


Tagged

hash hashTable hashFunction


Versions (?)

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.

  1. A hash table is an associative abstract data type. Google it if you're curious.
  2.  
  3.  
  4. 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).
  5.  
  6. Example (pseudocodish):
  7. key = "and"
  8. unsigned int n = 0
  9. n = (0 * 8) + 97 = 97 // ASCII value of 'a' is 97
  10. n = (1 * 8) + 110 = 886 // ASCII value of 'n' is 110
  11. n = (2 * 8) + 100 = 7188 // 'd' is 100
  12.  
  13. Example (C++):
  14. class hFstring
  15. {
  16. public:
  17. unsigned int operator() (const string& item) const
  18. {
  19. unsigned int prime = 2049982463;
  20. int n = 0, i;
  21. for (i = 0; i < item.length(); i++) {
  22. n = n*8 + item[i];
  23. }
  24. return (n > 0) ? (n % prime) : (-n % prime); // tertiary operator to account for possible overflow creating a negative number
  25. }
  26. }
  27.  
  28. main
  29. {
  30. hFstring h;
  31. h("and"); // = 7188
  32. }
  33.  
  34. -- This function taken from Ford, William and Topp, William; Data Structures with C++ Using STL, 2ed. 2002 Prentice Hall; p658

Report this snippet  

You need to login to post a comment.