Advanced Data Structures: Hash Tables in C

What You’ll Learn 📚

• Core concepts of hash tables
• Key terminology explained
• Simple to complex examples
• Common questions and answers
• Troubleshooting tips

Introduction to Hash Tables

Hash tables are a type of data structure that allow you to store key-value pairs. They are incredibly efficient for tasks like looking up, inserting, and deleting data. Imagine a dictionary where you can quickly find the definition of a word. That’s similar to how a hash table works! 🗝️

Key Terminology

• Hash Function: A function that converts a given key into a specific index in the hash table.
• Collision: When two keys hash to the same index. We’ll learn how to handle these later.
• Bucket: A slot in the hash table where data is stored.

Simple Example: Creating a Basic Hash Table

#include <stdio.h> #include <stdlib.h> #include <string.h> #define TABLE_SIZE 10 typedef struct { char* key; char* value; } HashItem; HashItem* hashTable[TABLE_SIZE]; unsigned int hashFunction(char* key) { unsigned int hash = 0; for (int i = 0; key[i] != '\0'; i++) { hash += key[i]; } return hash % TABLE_SIZE; } void insert(char* key, char* value) { unsigned int index = hashFunction(key); hashTable[index] = (HashItem*) malloc(sizeof(HashItem)); hashTable[index]->key = strdup(key); hashTable[index]->value = strdup(value); } char* search(char* key) { unsigned int index = hashFunction(key); if (hashTable[index] != NULL && strcmp(hashTable[index]->key, key) == 0) { return hashTable[index]->value; } return NULL; } int main() { insert("name", "Alice"); printf("Value for 'name': %s\n", search("name")); return 0; }

Progressively Complex Examples

Example 1: Handling Collisions with Chaining

#include <stdio.h> #include <stdlib.h> #include <string.h> #define TABLE_SIZE 10 typedef struct HashItem { char* key; char* value; struct HashItem* next; } HashItem; HashItem* hashTable[TABLE_SIZE]; unsigned int hashFunction(char* key) { unsigned int hash = 0; for (int i = 0; key[i] != '\0'; i++) { hash += key[i]; } return hash % TABLE_SIZE; } void insert(char* key, char* value) { unsigned int index = hashFunction(key); HashItem* newItem = (HashItem*) malloc(sizeof(HashItem)); newItem->key = strdup(key); newItem->value = strdup(value); newItem->next = hashTable[index]; hashTable[index] = newItem; } char* search(char* key) { unsigned int index = hashFunction(key); HashItem* item = hashTable[index]; while (item != NULL) { if (strcmp(item->key, key) == 0) { return item->value; } item = item->next; } return NULL; } int main() { insert("name", "Alice"); insert("eman", "Bob"); printf("Value for 'name': %s\n", search("name")); printf("Value for 'eman': %s\n", search("eman")); return 0; }

Example 2: Deleting an Item from the Hash Table

#include <stdio.h> #include <stdlib.h> #include <string.h> #define TABLE_SIZE 10 typedef struct HashItem { char* key; char* value; struct HashItem* next; } HashItem; HashItem* hashTable[TABLE_SIZE]; unsigned int hashFunction(char* key) { unsigned int hash = 0; for (int i = 0; key[i] != '\0'; i++) { hash += key[i]; } return hash % TABLE_SIZE; } void insert(char* key, char* value) { unsigned int index = hashFunction(key); HashItem* newItem = (HashItem*) malloc(sizeof(HashItem)); newItem->key = strdup(key); newItem->value = strdup(value); newItem->next = hashTable[index]; hashTable[index] = newItem; } char* search(char* key) { unsigned int index = hashFunction(key); HashItem* item = hashTable[index]; while (item != NULL) { if (strcmp(item->key, key) == 0) { return item->value; } item = item->next; } return NULL; } void delete(char* key) { unsigned int index = hashFunction(key); HashItem* item = hashTable[index]; HashItem* prev = NULL; while (item != NULL && strcmp(item->key, key) != 0) { prev = item; item = item->next; } if (item == NULL) return; if (prev == NULL) { hashTable[index] = item->next; } else { prev->next = item->next; } free(item->key); free(item->value); free(item); } int main() { insert("name", "Alice"); insert("eman", "Bob"); printf("Value for 'name': %s\n", search("name")); delete("name"); printf("Value for 'name' after deletion: %s\n", search("name")); return 0; }

Common Questions and Answers

1. What is a hash table used for?

   Hash tables are used for fast data retrieval. They are perfect for scenarios where you need quick lookups, such as databases, caches, and dictionaries.

2. How does a hash function work?

   A hash function takes an input (or key) and returns an integer, which is the index where the value is stored in the hash table.

3. What happens if two keys hash to the same index?

   This is called a collision. We can handle collisions using methods like chaining or open addressing.

4. Why is the choice of hash function important?

   A good hash function distributes keys evenly across the hash table, minimizing collisions and ensuring efficient data retrieval.

5. Can hash tables store duplicate keys?

   No, each key in a hash table must be unique. However, you can store duplicate values.

6. What is the time complexity of hash table operations?

   In the average case, insertion, deletion, and search operations are O(1). However, in the worst case, they can degrade to O(n) due to collisions.

7. How do you handle collisions in a hash table?

   Common methods include chaining (using linked lists) and open addressing (probing for the next available slot).

8. What is chaining in hash tables?

   Chaining involves storing multiple elements at the same index using a linked list. This helps manage collisions effectively.

9. What is open addressing?

   Open addressing involves finding another slot within the table when a collision occurs, using methods like linear probing or quadratic probing.

10. How do you resize a hash table?

    Resizing involves creating a new, larger table and rehashing all existing keys into the new table. This helps maintain efficiency as the table grows.

11. What are the drawbacks of hash tables?

    Hash tables can be inefficient if the hash function is poor, leading to many collisions. They also require additional memory for storing pointers in chaining.

12. Can hash tables be used for ordered data?

    No, hash tables do not maintain order. If you need ordered data, consider using a different data structure like a binary search tree.

13. What is a load factor?

    The load factor is the ratio of the number of elements to the table size. A high load factor can lead to more collisions.

14. How do you choose the size of a hash table?

    Choose a size that is a prime number to reduce the likelihood of collisions. The size should also be larger than the expected number of elements.

15. Can hash tables store complex data types?

    Yes, hash tables can store complex data types as values, but the keys must be hashable (e.g., strings, integers).

16. What is double hashing?

    Double hashing uses two hash functions to resolve collisions, providing a more uniform distribution of keys.

17. How do you implement a hash table in C?

    Implementing a hash table in C involves defining a structure for the table, creating a hash function, and implementing functions for insertion, deletion, and search.

18. Why are hash tables so efficient?

    Hash tables offer average O(1) time complexity for operations, making them extremely fast for data retrieval compared to other data structures.

19. What is a perfect hash function?

    A perfect hash function maps each key to a unique index with no collisions. However, creating such a function is often impractical for large datasets.

20. How do you debug a hash table?

    Debugging involves checking the hash function, ensuring proper handling of collisions, and verifying that all pointers and memory allocations are correct.

Troubleshooting Common Issues

If you encounter segmentation faults, check your memory allocations and pointer dereferences. Ensure that you’re not accessing memory that hasn’t been allocated.

If your hash table isn’t returning the expected results, verify that your hash function is distributing keys evenly. A poor hash function can lead to clustering and inefficiency.

Remember to free allocated memory to prevent memory leaks, especially when deleting items from the hash table.

Practice Exercises

• Implement a hash table with open addressing using linear probing.
• Modify the hash table to store integer keys and values.
• Create a hash table that resizes dynamically as more elements are added.

Try these exercises to solidify your understanding and gain hands-on experience with hash tables in C. Happy coding! 💻