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...

based on the FNV algorithm, what causes the hash value that is returned to keep changing. I thought of using the returned value then mod size_1but the unstable hash function prevents this...

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] = {};

I tried:

Code:

auto int bucket= fnv_hash( &nam_1, nam_1.size() );

b/c

Code:

auto int bucket= fnv_hash( nam_1.c_str(), nam_1.size() );

doesn't compile since first argument expects a generic ptr BUT the former statement still outputs a very large value...

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() );

This is the errors compiler shows:
hash_tables.cpp:287: error: ISO C++ forbids declaration of 'bucket' with no type
hash_tables.cpp:287: error: invalid conversion from 'const void*' to 'void*'
hash_tables.cpp:287: error: initializing argument 1 of 'unsigned int fnv_hash(void*, int)'

BTW: line 287 is:

Code:

auto bucket= fnv_hash( nam_1.c_str(), nam_1.size() );

My compiler version:
Thread model: win32
gcc version 4.4.1 (TDM-2 mingw32)

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.

Now it compiles, but it still outputs a large value like 205991382. I did manually use standard c++0x so: g++ -std=c++0x -o hash_tables hash_tables.cpp.

The parameters to use are corrrect according to the official site @ http://www.isthe.com/chongo/tech/comp/fnv/ ... I'll look around for other string hash functions and try to resolve this...

Btw, have you tried to implement the code on your end?

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?

You're right, I just reduce the large value from the FNV hash with mod size and now the large value doesn't keep changing (that was my problem b/c of the garbage bits which I'll look into).

Btw, my compiler it must be:

Code:

auto int bucket = fnv_hash(nam_1.c_str(), nam_1.size() );

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.

I added the param: std=c++0x and now I can do w/o the int, and the only reason I am compressing it w/ mod size is b/c my phonebook_1 hashtable is size 10. I understand collision is inevitable and that perfect hashing is only acheivable as long as you know from the get-go the size of the table and all the keys so that you can tinker like a mad scientist (black art) to figure out how to distribute all the keys w/o collisions. But I'm just building a simple open addressing hash table w/ linear probing method for practice.

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

Originally Posted by Elysia

Don't mod the hash value unless you want collisions.

The implication here is that hash algorithms don't produce collisions alone. They do.