A hash table is a data structure that provides fast insertion, deletion, and lookup operations by mapping keys to array indices using a hash function. This implementation uses chaining to handle collisions, where each array slot contains a linked list of key-value pairs.
/** * struct hash_node_s - Node of a hash table * * @key: The key, string * The key is unique in the HashTable * @value: The value corresponding to a key * @next: A pointer to the next node of the List */typedef struct hash_node_s{ char *key; char *value; struct hash_node_s *next;} hash_node_t;
/** * struct hash_table_s - Hash table data structure * * @size: The size of the array * @array: An array of size @size * Each cell of this array is a pointer to the first node of a linked list, * because we want our HashTable to use a Chaining collision handling */typedef struct hash_table_s{ unsigned long int size; hash_node_t **array;} hash_table_t;
Collision Handling via Chaining:When multiple keys hash to the same index, they form a linked list at that array position:
Array Index 0: [key1:val1] -> [key2:val2] -> NULLArray Index 1: NULLArray Index 2: [key3:val3] -> NULLArray Index 3: [key4:val4] -> [key5:val5] -> [key6:val6] -> NULL
This approach handles collisions gracefully but can degrade to O(n) in worst case.
/** * hash_table_create - creates a hash table * @size: size of the table * Return: hash table on success, NULL on failure. */hash_table_t *hash_table_create(unsigned long int size){ hash_table_t *hash_table; if (size == 0) return (NULL); hash_table = malloc(sizeof(hash_table_t)); if (hash_table == NULL) return (NULL); hash_table->size = size; hash_table->array = calloc(size, sizeof(hash_node_t *)); if (hash_table->array == NULL) { free(hash_table); return (NULL); } return (hash_table);}
Important: Uses calloc() to initialize all array pointers to NULL, indicating empty buckets.Time Complexity: O(n) where n is the size Space Complexity: O(n)
/** * hash_djb2 - implementation of the djb2 algorithm * @str: string used to generate hash value * * Return: hash value */unsigned long int hash_djb2(const unsigned char *str){ unsigned long int hash; int c; hash = 5381; while ((c = *str++)) { hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ } return (hash);}
Show Understanding the djb2 Algorithm
The djb2 hash function was created by Daniel J. Bernstein and is one of the most effective string hash functions.How it works:
/** * key_index - returns the index of a key * @key: key * @size: size of the array of the hash table * Return: index */unsigned long int key_index(const unsigned char *key, unsigned long int size){ unsigned long int index = hash_djb2(key) % size; return (index);}
The modulo operation (% size) maps the large hash value to a valid array index:
/** * hash_table_get - retrieves a value associated with a key. * @ht: the hash table you want to look into * @key: is the key you are looking for * Return: value associated with key if found, NULL if failed */char *hash_table_get(const hash_table_t *ht, const char *key){ hash_node_t *node; unsigned long int index; if (ht == NULL) return (NULL); index = key_index((const unsigned char *) key, ht->size); node = ht->array[index]; while (node != NULL) { if (strcmp(node->key, key) == 0) return (node->value); node = node->next; } return (NULL);}
/** * hash_table_delete - deletes a hash table * @ht: the hash table you want to delete */void hash_table_delete(hash_table_t *ht){ unsigned long int i; hash_node_t *node; if (ht == NULL) return; for (i = 0; i < ht->size; i++) { node = ht->array[i]; free_hash_list(node); } free(ht->array); free(ht);}/** * free_hash_list - frees a hash_node_t list * @head: head of linked list */void free_hash_list(hash_node_t *head){ hash_node_t *current; hash_node_t *next; current = head; while (current != NULL) { next = current->next; free(current->key); free(current->value); free(current); current = next; }}
Memory deallocation order:
For each bucket in the array:
Free each node’s key string
Free each node’s value string
Free the node itself
Free the array of pointers
Free the hash table structure
Critical: Must free strings before nodes, and nodes before array.Time Complexity: O(n) where n is total number of stored elements