Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does a hash function return a size_t, and how is it used?

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;
}
  1. Why does this return a size_t?
  2. How would one use this to write a store() function which places a string in a hash table?
  3. How can this be adapted for an array of characters?
  4. In regards to #3, would it be appropriate to replace the 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.

like image 886
Adam S Avatar asked Oct 11 '22 17:10

Adam S


2 Answers

  1. It returns size_t because that's the native integer (also fastest). Why choose anything else?

  2. "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".)

  3. Isn't it already adapted for an array?

  4. If it's a null-terminated string, why not?

like image 143
user541686 Avatar answered Oct 13 '22 09:10

user541686


  1. It doesn't have to be size_t, but it should probably be an unsigned integer type so mod is well-defined.

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

  3. It appears already to be so adapted.

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

like image 32
luser droog Avatar answered Oct 13 '22 09:10

luser droog