Hash Table: adding and finding functions 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 &gt;= 4)
    {
        unsigned int k = *(unsigned int *) data;

        k *= m; 
        k ^= k &gt;&gt; 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] &lt;&lt; 16;
        case 2: hashValue ^= data[1] &lt;&lt; 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 &gt;&gt; 13;
    hashValue *= m;
    hashValue ^= hashValue &gt;&gt; 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-&gt;element.date = key;
   addition-&gt;element.holiday = holiday;

   // Add holiday to Hash Table
   if (hashTable[murmurHash(key, strlen(key))] == NULL)
   {    
       addition-&gt;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-&gt;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))]-&gt;element.holiday);
}

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

   getchar();
}
For one thing, this:

   // Add holiday to Hash Table
   if (hashTable[murmurHash(key, strlen(key))] == NULL)
   {    
       addition-&gt;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-&gt;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-&gt;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-&gt;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&lt;&gt; template, and it is a good design to emulate.

Best of luck.