How do you implement a hash table in C, and what are the common techniques for handling collisions?

A hash table is a data structure that allows for efficient insertion, deletion, and retrieval of data items based on a key-value pair. In a hash table, each key is mapped to a unique index in an array using a hash function. The value associated with the key is stored in the array at the index returned by the hash function.

Here is an example of a simple hash function that maps keys to indices in an array of size N:

    int hash_function(int key, int N) {
        return key % N;
    }

This hash function takes a key value and returns an index in the range [0, N-1].

To implement a hash table in C, we need to define a struct that represents a hash table node:

    struct hash_node {
        int key;
        int value;
        struct hash_node* next;
    };

The key and value fields represent the key-value pair, and the next field is a pointer to the next node in the linked list (if collisions occur).

We also need to define a struct that represents the hash table:

    struct hash_table {
        int size;
        struct hash_node** table;
    };

The size field represents the size of the hash table (i.e., the number of buckets), and the table field is a pointer to an array of pointers to hash_node structs.

To insert a key-value pair into the hash table, we first compute the hash value for the key using the hash function. We then traverse the linked list at the index corresponding to the hash value, looking for a node with the same key. If such a node exists, we update its value. Otherwise, we create a new node and add it to the front of the linked list:

    void hash_table_put(struct hash_table* ht, int key, int value) {
        int index = hash_function(key, ht->size);
        struct hash_node* node = ht->table[index];
        while (node != NULL) {
            if (node->key == key) {
                node->value = value;
                return;
            }
            node = node->next;
        }
        node = malloc(sizeof(struct hash_node));
        node->key = key;
        node->value = value;
        node->next = ht->table[index];
        ht->table[index] = node;
    }

To retrieve a value from the hash table given a key, we first compute the hash value using the hash function. We then traverse the linked list at the index corresponding to the hash value, looking for a node with the same key. If such a node exists, we return its value. Otherwise, we return an error code:

    int hash_table_get(struct hash_table* ht, int key) {
        int index = hash_function(key, ht->size);
        struct hash_node* node = ht->table[index];
        while (node != NULL) {
            if (node->key == key) {
                return node->value;
            }
            node = node->next;
        }
        return -1;  // Error: key not found
    }

Deletion from a hash table is a bit more complicated, as we need to handle collisions and ensure that the linked list remains intact. One common technique for handling collisions is to use separate chaining, where each bucket in the hash table contains a linked list of nodes. When deleting a node, we need to update the next field of the previous node to skip over the deleted node.