Reference: https://www.cs.yale.edu/homes/aspnes/pinewiki/C(2f)HashTables.html?highlight=%28CategoryAlgorithmNotes%29 idtablehashtable.c is the same as the IDList.c on the reference link and dictionary.c is the same as dict.c

dictionary.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include "dictionary.h"

#define INITIAL_SIZE (1024)
#define GROWTH_FACTOR (2)
#define MAX_LOAD_FACTOR (1)
#define MULTIPLIER (97)

/* dictionary initialization code used in both DictCreate and grow */


Dictionary *internalDictCreate(int size){
    Dictionary *dictionary;
    
    dictionary = malloc(sizeof(*dictionary));

    assert(dictionary != NULL);

    dictionary->size = size;
    dictionary->n = 0;
    dictionary->table = malloc(sizeof(struct element *) * dictionary->size);

    assert(dictionary->table != NULL);

    for (int i = 0; i < dictionary->size; i++)
    {
        dictionary->table[i] = 0;
    }
    
    return dictionary;
}

Dictionary *DictCreate(void){
    return internalDictCreate(INITIAL_SIZE);
}

void DictDestroy(Dictionary *dictionary){

    struct element *element;
    struct element *next_element;

    for (int i = 0; i < dictionary->size; i++)
    {
        for (element = dictionary->table[i]; element != NULL; element = next_element)
        {
            next_element = element->next;

            free(element->key);
            free(element->value);
            free(element);
        }
        
    }
    
    free(dictionary->table);
    free(dictionary);

}

static unsigned long hash_multiplier(const char *s){

    unsigned long hash;
    unsigned const char *us;    //unsigned string

    us = (unsigned const char *)s; // cast the string to unsigned const char *, this ensures that elements of s will be treated as having values >=0
    hash = 0;

    while (*us != '\0')
    {
        hash = hash * MULTIPLIER + *us; 
        us++;
    }
    
    return hash;
}

static void grow(Dictionary *dictionary){
    Dictionary *dictionary_new;          /* new dictionary we will create */
    Dictionary temp_dictionary;          /* temporary structure for brain transplant :D */

    struct element *element;

    dictionary_new = internalDictCreate(dictionary->size * GROWTH_FACTOR);

    for (int i = 0; i < dictionary->size; i++)
    {
        for (element = dictionary->table[i]; element != NULL; element=element->next)
        {
            /* copy all the elements from the existing dictionary to the newly created dictionary */
            DictInsert(dictionary_new, element->key, element->value);
        }
        
    }
    
    /* We will swap the contents of dictionary and dictionary_new and then call DictDestroy on dictionary new */
    temp_dictionary = *dictionary;
    *dictionary = *dictionary_new;
    *dictionary_new = temp_dictionary;

    DictDestroy(dictionary_new);
}

/* insert a new key-value pair into an existing dictionary */
void DictInsert(Dictionary *dictionary, const char *key, const char *value){

    struct element *element;
    unsigned long hash;

    assert(key);
    assert(value);

    element = malloc(sizeof(*element));

    assert(element);

    element->key = strdup(key);
    element->value = strdup(value);

    hash = hash_multiplier(key) % dictionary->size;

    element->next = dictionary->table[hash];    // Assign current element to the next element
    dictionary->table[hash] = element;          // and then assign new element to the current element. This is where the chain collision is handled by the linked list :D

    dictionary->n++;

    /* grow table if there not enough room */
    if (dictionary->n >= (dictionary->size * MAX_LOAD_FACTOR))
    {
        grow(dictionary);
    }
    

}

const char * DictSearch(Dictionary *dictionary, const char *key){

    struct element *element;
    element = dictionary->table[hash_multiplier(key) % dictionary->size];

    while (element != NULL)
    {
       if (!strcmp(element->key,key))
       {
           return element->value;
       }
       
       element = element->next;
    }
    
    return 0;
}

void DictDelete(Dictionary *dictionary, const char *key){

    struct element **element_holder;            /* what to change when element is deleted */
    struct element *element;                    /* element to delete */
    
    element_holder = &dictionary->table[hash_multiplier(key) % dictionary->size];

    while (*element_holder != NULL)
    {
        if (!strcmp((*element_holder)->key,key))
        {
            /* we found it */
            element = *element_holder;
            *element_holder = element->next;

            free(element->key);
            free(element->value);
            free(element);

            return;
        }
        
    }
    

}

int main(int argc, char *argv[])
{
    Dictionary *dictionary;
    char buffer[512];

    dictionary = DictCreate();

    DictInsert(dictionary, "192.168.4.4","Luci Gateway");
    puts(DictSearch(dictionary, "192.168.4.4"));
    DictInsert(dictionary, "192.168.4.4","Chidelu Internet Services");
    puts(DictSearch(dictionary, "192.168.4.4"));
    DictDelete(dictionary,"192.168.4.4");
    puts(DictSearch(dictionary, "192.168.4.4"));
    DictDelete(dictionary,"192.168.4.4");
    assert(DictSearch(dictionary,"192.168.4.4") == 0);
    DictDelete(dictionary,"192.168.4.4");

    for (int i = 0; i < 10000; i++)
    {
        sprintf(buffer,"%d",i);
        DictInsert(dictionary,buffer,buffer);
    }
    
    for (int i = 0; i < 50; i++)
    {
        char ch[4];
        snprintf(ch,sizeof(ch),"%d",i);
        puts(DictSearch(dictionary, ch));
    }


    DictDestroy(dictionary);
    return 0;
}

dictionary.h

/**
 * String to string dictionary using chaining for collision resolution during hashing
*/

typedef struct _dict{
    int size;                       /* size of the pointer table */
    int n;                          /* number of elements stored */
    struct element **table;
} Dictionary;

struct element
{
    struct element *next;
    char *key;
    char *value;
};

/* create a new empty dictionary */
Dictionary *DictCreate(void);

/* destroy  a dictionary */
void DictDestroy(Dictionary *dictionary);

/* insert a new key-value pair into an existing dictionary */
void DictInsert(Dictionary *dictionary, const char *key, const char *value);

/* return the most recently inserterd value associated with a key or return 0 if no matching key is present */
const char *DictSearch(Dictionary *dictionary, const char *key);

/* delete the most recently inserted record with the given key, if there is no such record do nothing */
void DictDelete(Dictionary *dictionary, const char *key);

idtablehashtable.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include "idtablehashtable.h"

/**
 * @brief A low overhead hash table using open addressing. The application is rapidly verifying ID numbers in the range
 * 000000000 to 999999999 by checking them against a list of known IDs. Since the quantity of a valid ID number 
 * must be very large, a goal of the mechanism is to keep the value of extra storage used as small as possible.
 * This implementation uses a tunable overhead parameter.
 * Setting the parameter to a high value makes the lookups fast but requires more space per ID in the list.
 * Setting it to a low value can reduce the storage cost arbitrarily close to 4 bytes per ID, at the cost of increasing search times
 * 
 * 
 * Hash table using open addressing 
*/

/*  overhead parameter that determines both space ans search costs must be strictly greater than 1 */
#define OVERHEAD (1.1)
#define NULL_ID (-1)

IDList *IDListCreate(int n, int unsorted_id_list[]){

    IDList *list;
    int size;
    int i;
    int probe;
    int next;
    size = (int) (n * OVERHEAD + 1);

    list = malloc(sizeof(IDList) + sizeof(int) * (size - 1));
    if(list == NULL)
        return NULL;

    list->size = size;

    // clear the hash table 

    for (i = 0; i < n; i++)
    {
        list->ids[i] = NULL_ID;
    }
    
    // load up the hast tabele
    for ( i = 0; i < n; i++)
    {
        assert(unsorted_id_list[i] >= MIN_ID);
        assert(unsorted_id_list[i] <= MAX_ID);

        /* hashing with open addressing by division, this must be the same pattern as in IDListContains */
        
        /* This is doing the same thing  as insert function in hashtabletest.c, probe is the hashindex, list->size is SIZE macro used in hashcode function
           then probe = (probe + 1) % list->size) is the wrap around expression ++hashIndex; hashIndex = hashIndex % SIZE;
        */
        for (probe = unsorted_id_list[i] % list->size; list->ids[probe] != NULL_ID; probe = (probe + 1) % list->size);
        
        assert(list->ids[probe] == NULL_ID);

        list->ids[probe] = unsorted_id_list[i];
    }
    
    return list;
}

void IDListDestroy(IDList *list){
    free(list);
}

int IDListContains(IDList *list, int id)
{
    int probe;

    /* this must be the same pattern as in IDListCreate */
    for (probe = id % list->size; list->ids[probe] != NULL_ID; probe = (probe + 1) % list->size)
    {
        if (list->ids[probe] == id)
        {
           return 1;
        }
        if (list->ids[probe] != id && probe >= (list->size - 1))
        {
            return 0;
        }
        
    }
    
    return 0;

}

int main(int argc, char * argv[]){
    IDList *list;
    int ids[5] = {1,23,45,62,42};
    
    list = IDListCreate(sizeof(ids)/sizeof(int),ids);

    if (list != NULL)
    {
        printf("Size %d", list->size);
    }
    
    int result = IDListContains(list,93);

    return 0;
}

idtablehashtable.h

typedef struct id_list{
    int size;
    int ids[1];         /* we will malloc more space than this*/
} IDList;

#define MIN_ID (0)
#define MAX_ID (999999999)

/** build an IDList out of an unsorted array of n good ids
 *  returns 0 on allocation failure   
 */

IDList *IDListCreate(int n, int unsorted_id_list[]);

/* destroy and IDList */
void IDListDestroy(IDList *list);

/**
 * check an id against the list
 * resturns nonzero if id is in the list
*/
int IDListContains(IDList *list, int id);