Thread: How to use string hash function

For some reason, it's hashing to a very large number like
1241200051for an index (i.e. bucket). I'm building a simple hash table via open addressing w/ linear probing and it's phonebooks where the keys are string names, with 7-digit phone nums as values.

here is the tested-and-tried string hash function FNV I found @:
Eternally Confuzzled - The Art of Hashing

Code:

unsigned fnv_hash ( void *key, int len )//Q: how do I use generic ptr key?
{
   unsigned char* p = (unsigned char*)key;
   unsigned h = 2166136261U;
   int i;
 
   for ( i = 0; i < len; i++ )
     h = ( h * 16777619 ) ^ p[i];
 
   return h;
}

Code:

int main()
{
   int phonebook_1[10] = {0,0,0,0,0,0,0,0,0,0};//always initialize size since specific compilers say its ok so don't get comfy w/ bad practices
    
   size_t size_1 = 10;
    
   string nam_1 = "Cooke";
   void* p_to_nam_1 = &nam_1;
    
   unsigned int bucket= fnv_hash( p_to_nam_1, size_1 );
    
   cout << bucket << endl;
   return 0;
}

EDIT: actually I found the official website on how to set the params and values @ FNV Hash, so I'lll take a look first before posting further...

You're telling it to hash 10 characters but the string is only 5 bytes long (well 6 including the nul-terminator, but you don't need to hash that).

So you're hashing whatever random garbage comes after that, as well.

Worse still, you're hashing the std::string object itself. But a std::string is itself not a char array. It holds one internally through pointers, but it is not itself actually just a char array. You need to call .c_str() to get at that.

You should be doing,
auto bucket = fnv_hash( nam_1.c_str(), nam_1.size() );
Also,
This
int phonebook_1[10] = {0,0,0,0,0,0,0,0,0,0};
is the same as
int phonebook_1[10] = {};

Any pointer can be converted to void* and back, so the second should compile. Otherwise post the error.
You've already been told not to use the former since it's wrong, wrong, wrong and utterly wrong in all sorts of ways. You should not hash C++ objects. The internals of an object should not be hashed. Furthermore, the size of the string object is not num_1.size(), so the hash function will even read bytes which do not exist!

Oh, and remove the "int".
It should be
auto bucket = fnv_hash( nam_1.c_str(), nam_1.size() );

Well, the hashing function is broken.
Will attempt to fix:

Code:

unsigned int fnv_hash(const void* key, int len)
{
   const unsigned char* p = static_cast<const unsigned char*>(key);
   unsigned int h = 2166136261U;
  
   for (int i = 0; i < len; i++)
     h = (h * 16777619) ^ p[i];
  
   return h;
}

As for the first compile error, be sure to use C++11 (or C++0x). Add -std=c++0x if you are compiling manually or find the option to enable it in the compiler options of your IDE.

Why do you think it shouldn't output a large value? AFAIK, it's pretty normal with hash functions.
Also, what is wrong with large values?

Don't mod the hash value unless you want collisions. In a hash table, it is inevitable that you must do so, but remember the consequences: you will get collisions.
>>auto int bucket = fnv_hash(nam_1.c_str(), nam_1.size() );
That's wrong. Remove the int. If you compile it properly with the C++11 standard, it will work. Otherwise the auto keyword is useless.

Alright, that is fine. That is typically how hash tables are implemented.