C Programming data structures Hash Table, Hash Map, and Hash Set Step by step Implementation and Top 10 Questions and Answers
 .NET School AI Teacher - SELECT ANY TEXT TO EXPLANATION.    Last Update: April 01, 2025      22 mins read      Difficulty-Level: beginner

C Programming: Understanding Data Structures - Hash Table, Hash Map, and Hash Set

Data structures are fundamental constructs used for organizing and storing data efficiently. In the realm of programming, these structures play a crucial role in determining the speed, efficiency, and ease of access to the data. Among the various data structures, hash tables, hash maps, and hash sets are incredibly powerful tools. Each of these data structures leverages the concept of hashing to provide fast retrieval, insertion, and deletion operations. Let's delve into each of them in detail.

Hash Table

Definition: A hash table is a data structure that implements an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Components:

  1. Array (Bucket Array): The primary storage where each slot is called a bucket.
  2. Hash Function: A function that converts a key into an integer, which is then mapped to an index in the bucket array.
  3. Collision Resolution: Strategies to handle cases when two keys result in the same index (hash collision).

Operations:

  • Insertion: Compute the hash value of the key and place the key-value pair in the appropriate bucket.
  • Search: Compute the hash value of the key and retrieve the value from the corresponding bucket.
  • Deletion: Locate the key, remove it, and possibly reorganize the bucket if necessary.

Advantages:

  • Average-case time complexity for search, insert, and delete operations is O(1).
  • Simple and efficient implementation.

Disadvantages:

  • Worst-case time complexity for all operations is O(n) due to collisions.
  • Requires more memory than simpler data structures like arrays.

Example in C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 300

struct DataItem {
   int data;
   int key;
};

struct DataItem* hashArray[SIZE];
struct DataItem* dummyItem;
struct DataItem* item;

int hashCode(int key) {
   return key % SIZE;
}

struct DataItem *search(int key) {
   //get the hash
   int hashIndex = hashCode(key);

   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];

      //go to next cell
      ++hashIndex;

      //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;
}

void insert(int key, int data) {

   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;
   item->key = key;

   //get the hash
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;

      //wrap around the table
      hashIndex %= SIZE;
   }

   hashArray[hashIndex] = item;
}

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

   //get the hash
   int hashIndex = hashCode(key);

   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {

      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex];

         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem;
         return temp;
      }

      //go to next cell
      ++hashIndex;

      //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;
}

void display() {
   int i = 0;

   for(i = 0; i<SIZE; i++) {

      if(hashArray[i] != NULL)
         printf(" (%d,%d)",hashArray[i]->key,hashArray[i]->data);
      else
         printf(" ~~ ");
   }

   printf("\n");
}

int main() {
   dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem));
   dummyItem->data = -1;
   dummyItem->key = -1;

   insert(1, 20);
   insert(2, 70);
   insert(42, 80);
   insert(4, 25);
   insert(12, 44);
   insert(14, 32);
   insert(17, 11);
   insert(13, 78);
   insert(37, 97);

   display();
   item = search(37);

   if(item != NULL) {
      printf("Element found: %d\n", item->data);
   } else {
      printf("Element not found\n");
   }

   delete(item);
   item = search(37);

   if(item != NULL) {
      printf("Element found: %d\n", item->data);
   } else {
      printf("Element not found\n");
   }
}

Hash Map

A hash map (also known as hash table in other programming languages) is essentially the same as a hash table. It is a data structure that stores key-value pairs, allowing fast lookups based on the key. In C++, Java, and other languages, HashMap is often used as a standard library component.

Key Differences:

  • In C, there is no built-in HashMap, so one has to implement it manually with hash functions.
  • In many other higher-level languages, HashMap offers additional functionalities, such as dynamic resizing.

Common Functions:

  • put(key, value): Adds a mapping from a key to a specific value.
  • get(key): Retrieves the value associated with a given key.
  • remove(key): Deletes the entry associated with the specified key.

Since the concepts and implementation are largely similar to hash tables, this section won't repeat those specifics in C.

Hash Set

A hash set is a data structure that implements a mathematical set using a hash table to store the elements. Unlike hash maps or hash tables, hash sets only store keys without associated values. They ensure that there are no duplicate entries.

Operations:

  • Add: Inserts an element into the set.
  • Remove: Deletes an existing element from the set.
  • Contains: Checks whether an element exists in the set.

Advantages:

  • Efficient membership checking: average time complexity is O(1).
  • No duplicates: helps maintain uniqueness.

Disadvantages:

  • Limited operations compared to hash maps or hash tables.

Example Implementation in C:

#include <stdio.h>
#include <stdlib.h>

#define SIZE 101

struct HashSetNode {
    int data;
};

typedef struct {
    struct HashSetNode* nodes;
} HashSet;

HashSet* createHashSet() {
    HashSet* set;
    int i;

    if ((set = (HashSet*) malloc(sizeof(HashSet))) == NULL) {
        fprintf(stderr, "Unable to allocate memory for HashSet\n");
        exit(1);
    }

    if ((set->nodes = (struct HashSetNode*) malloc(SIZE * sizeof(struct HashSetNode))) == NULL) {
        fprintf(stderr, "Unable to allocate memory for HashSet nodes\n");
        exit(1);
    }

    for (i = 0; i < SIZE; i++) {
        set->nodes[i].data = -1; // Initialize all elements as empty
    }

    return set;
}

unsigned long hashFunction(int n) {
    return n % SIZE;
}

int add(HashSet* set, int data) {
    unsigned long hash = hashFunction(data);

    // Resolve collision by linear probing
    while (set->nodes[hash].data != -1 && set->nodes[hash].data != data) {
        hash = (hash + 1) % SIZE;
        if (set->nodes[hash].data == data) {
            return 0; // Already present, hence didn't add
        }
    }

    set->nodes[hash].data = data;
    return 1; // Added successfully
}

int contains(HashSet* set, int data) {
    unsigned int hash = hashFunction(data);

    // Find the correct index through linear probing
    while (set->nodes[hash].data != -1) {
        if (set->nodes[hash].data == data) {
            return 1; // Found
        }
        hash = (hash + 1) % SIZE;
        if (set->nodes[hash].data == data) {
            return 1; // Found
        }
    }
    return 0; // Not found
}

int main() {
    HashSet* set = createHashSet();

    add(set, 10);
    add(set, 20);
    add(set, 30);

    printf("Contains 10: %s\n", contains(set, 10) ? "true" : "false");
    printf("Contains 40: %s\n", contains(set, 40) ? "true" : "false");

    free(set->nodes);
    free(set);

    return 0;
}

Conclusion

Hash tables, hash maps, and hash sets are powerful data structures that provide highly efficient operations for common tasks, such as searching, inserting, and deleting elements. By leveraging hashing mechanisms and effective collision resolution strategies, these structures significantly improve performance. In C programming, understanding and implementing these data structures can lead to optimized and robust applications. Despite the lack of built-in support for these structures in C, the concepts can be applied to create efficient solutions tailored to specific use cases.

Building an Application Using C Programming: Hash Table, Hash Map, and Hash Set

Introduction

Data structures are fundamental components of any programming language that help organize and manage data efficiently. Among these, hash tables, hash maps, and hash sets play significant roles due to their ability to provide quick access, insertion, and deletion operations. In this guide, we will explore how to implement a simple application in C that utilizes these data structures. Specifically, we'll create a basic application simulating a user database system where we will use a hash table, map, and set to manage user data. The application will have both frontend and backend components, illustrating data flow. We will cover each step thoroughly, making it easy for beginners to understand and follow.

Backend: Data Structures Implementation

1. Hash Table:

A hash table is a data structure that implements an associative array, a structure that can map keys to values.

// Define the structure for hash table nodes
typedef struct Node {
    int key;
    char *value;
    struct Node *next;
} Node;

// Define the structure for hash table
typedef struct HashTable {
    int capacity;
    int size;
    Node **array;
} HashTable;

// Create a new node
Node* createNode(int key, const char *value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = strdup(value);
    newNode->next = NULL;
    return newNode;
}

// Hash function
unsigned int hashFunction(int key, int capacity) {
    return key % capacity;
}

// Create hash table
HashTable* createHashTable(int capacity) {
    HashTable* hTable = (HashTable*)malloc(sizeof(HashTable));
    hTable->capacity = capacity;
    hTable->size = 0;
    hTable->array = (Node**)calloc(capacity, sizeof(Node*));
    return hTable;
}

// Insert element into hash table
void insertElement(HashTable* hTable, int key, const char *value) {
    unsigned index = hashFunction(key, hTable->capacity);
    Node* newNode = createNode(key, value);

    if (hTable->array[index] == NULL)
        hTable->array[index] = newNode;
    else {
        Node* temp = hTable->array[index];
        while (temp->next != NULL)
            temp = temp->next;
        temp->next = newNode;
    }
    ++hTable->size;
}

// Search element in hash table
char* searchElement(HashTable* hTable, int key) {
    unsigned index = hashFunction(key, hTable->capacity);
    Node* temp = hTable->array[index];

    while (temp != NULL) {
        if (temp->key == key)
            return temp->value;
        temp = temp->next;
    }
    return (char *)"NOT FOUND";
}

2. Hash Map:

While conceptually distinct, a hash map can essentially be implemented using a hash table. Here, we map strings to integer values:

// Define hash map node structure
typedef struct HashMapNode {
    char* key;
    int value;
    struct HashMapNode *next;
} HashMapNode;

// Define hash map structure similar to hash table
typedef struct HashMap {
    int capacity;
    int size;
    HashMapNode** array;
} HashMap;

// Hash function for strings
unsigned int stringHashFunction(const char* str, int capacity) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++))
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    return hash % capacity;
}

// Create hash map
HashMap* createHashMap(int capacity) {
    HashMap* hMap = (HashMap*)malloc(sizeof(HashMap));
    hMap->capacity = capacity;
    hMap->size = 0;
    hMap->array = (HashMapNode **)calloc(capacity, sizeof(HashMapNode *));
    return hMap;
}

// Insert key-value pair in hash map
void insertInHashMap(HashMap* hMap, const char* key, int value) {
    unsigned int index = stringHashFunction(key, hMap->capacity);
    HashMapNode* newEntry = (HashMapNode *)malloc(sizeof(HashMapNode));
    HashMapNode* head = hMap->array[index];
    
    if (head == NULL) {
        newEntry->key = strdup(key);
        newEntry->value = value;
        hMap->array[index] = newEntry;
        newEntry->next = NULL;
    } else {
        HashMapNode* temp = head;
        while (temp) {
            if (!strcmp(temp->key, key)) {
                temp->value = value;
                return;
            }
            temp = temp->next;
        }
        newEntry->key = strdup(key);
        newEntry->value = value;
        newEntry->next = hMap->array[index];
        hMap->array[index] = newEntry;
    }
    ++hMap->size;
}

// Retrieve value from hash map based on key
int retrieveValueFromHashMap(HashMap* hMap, const char* key) {
    unsigned int index = stringHashFunction(key, hMap->capacity);
    HashMapNode* temp = hMap->array[index];
    
    while (temp) {
        if (!strcmp(temp->key, key)) {
            return temp->value;
        }
        temp = temp->next;
    }
    return -1;  // NOT FOUND marker
}

3. Hash Set:

A hash set is a collection that contains no duplicate elements. Implementing a hash set uses concepts similar to the hash table, but with elements representing both keys and values.

// Define hash set element
typedef struct HashSetNode {
    int key;
    struct HashSetNode* next;
} HashSetNode;

// Define hash set structure similar to hash table
typedef struct HashSet {
    int capacity;
    int size;
    HashSetNode** array;
} HashSet;

// Create HashSet
HashSet* createHashSet(int capacity) {
    HashSet* hSet = (HashSet*)malloc(sizeof(HashSet));
    hSet->capacity = capacity;
    hSet->size = 0;
    hSet->array = (HashSetNode **)calloc(capacity, sizeof(HashSetNode *));
    return hSet;
}

// Insert element into HashSet
void insertInHashSet(HashSet* hSet, int key) {
    unsigned index = hashFunction(key, hSet->capacity);
    HashSetNode* newEntry = (HashSetNode *)malloc(sizeof(HashSetNode));
    HashSetNode* head = hSet->array[index];

    if (head == NULL) {
        newEntry->key = key;
        hSet->array[index] = newEntry;
        newEntry->next = NULL;
    } else {
        HashSetNode* temp = head;
        while (temp) {
            HashSetNode* prev = temp;
            temp = temp->next;
            if (prev->key == key)
                return; // Duplicate found
        }
        newEntry->key = key;
        newEntry->next = hSet->array[index];
        hSet->array[index] = newEntry;
    }
    ++hSet->size;
}

// Check if element exists in HashSet
int existsInHashSet(HashSet* hSet, int key) {
    unsigned index = hashFunction(key, hSet->capacity);
    HashSetNode* temp = hSet->array[index];
    
    while (temp) {
        if (temp->key == key)
            return 1; // Element found
        temp = temp->next;
    }
    return 0; // Element not found
}

Frontend: User Interaction

The frontend of our application will handle user input/output operations and interact with the backend data structures.

Let's create a simple menu-driven interface:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Backend functions prototypes
HashTable* createHashTable(int);
void insertElement(HashTable*, int, const char *);
char* searchElement(HashTable*, int);

HashMap* createHashMap(int);
void insertInHashMap(HashMap*, const char*, int);
int retrieveValueFromHashMap(HashMap*, const char*);

HashSet* createHashSet(int);
void insertInHashSet(HashSet*, int);
int existsInHashSet(HashSet*, int);


// Frontend functions
int main() {
    HashTable* usersTable = createHashTable(20);
    HashMap* userRolesMap = createHashMap(20);
    HashSet* uniqueIDsSet = createHashSet(20);

    int choice, userID;
    char name[20], role[10];

    printf("\n\tSimple User Database System\n");

    do {
        printf("\n1. Add User\n2. Find User by ID\n3. Retrieve Role for User\n4. Check Unique ID\n5. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter User ID: ");
                scanf("%d", &userID);
                printf("Enter Name: ");
                scanf("%s", name);
                printf("Enter Role (e.g., admin, user): ");
                scanf("%s", role);

                if(!existsInHashSet(uniqueIDsSet, userID)) { // Ensure unique ID
                    insertElement(usersTable, userID, name);
                    insertInHashSet(uniqueIDsSet, userID);
                    insertInHashMap(userRolesMap, name, strcmp(role, "admin") == 0 ? 1 : 0);
                    printf("\nUser with ID %d added successfully.\n", userID);
                } else {
                    printf("Error: This ID already exists!\n");
                }

                break;
            case 2:
                printf("Enter User ID: ");
                scanf("%d", &userID);
                printf("Name: %s\n", searchElement(usersTable, userID));
                break;
            case 3:
                printf("Enter Name: ");
                scanf("%s", name);
                printf("Role: %s\n", retrieveValueFromHashMap(userRolesMap, name) ? "Admin" : "User");
                break;
            case 4:
                printf("Enter User ID: ");
                scanf("%d", &userID);
                printf("ID %d existence: %s\n", userID, existsInHashSet(uniqueIDsSet, userID) ? "TRUE" : "FALSE");
                break;
            case 5:
                printf("Exiting...\n");
                break;
            default:
                printf("Invalid choice! Please try again.\n");
                break;
        }

    } while(choice != 5);

    free(usersTable);
    free(userRolesMap);
    free(uniqueIDsSet);

    return 0;
}

Data Flow Overview

  1. Start: The application initializes three different data structures: HashTable for storing users by ID, HashMap to map user names to roles, and HashSet for ensuring the uniqueness of IDs.

  2. Add a User:

    • Prompt user for input (ID, name, role).
    • Use HashSet (uniqueIDsSet) to check if ID already exists.
    • If ID doesn’t exist:
      • Insert the user in HashTable (usersTable) using insertElement.
      • Insert the user’s role in HashMap (userRolesMap) using insertInHashMap.
      • Add user ID to HashSet (uniqueIDsSet) to maintain uniqueness.
    • Inform the user about operation success or failure.

  3. Find User by ID:

    • Prompt user for input (ID).
    • Call searchElement on usersTable to fetch user name by ID.
    • Display the user’s name.

  4. Retrieve Role for User:

    • Prompt user for input (name).
    • Call retrieveValueFromHashMap on userRolesMap to fetch role number for user.
    • Convert role number to a human-readable form (1 → Admin, 0 → User).
    • Display the user’s role.

  5. Check if ID Exists:

    • Prompt user for input (ID).
    • Use existsInHashSet on uniqueIDsSet to determine if provided ID is unique.
    • Display the result (TRUE/FALSE).

  6. Exit: Clean up allocated memory for all data structures and terminate the application properly.

Compilation and Execution Steps

To compile and run our application:

  1. Open your terminal or command prompt.

  2. Save the above code into a single file, let’s say main.c.

  3. Compile the code by entering gcc -o userDB main.c in the terminal/command prompt. This command creates an executable named userDB.

  4. Run the executable using ./userDB.

After compiling and running, the application should present a user-friendly text-based menu through which you can interact with the user database.

Conclusion

Through this example, we walked through the implementation of basic data structures—hash table, hash map, and hash set—in C. We also created a simple application that demonstrated their usage in the context of managing a user database.

Understanding the fundamental operations (insertion, search, checking for duplicates) on hash-based data structures equips you with tools necessary to implement efficient solutions in many software systems, particularly those involving large volumes of dynamic data.

Feel free to modify and extend this application as per your learning needs or interests! Happy coding!

Certainly! Here are the top 10 questions and answers related to C programming data structures, focusing on Hash Table, Hash Map, and Hash Set:

1. What is a Hash Table in C programming?

Answer: A Hash Table is a data structure that stores key-value pairs. It uses a hash function to compute an index into an array in which an element can be inserted or searched. The idea behind hashing is to distribute entries (key-value pairs) uniformly across an array. This allows fast retrieval, insertion, and deletion of elements, typically in constant time O(1) on average.

2. How does a hash function work in a hash table?

Answer: A hash function takes an input (key) and returns an integer (hash value) which is used as an index to store the element in a hash table. An ideal hash function should minimize collisions (two keys producing the same hash value) and be fast to compute. Common hashing techniques include division method, multiplication method, and universal hashing.

3. What is a collision in a hash table, and how can it be handled?

Answer: A collision occurs when two or more keys hash to the same index. To handle collisions, there are several strategies:

  • Chaining (Separate Chaining): Each slot in the hash table points to a linked list or another data structure of entries that hash to the same index.
  • Open Addressing: When a collision occurs, the hash table searches for the next available slot using probing methods like linear probing, quadratic probing, or double hashing.

4. What are the advantages and disadvantages of hash tables in C?

Answer:

  • Advantages:
    • Fast data retrieval, insertion, and deletion operations on average.
    • Simplicity in implementation.
    • Supports an efficient way to implement associative arrays or maps.
  • Disadvantages:
    • Hash functions are crucial, and poor hash functions can degrade performance.
    • Memory usage can be high due to the need for a larger array to minimize collisions.
    • Handling collisions can introduce overhead.

5. What is a Hash Map in C?

Answer: A Hash Map (also known as a hash dictionary, hash, map, or dictionary) is a data structure that maps keys to values. Unlike a standard array, the keys can be of any data type and do not need to be integers. In C, a hash map can be implemented using a hash table with chaining or open addressing to handle collisions.

6. What is a Hash Set in C?

Answer: A Hash Set is a data structure that stores unique elements (values). It is similar to a hash map but only maintains the keys (values) without any associated value. Hash Sets are useful for quick lookups to check the existence of an item. Just like hash maps, hash sets can be implemented using hash tables with chaining or open addressing to handle collisions.

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

Answer: Implementing a hash table in C involves:

  1. Defining the Hash Table Structure: 
    struct HashTable {
    int size;
    struct Node** table;
};
  2. Creating a Node Structure for Chaining: 
    struct Node {
    int key;
    int value;
    struct Node* next;
};
  3. Creating Hash Table Functions: 
    struct HashTable* createHashTable(int size);
unsigned int hashFunction(int key, int size);
void insert(struct HashTable* ht, int key, int value);
int search(struct HashTable* ht, int key);
void delete(struct HashTable* ht, int key);
void freeHashTable(struct HashTable* ht);

8. What are the common hash functions used in C programming?

Answer: Common hash functions in C include:

  • Division Method: hash = key % tableSize
  • Multiplication Method: hash = (int)((A * key) % 1) * tableSize where 0 < A < 1 (often chosen as constants like the golden ratio)
  • Universal Hashing: This involves using random coefficients to reduce the likelihood of collisions.

9. How can you optimize a hash table for better performance in C?

Answer: To optimize a hash table for better performance:

  • Choose a Good Hash Function: Ensure the hash function distributes keys uniformly.
  • Adjust Load Factor: Maintain an optimal load factor (ratio of the number of elements to the size of the table) to minimize collisions.
  • Rehashing: Increase the size of the hash table and rehash all keys when the load factor exceeds a certain threshold.
  • Use Efficient Data Structures for Chaining: Using dynamic resizing for linked lists (like realloc) can be beneficial.

10. What are the time and space complexities of a hash table?

Answer: The time and space complexities of a hash table depend on the load factor (α) and the collision handling strategy:

  • Average Time Complexity:
    • Insertion: O(1) with good hash functions and balanced load.
    • Search/Deletion: O(1) on average.
  • Worst Time Complexity (due to collisions):
    • Insertion: O(n) if all keys hash to the same index.
    • Search/Deletion: O(n)
  • Space Complexity:
    • O(n), where n is the number of elements in the hash table. However, additional space is required for the array and linked lists/chains.

By understanding these concepts and implementations, you can efficiently use hash tables, hash maps, and hash sets in C programming to handle and manage large datasets effectively.