Hash function for a string

First, it usually does not matter that much in practice. Most hash functions are “good enough”.

But if you really care, you should know that it is a research subject by itself. There are thousand of papers about that. You can still get a PhD today by studying & designing hashing algorithms.

Your second hash function might be slightly better, because it probably should separate the string "ab" from the string "ba". On the other hand, it is probably less quick than the first hash function. It may, or may not, be relevant for your application.

I’ll guess that hash functions used for genome strings are quite different than those used to hash family names in telephone databases. Perhaps even some string hash functions are better suited for German, than for English or French words.

Many software libraries give you good enough hash functions, e.g. Qt has qhash, and C++11 has std::hash in <functional>, Glib has several hash functions in C, and POCO has some hash function.

I quite often have hashing functions involving primes (see Bézout’s identity) and xor, like e.g.

#define A 54059 /* a prime */
#define B 76963 /* another prime */
#define C 86969 /* yet another prime */
#define FIRSTH 37 /* also prime */
unsigned hash_str(const char* s)
{
   unsigned h = FIRSTH;
   while (*s) {
     h = (h * A) ^ (s[0] * B);
     s++;
   }
   return h; // or return h % C;
}

But I don’t claim to be an hash expert. Of course, the values of A, B, C, FIRSTH should preferably be primes, but you could have chosen other prime numbers.

Look at some MD5 implementation to get a feeling of what hash functions can be.

Most good books on algorithmics have at least a whole chapter dedicated to hashing. Start with wikipages on hash function & hash table.

Related Posts:

  1. Hash function for a string
  2. Why the switch statement cannot be applied on strings?
  3. Easiest way to convert int to string in C++
  4. std::string to char*
  5. C++ — expected primary-expression before ‘ ‘
  6. Conversion from string to char – c++
  7. What is `CString`?
  8. How do I include the string header?
  9. Differences between C++ string == and compare()?
  10. How to convert a char array to a string?
  11. How do I convert a double into a string in C++?
  12. Split a string using C++11
  13. How do I iterate over the words of a string?
  14. How to convert an instance of std::string to lower case
  15. Check if a string contains a string in C++
  16. How do I iterate over the words of a string?
  17. Returning an empty string : efficient way in c++
  18. Replace part of a string with another string
  19. C++ string to double conversion
  20. What is use of c_str function In c++
  21. How to reverse an std::string? [duplicate]
  22. C++ Parsing input string to variables
  23. std::string to char*
  24. How do I tokenize a string in C++?
  25. Why use string::iterator rather than index?
  26. Why am I getting string does not name a type Error?
  27. C++ deprecated conversion from string constant to ‘char*’
  28. identifier “string” undefined?
  29. Press Enter to Continue
  30. Converting a vector to string
  31. Parsing a comma-delimited std::string
  32. How can I convert const char* to string and then back to char*?
  33. std::string formatting like sprintf
  34. Sorting Characters Of A C++ String
  35. basic_string::_M_construct null not valid after constructing subvector of strings
  36. How to copy a string of std::string type in C++?
  37. How to return a string from a C++ function?
  38. std::out_of_range error?
  39. What is the difference between isdigit() and isnumber()?
  40. Convert char* to string C++
  41. printf with std::string?
  42. Convert a String In C++ To Upper Case
  43. Right way to split an std::string into a vector
  44. Read whole ASCII file into C++ std::string
  45. C++: std does not have member “string”
  46. Right way to split an std::string into a vector
  47. string subscript out of range error
  48. C++ String Variable Declaration
  49. Returning an empty string : efficient way in c++
  50. Split a string into an array in C++
  51. splitting a string into an array in C++ without using vector
  52. Remove spaces from std::string in C++
  53. Remove spaces from std::string in C++
  54. c++ convert string to hex
  55. How can I iterate through a string and also know the index (current position)?
  56. c++ parse int from string [duplicate]
  57. C++ strings and pointers
  58. How to Convert a C++ String to Uppercase
  59. std::wstring VS std::string
  60. C++ Simple hangman game
  61. std::cin input with spaces?
  62. Remove First and Last Character C++
  63. C++ Remove punctuation from String
  64. C++ string to enum
  65. C++ Convert string (or char*) to wstring (or wchar_t*)
  66. C++ – Assigning null to a std::string
  67. How to alphabetically sort strings?
  68. Reading string by char till end of line C/C++
  69. How do I check if a C++ std::string starts with a certain string, and convert a substring to an int?
  70. Dynamically allocated string array, then change it’s value?
  71. Fastest way to Convert String to Binary?
  72. Why I cannot cout a string?
  73. How to print a string in C++
  74. std::string length() and size() member functions
  75. How to convert QString to int?
  76. Which is faster C++ String length() or size()?
  77. How do I create a random alpha-numeric string in C++?
  78. Is string::compare reliable to determine alphabetical order?
  79. Trying to use int in getline
  80. error: switch quantity not an integer
  81. Reading a string from file c++
  82. How to change string into QString?
  83. Remove last character from C++ string
  84. Function stoi not declared
  85. Converting String to Cstring in C++
  86. c++ sizeof( string )
  87. How to do std::string indexof in C++ that returns index of matching string?
  88. variable or field declared void
  89. Function stoi not declared
  90. How exactly do lookup tables work and how to implement them?
  91. How to get the MD5 hash of a file in C++?
  92. Understanding error “terminate called after throwing an instance of ‘std::length_error’ what(): basic_string::_S_create Aborted (core dumped)”
  93. convert string to size_t
  94. ‘setprecision’ is not a member of ‘std’
  95. enum to string in modern C++11 / C++14 / C++17 and future C++20
  96. Converting bool to text in C++
  97. Why are there two different getline() functions (if indeed there are)?
  98. How to find and replace string?
  99. Declaration is incompatible with type
  100. I’m getting the error “stoi is not a member of std” in myprogramminglab [duplicate]

Leave a Comment