I understand the mathematical basis for hash tables. I have a hash function (that I found somewhere) below:
/* Fowler / Noll / Vo (FNV) Hash */
static const size_t InitialFNV = 2166136261U;
static const size_t FNVMultiple = 16777619;
size_t myhash(const string &s, int length)
{
size_t hash = InitialFNV;
for(size_t i = 0; i < length; i++)
{
//XOR the lower 8 bits
hash = hash ^ (s[i]);
//Multiply by the multiple
hash = hash * FNVMultiple;
}
return hash;
}
size_t
?store()
function which places a
string in a hash table?for
loop with a while
loop that
terminates at the '\0'
character?FYI, I am studying up for a second job interview, and that's why I'm asking.
It returns size_t
because that's the native integer (also fastest). Why choose anything else?
"The table"? Which table? If you mean a hashtable, then you can use the return value to choose a random bucket to put the object in. (Hint: Think "remainder".)
Isn't it already adapted for an array?
If it's a null-terminated string, why not?
It doesn't have to be size_t
, but it should probably be an unsigned integer type so mod is well-defined.
The usual way is to use the hash function to transform the 'key' data into an array index. So you mod by the size of the array to get an integer from 0 to SIZE-1 that you can use as an index. You'll also need a "collision resolution strategy" because unless the hash yields perfect results, some pairs of keys which are different will hash to the same value.
It appears already to be so adapted.
If the string ends in NUL, you can search for the null. But the function as written is passed a length as argument. Simplest to leave the working function alone, and call it with the result of strlen().
Ps. the const string &s
means C++, not C. This may be important when compiling.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With