/** * @file 28_hash_table_implementation.c * @brief Part 4, Lesson 28: Hash Table Implementation * @author dunamismax * @date 06-15-2025 * * This file is a major project: we will implement a Hash Table, one of the * most important and powerful data structures in all of computer science. */ /* * ===================================================================================== * | - LESSON START - | * ===================================================================================== * * PROJECT: IMPLEMENT A HASH TABLE * * So far, we've seen arrays (fast access by index, slow search) and linked lists * (slow search, flexible size). Now, we will build a data structure that offers * the best of both worlds: the HASH TABLE (also known as a Hash Map). * * WHAT IS A HASH TABLE? * A Hash Table is a data structure that maps KEYS to VALUES. You give it a key * (e.g., a person's name), and it can very quickly find the associated value * (e.g., their phone number). The goal is to achieve an average time complexity * of O(1) -- constant time -- for insertion, deletion, and searching. This is * incredibly fast and is why hash tables are used everywhere, from databases to * compiler symbol tables to the dictionaries/maps in modern languages like * Python and JavaScript. * * HOW DOES IT WORK? * 1. THE HASH FUNCTION: The magic is in the HASH FUNCTION. This is a function * that takes a key (which can be a string, number, etc.) and converts it * into an integer index. This index tells us where to store the value in * an underlying array. A good hash function distributes keys evenly across * the array to minimize collisions. * * 2. THE ARRAY (TABLE): The hash table uses a simple array as its backbone. The * index generated by the hash function corresponds to a "bucket" or "slot" * in this array. * * 3. COLLISION HANDLING: What if two different keys hash to the same index? * This is called a COLLISION. It's inevitable. We will handle collisions * using a method called SEPARATE CHAINING. This means that each slot in our * array won't hold the value directly. Instead, each slot will be a pointer * to the HEAD of a LINKED LIST. If a collision occurs, we just add the new * key-value pair as a new node in that linked list. * * OUR IMPLEMENTATION PLAN: * 1. Define an `Entry` struct (a node in our linked list for a key-value pair). * 2. Define a `HashTable` struct (which holds the main array of entry pointers). * 3. Write a `hash_function` to convert string keys to array indices. * 4. Implement `ht_create` to initialize the table. * 5. Implement `ht_insert` to add or update key-value pairs. * 6. Implement `ht_search` to retrieve a value by its key. * 7. Implement `ht_delete` to remove a key-value pair. * 8. Implement `ht_free` to clean up all allocated memory. */ // --- Required Headers --- #include #include #include // --- Part 1: Data Structures and Constants --- #define TABLE_SIZE 10 // A small size for easy demonstration // A single key-value entry. This is also a node in a linked list. typedef struct Entry { char *key; char *value; struct Entry *next; } Entry; // The Hash Table itself. typedef struct HashTable { // The table is an array of pointers to Entry structs. // This is an array of linked list heads. Entry **entries; } HashTable; // --- Function Prototypes (Lesson 7) --- // Declaring the functions up front gives a summary of the file. Their // definitions, with the explanations, follow below. unsigned int hash_function(const char *key); HashTable *ht_create(void); char *copy_string(const char *text); Entry *create_entry(const char *key, const char *value); void ht_insert(HashTable *hashtable, const char *key, const char *value); char *ht_search(HashTable *hashtable, const char *key); void ht_delete(HashTable *hashtable, const char *key); void ht_free(HashTable *hashtable); void ht_print(HashTable *hashtable); // --- Part 2: The Hash Function --- /* * This is a simple POLYNOMIAL hash function. For each character in the key, * it multiplies the running value by 37 and adds the character's code. Then * it uses the modulo operator to bring the result within the bounds of our * table size. * * Why not just add up the character codes? Because then "stop" and "pots" * (the same letters in a different order) would always collide. Multiplying * before each addition makes the position of every character count. * * `value` is unsigned, so if it grows past the largest `unsigned long` it * simply wraps around to small numbers again. That is well-defined for * unsigned types and harmless for hashing. (Overflow of a SIGNED integer, by * contrast, is undefined behavior.) * * A good hash function is crucial for performance, but this is fine for learning. */ unsigned int hash_function(const char *key) { unsigned long int value = 0; size_t key_len = strlen(key); for (size_t i = 0; i < key_len; ++i) { // The cast makes the character code 0-255 even where `char` is // signed and the key holds non-ASCII bytes. value = value * 37 + (unsigned char)key[i]; } // Return the value modulo the table size. The result is always less // than TABLE_SIZE, so converting it to `unsigned int` loses nothing; the // cast says so. return (unsigned int)(value % TABLE_SIZE); } // --- Part 3: Core Hash Table Operations --- /** * @brief Creates and initializes a new hash table. * @return A pointer to the newly created HashTable, or NULL on failure. */ HashTable *ht_create(void) { // Allocate memory for the HashTable structure itself. HashTable *hashtable = malloc(sizeof(HashTable)); if (hashtable == NULL) { return NULL; } // Allocate memory for the array of Entry pointers ("buckets"). // We use calloc to initialize all pointers in the array to NULL. hashtable->entries = calloc(TABLE_SIZE, sizeof(Entry *)); if (hashtable->entries == NULL) { free(hashtable); // Clean up partially allocated memory return NULL; } return hashtable; } /** * @brief Makes a copy of a string on the heap. * * `strcpy` never checks the size of its destination, so it is only safe when * we know the destination is big enough. Here we are sure: we allocate * exactly `strlen(text) + 1` bytes, room for every character plus the `\0`. * * Like `create_node` in Lesson 20, we stop the program if `malloc` fails. * Every caller can then rely on getting a valid copy back. */ char *copy_string(const char *text) { char *copy = malloc(strlen(text) + 1); if (copy == NULL) { fprintf(stderr, "Error: Memory allocation failed!\n"); exit(1); } strcpy(copy, text); return copy; } /** * @brief Creates a new key-value entry. */ Entry *create_entry(const char *key, const char *value) { Entry *entry = malloc(sizeof(Entry)); if (entry == NULL) { fprintf(stderr, "Error: Memory allocation failed!\n"); exit(1); } entry->key = copy_string(key); entry->value = copy_string(value); entry->next = NULL; return entry; } /** * @brief Inserts a key-value pair into the hash table. Updates value if key exists. */ void ht_insert(HashTable *hashtable, const char *key, const char *value) { unsigned int index = hash_function(key); Entry *current_entry = hashtable->entries[index]; // Traverse the linked list at this index to see if the key already exists. while (current_entry != NULL) { if (strcmp(current_entry->key, key) == 0) { // Key found, so update the value. free(current_entry->value); // Free the old value current_entry->value = copy_string(value); return; // We're done. } current_entry = current_entry->next; } // Key not found. Create a new entry and insert it at the head of the list. Entry *new_entry = create_entry(key, value); new_entry->next = hashtable->entries[index]; hashtable->entries[index] = new_entry; } /** * @brief Searches for a key in the hash table. * @return The value associated with the key, or NULL if the key is not found. */ char *ht_search(HashTable *hashtable, const char *key) { unsigned int index = hash_function(key); Entry *entry = hashtable->entries[index]; // Traverse the linked list at the calculated index. while (entry != NULL) { if (strcmp(entry->key, key) == 0) { // Key found! Return its value. return entry->value; } entry = entry->next; } // Key not found. return NULL; } /** * @brief Deletes a key-value pair from the hash table. */ void ht_delete(HashTable *hashtable, const char *key) { unsigned int index = hash_function(key); Entry *entry = hashtable->entries[index]; Entry *prev = NULL; // Traverse the list to find the entry to delete while (entry != NULL && strcmp(entry->key, key) != 0) { prev = entry; entry = entry->next; } // If entry is NULL, the key wasn't found. if (entry == NULL) { return; } // Relink the list if (prev == NULL) { // The item to delete is the head of the list hashtable->entries[index] = entry->next; } else { // The item is in the middle or at the end prev->next = entry->next; } // Free the memory for the deleted entry free(entry->key); free(entry->value); free(entry); } /** * @brief Frees all memory used by the hash table. */ void ht_free(HashTable *hashtable) { for (int i = 0; i < TABLE_SIZE; ++i) { Entry *entry = hashtable->entries[i]; while (entry != NULL) { Entry *temp = entry; entry = entry->next; free(temp->key); free(temp->value); free(temp); } } free(hashtable->entries); free(hashtable); } /** * @brief A helper function to print the contents of the hash table. */ void ht_print(HashTable *hashtable) { printf("\n--- Hash Table Contents ---\n"); for (int i = 0; i < TABLE_SIZE; ++i) { printf("Bucket[%d]: ", i); Entry *entry = hashtable->entries[i]; if (entry == NULL) { printf("~empty~\n"); continue; } while (entry != NULL) { printf(" -> [\"%s\": \"%s\"]", entry->key, entry->value); entry = entry->next; } printf("\n"); } printf("---------------------------\n"); } // --- Main Function for Demonstration --- int main(void) { printf("Creating a new hash table.\n"); HashTable *ht = ht_create(); if (ht == NULL) { fprintf(stderr, "Error: Could not create the hash table.\n"); return 1; } printf("\nInserting key-value pairs...\n"); ht_insert(ht, "name", "John Doe"); ht_insert(ht, "age", "30"); // With TABLE_SIZE 10, "age" and "city" hash to the same bucket (5): a // COLLISION. The table output below shows them chained in one list. ht_insert(ht, "city", "New York"); ht_insert(ht, "country", "USA"); ht_insert(ht, "language", "C"); ht_print(ht); printf("\nSearching for keys...\n"); char *name = ht_search(ht, "name"); char *job = ht_search(ht, "job"); // This key doesn't exist printf("Value for 'name': %s\n", name ? name : "Not Found"); printf("Value for 'job': %s\n", job ? job : "Not Found"); printf("\nDeleting key 'age'...\n"); ht_delete(ht, "age"); ht_print(ht); printf("\nUpdating key 'city'...\n"); ht_insert(ht, "city", "Los Angeles"); // This should update the existing entry ht_print(ht); printf("\nFreeing all hash table memory...\n"); ht_free(ht); printf("Memory freed successfully.\n"); return 0; } /* * ===================================================================================== * | - LESSON END - | * ===================================================================================== * * Congratulations on building a complete hash table! You've implemented one of the * most fundamental and high-performance data structures. You used dynamic memory, * pointers to pointers, structs, linked lists (for collision handling), and * string manipulation. This is a massive achievement. * * You now understand the core principles behind the dictionaries, maps, and objects * that power modern, high-level programming languages. * * HOW TO COMPILE AND RUN THIS CODE: * * 1. Open a terminal and compile the program: * `gcc -Wall -Wextra -std=c17 -o 28_hash_table_implementation 28_hash_table_implementation.c` * * 2. Run the executable: * `./28_hash_table_implementation` * * 3. Observe the output. Pay close attention to how the `ht_print` function shows * the state of the table after each operation, especially how collisions * result in linked lists within a single bucket. */