5
\$\begingroup\$

I made this function to teach myself about hash tables. Any ideas? I commented out free(addition) because it was giving me a compiler error, but I need to figure out how to deallocate the memory.

#define hashSize 1000

typedef struct hashElem{
    char* date;
    char* holiday;
}hashElem;

typedef struct hash{
    struct hashElem element;
    struct hash* next;
}hash;

hash* hashTable[hashSize];

// Hash function
size_t murmurHash(const void *keyPtr, size_t keySize)
{
     /*  DESCRIPTION:    Very fast string hashing algorithm with excelleng distribution and 
     *                  collision resistance. This source code has been released into the public
     *                  domain.
     *
     *  NOTES:          http://murmurhash.googlepages.com
     *
     *  RETURNS:        Hashtable index for the key
     *
     */

    /* 'm' and 'r' are mixing constants generated offline.         */
    /* They're not really 'magic', they just happen to work well.  */

    const unsigned int m = 0x5bd1e995;
    const int r = 24;

    size_t hashValue = 0;

    /* Mix 4 bytes at a time into the hash */

    const unsigned char * data = (const unsigned char *)keyPtr;

    while(keySize >= 4)
    {
        unsigned int k = *(unsigned int *) data;

        k *= m; 
        k ^= k >> r; 
        k *= m; 

        hashValue *= m; 
        hashValue ^= k;

        data += 4;
        keySize -= 4;
    }

    /* Handle the last few bytes of the input array */

    switch(keySize)
    {
        case 3: hashValue ^= data[2] << 16;
        case 2: hashValue ^= data[1] << 8;
        case 1: hashValue ^= data[0];
                hashValue *= m;
    }; 

    /* Do a few final mixes of the hash to ensure the last few  */
    /* bytes are well-incorporated.                             */

    hashValue ^= hashValue >> 13;
    hashValue *= m;
    hashValue ^= hashValue >> 15;

    return (hashValue % hashSize);
}

// strlen: return length of string
int strlen(char *s)
{
    char* p = s;

    while (*p != '\0')
        ++p;
    return p - s;
}

// Add Holiday into hash table
void addHoliday(char* date, char* holiday)
{
   char* key;
   int keyLen;
   size_t keyHash;
   hash* addition = malloc(sizeof(*addition));

   key = date;
   addition->element.date = key;
   addition->element.holiday = holiday;

   // Add holiday to Hash Table
   if (hashTable[murmurHash(key, strlen(key))] == NULL)
   {    
       addition->next = NULL;
       hashTable[murmurHash(key, strlen(key))] = addition; 
   }
   else  //If there is already an element at the index, add current holiday to beginning of list
   {
       addition->next = hashTable[murmurHash(key, strlen(key))];
       hashTable[murmurHash(key, strlen(key))] = addition;
   }

   //free(addition);
}

// If a date is entered, retrieve holiday from hash function index
char* getHoliday(char* date)
{
    return(hashTable[murmurHash(date, strlen(date))]->element.holiday);
}

void main(void)
{
   addHoliday("01/01/13", "New Years Day");
   printf("%s\n", getHoliday("01/01/13"));

   getchar();
}
\$\endgroup\$
6
\$\begingroup\$

For one thing, this:

   // Add holiday to Hash Table
   if (hashTable[murmurHash(key, strlen(key))] == NULL)
   {    
       addition->next = NULL;
       hashTable[murmurHash(key, strlen(key))] = addition; 
   }
   else  //If there is already an element at the index, add current holiday to beginning of list
   {
       addition->next = hashTable[murmurHash(key, strlen(key))];
       hashTable[murmurHash(key, strlen(key))] = addition;
   }

can simply be this:

   // Add holiday to Hash Table
   size_t idx = = murmurHash(key, strlen(key));
   addition->next = hashTable[idx];
   hashTable[idx] = addition;

Which cuts at least one invoke of the hash function, and in the process a similar number of strlen invokes. There is little sense is "checking" for a NULL in the hash table slot, because that is precisely what you want the next pointer of your new node to be anyway.

Not entirely clear either is whether you intended on your keys being unique. Both code snippets above (yours and mine) do not enforce unique keys. It is worth a thought to determine whether that feature is needed or not.

And (not really) finally, try and make a habit of creating hash functions that are independent of the hash table size. Though that may sound odd, it makes sense from the perspective of reuse. A hash function ideally returns a "value". That value is then massaged (usually via a modulo with the hash table size) to drive the final key into a slot within the table constraints. But that operation is separate from the hash function itself, which should be restricted only by the domain of the return type. In other words, this:

size_t murmurHash(const void *key, size_t len)

should simply return a value between 0 and the maximum value of a size_t on the platform. Period. No table size should be involved in the has function itself. Just chew on data and return some size_t. The caller of the function (the inserter, the lookup, etc), then takes this value and restricts it down to the table size (usually via a modulo of some kind). This makes the invocation look something like this:

   // Add holiday to Hash Table
   size_t idx = = murmurHash(key, strlen(key)) % hashSize;
   addition->next = hashTable[idx];
   hashTable[idx] = addition;

Though it may seem a little odd at first, it makes your hash functions more robust. They are not restricted by some table size. The user of the hash function does that step; not the function itself. This is the approach used by the standard C++ library std::hash<> template, and it is a good design to emulate.

Best of luck.

\$\endgroup\$
5
\$\begingroup\$

I agree with WhozCraig; it is not necessary to run the hash multiple times. I would add that freeing the pointer (addition) would result in loss of the data you just added. Your array hashTable is an array of pointers - it doesn't include storage for the hash elements themselves. Thus, you can't free any hash elements until you remove them from the table or are done with the table itself.

Tearing down the table will have to go something like this:

for (int i = 0 ; i < hashSize ; i++) {
    hash* ptrToFree = hashTable[i];
    while (ptrToFree != NULL) {
        hash* next = ptrToFree->next;
        mfree(ptrToFree);
        ptrToFree = next;
    }
}

If you don't like iterating over all of your pointers (it looks time-consuming, but you're probably on the way out of your process, right?) you can keep a static list of all elements, then iterate through that.

typedef struct _HashStorage {
    struct hash element;
    struct _HashStorage * more;
} HashStorage;

HashStorage* storage = NULL;

hash* newHash() {
    HashStorage* oldTop = storage;
    storage = malloc(sizeof(HashStorage));
    storage->more = oldTop;
    return (hash*) storage;
}

void dispose() {
    HashStorage* iterator = storage;
    while (iterator != NULL) {
        HashStorage* more = iterator->more;
        mfree(iterator);
        iterator = more;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.