C Notes
HubApplications of C Programming LanguageFeatures of C Programming LanguageHistory of C Programming LanguageWhat is C Language?Why Learn C Programming in 2024?First C Program - Hello World in C with ExplanationGCC Compiler - Complete Guide to GNU C CompilerInstall C Compiler on Linux - GCC Setup Guide for All DistrosInstall C Compiler on macOS - Xcode Command Line Tools and Homebrew GCCInstall C Compiler on Windows - MinGW, MSYS2, and WSL GuideSetup VS Code for C Programming - Complete Configuration GuideC Syntax Rules — Complete GuideComments in C ProgrammingConstants in C ProgrammingData Types in CIdentifiers in C ProgrammingKeywords in C ProgrammingStructure of a C ProgramVariables in C ProgrammingArithmetic Operators in C ProgrammingAssignment Operators in C ProgrammingBitwise Operators in C ProgrammingIncrement and Decrement Operators in CLogical Operators in C ProgrammingRelational Operators in C ProgrammingTernary Operator in C ProgrammingBreak Statement in C ProgrammingContinue Statement in C ProgrammingDo-While Loop in C ProgrammingFor Loop in C ProgrammingGoto Statement in C Programmingif-else Statement in C Programmingif Statement in C ProgrammingNested if Statements in C ProgrammingSwitch Statement in C ProgrammingWhile Loop in C ProgrammingFunction Arguments in C - Pass by Value vs Pass by ReferenceFunction Call in C ProgrammingFunction Declaration (Prototype) in CFunction Definition in C ProgrammingIntroduction to Functions in C ProgrammingRecursion in C ProgrammingReturn Statement in C ProgrammingStorage Classes in C ProgrammingArray Operations in C - Searching, Sorting, Insert and DeleteArray Programs in C - Reverse, Rotate, Duplicates, MergeIntroduction to Arrays in C ProgrammingMultidimensional Arrays in C ProgrammingOne Dimensional Arrays in C ProgrammingPassing Arrays to Functions in CTwo Dimensional Arrays in C ProgrammingString Comparison in C - strcmp, strncmp, Case-InsensitiveString Functions in C - strlen, strcpy, strcat, strcmpC String Handling Library - Complete string.h ReferenceString Manipulation in C - Reverse, Uppercase, PalindromeString Programs in C - Anagram, Word Count, Vowels, FrequencyStrings in C Programming - Complete IntroductionDouble Pointers in C - Pointer to PointerPointer Arithmetic in C ProgrammingPointer Declaration and Initialization in CPointer Programs in C - Swap, String Reversal, Dynamic AllocationPointers and Arrays in C - The Relationship ExplainedPointers and Functions in C - Pass by ReferenceIntroduction to Pointers in C ProgrammingVoid Pointers in C - Generic Pointers Guidecalloc() in C – Contiguous Memory AllocationDynamic Arrays in C – Runtime-Sized Arraysfree() in C – Releasing Dynamic Memorymalloc() in C – Dynamic Memory AllocationMemory Management Best Practices in Crealloc() in C – Resizing Dynamic MemoryBinary Files in C – fread and fwriteFile Handling in C – IntroductionFile Handling Projects in C – Student Records & Phone BookFile Modes in C – Complete Guidefopen() and fclose() in C – Opening and Closing FilesReading Files in C – fgetc, fgets, fscanf, freadWriting Files in C – fputc, fputs, fprintf, fwriteConditional Compilation in C – #ifdef, #ifndef, #if#define Macros in C – Constants and Macro FunctionsHeader Files in C – Creating Custom Headers#include Directive in C – File InclusionMacro Functions in C – Parameterized MacrosC Preprocessor – Overview and DirectivesGraphs in C – Adjacency Matrix, Adjacency List, BFS, and DFSHash Tables in C – Implementation, Collision Handling, and ChainingLinked List in C – Singly, Doubly, and Circular with ImplementationQueue in C – Linear, Circular, and Priority Queue ImplementationStack in C – Array and Linked List Implementation with ApplicationsTrees in C – Binary Search Tree Implementation with TraversalsC Programming Best Practices – Coding Standards, Safety, and PerformanceBit Fields in C – Definition, Use Cases, and Protocol HeadersC Standard Library Overview – All Headers and Common FunctionsCommand Line Arguments in C – argc and argv ExplainedDebugging Techniques in C – GDB, Valgrind, and SanitizersFunction Pointers in C – Complete Guide with ExamplesMemory Layout of a C Program – Text, Data, BSS, Heap, StackBank Management System in C – Complete Project with File StorageFile Encryption Tool in C – XOR Cipher ImplementationLibrary Management System in C – Complete Project with Source CodeMini Compiler in C – Lexer and Parser for Simple ExpressionsSnake Game in C – Console-Based Game with Source CodeStudent Management System in C – Complete Project with Source CodeC Programming Cheatsheet – Complete Quick Reference GuideTop 50 C Programming Interview Questions with Answers (2025)Memory Management Interview Questions in C with AnswersOutput Prediction Questions in C – What Will This Program Print?Pointer Interview Questions in C – Tricky Problems with AnswersCommon C Programming Errors and Solutions – Debugging GuideImportant C Programs – 50+ Frequently Asked Programs with SolutionsQuick Revision Notes for C Programming – Complete C in 10 MinutesRecommended C Programming Books – From Beginner to ExpertFormat Specifiers in C - Complete Referencegetchar() and putchar() in C Programminggets() and puts() in C ProgrammingC Input Output Programs and Examplesprintf() Function in C Programmingscanf() Function in C ProgrammingArrays of Structures in C – Managing CollectionsEnums in C – Enumerated Data TypesNested Structures in C – Struct Within StructPointers to Structures in C – Arrow OperatorStructures in C – User-Defined Data Typestypedef in C – Creating Type AliasesUnions in C – Shared Memory Data Types
Learn hash table implementation in C with hash functions, collision resolution using chaining and open addressing, performance analysis, and practical examples.
A hash table is a data structure that provides near-constant time O(1) average-case performance for insertion, deletion, and lookup operations. It uses a hash function to compute an index into an array of buckets, where the desired value can be found. Hash tables are the backbone of dictionaries, caches, database indexes, and symbol tables in compilers.
How Hash Tables Work
- Key → passed to a hash function → produces an index
- Value stored at that index in an array
- On retrieval, same hash function maps key back to the same index
The challenge arises when two different keys produce the same index – this is called a collision.
Hash Function Design
A good hash function should:
- Distribute keys uniformly across the table
- Be fast to compute
- Minimize collisions
Example
#include <stdio.h>
#include <string.h>
#define TABLE_SIZE 10
// Simple hash for integers
unsigned int hashInt(int key) {
return (unsigned int)key % TABLE_SIZE;
}
// Hash function for strings (djb2 algorithm)
unsigned int hashString(const char *key) {
unsigned long hash = 5381;
int c;
while ((c = *key++))
hash = ((hash << 5) + hash) + c; // hash * 33 + c
return hash % TABLE_SIZE;
}
int main() {
printf("Hash of 42: %u\n", hashInt(42));
printf("Hash of 137: %u\n", hashInt(137));
printf("Hash of \"hello\": %u\n", hashString("hello"));
printf("Hash of \"world\": %u\n", hashString("world"));
printf("Hash of \"name\": %u\n", hashString("name"));
return 0;
}
Output
Hash of 42: 2 Hash of 137: 7 Hash of "hello": 5 Hash of "world": 2 Hash of "name": 8
Implementation with Chaining (Separate Chaining)
Each bucket contains a linked list of entries that hash to the same index. This is the most common collision resolution strategy.
Example
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10
typedef struct Entry {
char *key;
int value;
struct Entry *next;
} Entry;
typedef struct {
Entry *buckets[TABLE_SIZE];
int count;
} HashTable;
unsigned int hash(const char *key) {
unsigned long h = 5381;
int c;
while ((c = *key++))
h = ((h << 5) + h) + c;
return h % TABLE_SIZE;
}
HashTable* createTable() {
HashTable *table = (HashTable*)malloc(sizeof(HashTable));
table->count = 0;
for (int i = 0; i < TABLE_SIZE; i++)
table->buckets[i] = NULL;
return table;
}
// Insert or update a key-value pair
void insert(HashTable *table, const char *key, int value) {
unsigned int index = hash(key);
// Check if key already exists
Entry *current = table->buckets[index];
while (current) {
if (strcmp(current->key, key) == 0) {
current->value = value; // Update existing
return;
}
current = current->next;
}
// Create new entry
Entry *entry = (Entry*)malloc(sizeof(Entry));
entry->key = strdup(key);
entry->value = value;
entry->next = table->buckets[index];
table->buckets[index] = entry;
table->count++;
}
// Search for a key
int search(HashTable *table, const char *key, int *found) {
unsigned int index = hash(key);
Entry *current = table->buckets[index];
while (current) {
if (strcmp(current->key, key) == 0) {
*found = 1;
return current->value;
}
current = current->next;
}
*found = 0;
return -1;
}
// Delete a key
void delete(HashTable *table, const char *key) {
unsigned int index = hash(key);
Entry *current = table->buckets[index];
Entry *prev = NULL;
while (current) {
if (strcmp(current->key, key) == 0) {
if (prev) prev->next = current->next;
else table->buckets[index] = current->next;
free(current->key);
free(current);
table->count--;
return;
}
prev = current;
current = current->next;
}
}
// Display the hash table
void display(HashTable *table) {
printf("\n--- Hash Table (size: %d) ---\n", table->count);
for (int i = 0; i < TABLE_SIZE; i++) {
printf("[%d]: ", i);
Entry *current = table->buckets[i];
while (current) {
printf("(%s=%d) -> ", current->key, current->value);
current = current->next;
}
printf("NULL\n");
}
}
// Free the hash table
void freeTable(HashTable *table) {
for (int i = 0; i < TABLE_SIZE; i++) {
Entry *current = table->buckets[i];
while (current) {
Entry *temp = current;
current = current->next;
free(temp->key);
free(temp);
}
}
free(table);
}
int main() {
HashTable *table = createTable();
insert(table, "alice", 25);
insert(table, "bob", 30);
insert(table, "charlie", 35);
insert(table, "david", 28);
insert(table, "eve", 22);
insert(table, "frank", 40);
display(table);
int found;
int val = search(table, "charlie", &found);
printf("\nSearch 'charlie': %s (value=%d)\n",
found ? "Found" : "Not found", val);
val = search(table, "george", &found);
printf("Search 'george': %s\n", found ? "Found" : "Not found");
delete(table, "bob");
printf("\nAfter deleting 'bob':");
display(table);
freeTable(table);
return 0;
}
Output
--- Hash Table (size: 6) --- [0]: NULL [1]: (frank=40) -> NULL [2]: (eve=22) -> NULL [3]: (david=28) -> (alice=25) -> NULL [4]: NULL [5]: NULL [6]: (bob=30) -> NULL [7]: (charlie=35) -> NULL [8]: NULL [9]: NULL Search 'charlie': Found (value=35) Search 'george': Not found After deleting 'bob': --- Hash Table (size: 5) --- [0]: NULL [1]: (frank=40) -> NULL [2]: (eve=22) -> NULL [3]: (david=28) -> (alice=25) -> NULL [4]: NULL [5]: NULL [6]: NULL [7]: (charlie=35) -> NULL [8]: NULL [9]: NULL
Open Addressing (Linear Probing)
Instead of linked lists, find the next available slot in the array when a collision occurs.
Example
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define TABLE_SIZE 13
#define DELETED ((char*)-1)
typedef struct {
char *keys[TABLE_SIZE];
int values[TABLE_SIZE];
int count;
} OpenHashTable;
unsigned int hash(const char *key) {
unsigned long h = 5381;
while (*key) h = h * 33 + *key++;
return h % TABLE_SIZE;
}
void initTable(OpenHashTable *t) {
t->count = 0;
for (int i = 0; i < TABLE_SIZE; i++) t->keys[i] = NULL;
}
bool insert(OpenHashTable *t, const char *key, int value) {
if (t->count >= TABLE_SIZE) return false;
unsigned int index = hash(key);
for (int i = 0; i < TABLE_SIZE; i++) {
unsigned int probe = (index + i) % TABLE_SIZE;
if (t->keys[probe] == NULL || t->keys[probe] == DELETED) {
t->keys[probe] = strdup(key);
t->values[probe] = value;
t->count++;
return true;
}
if (strcmp(t->keys[probe], key) == 0) {
t->values[probe] = value; // Update
return true;
}
}
return false;
}
int search(OpenHashTable *t, const char *key, bool *found) {
unsigned int index = hash(key);
for (int i = 0; i < TABLE_SIZE; i++) {
unsigned int probe = (index + i) % TABLE_SIZE;
if (t->keys[probe] == NULL) break;
if (t->keys[probe] != DELETED && strcmp(t->keys[probe], key) == 0) {
*found = true;
return t->values[probe];
}
}
*found = false;
return -1;
}
int main() {
OpenHashTable t;
initTable(&t);
insert(&t, "apple", 5);
insert(&t, "banana", 3);
insert(&t, "cherry", 8);
insert(&t, "date", 12);
bool found;
printf("apple: %d\n", search(&t, "apple", &found));
printf("cherry: %d\n", search(&t, "cherry", &found));
search(&t, "grape", &found);
printf("grape: %s\n", found ? "Found" : "Not found");
return 0;
}
Output
apple: 5 cherry: 8 grape: Not found
Collision Resolution Comparison
| Method | Pros | Cons |
|---|---|---|
| Separate Chaining | Simple, no clustering, unlimited entries | Extra memory for pointers |
| Linear Probing | Cache-friendly, no extra allocation | Clustering, performance degrades |
| Quadratic Probing | Reduces clustering | May not find empty slot |
| Double Hashing | Best distribution | More complex hash computation |
Performance Analysis
| Operation | Average Case | Worst Case |
|---|---|---|
| Insert | O(1) | O(n) |
| Search | O(1) | O(n) |
| Delete | O(1) | O(n) |
The load factor (α = n/table_size) determines performance. Keep α < 0.75 for good performance. Resize (rehash) when it exceeds this threshold.
Interview Questions on Hash Tables
Q1: What makes a good hash function? Uniform distribution, deterministic output, fast computation, and avalanche effect (small input change causes large output change).
Q2: What is the load factor and why does it matter? Load factor = number of entries / table size. As it increases, collision probability rises. Most implementations resize at 0.75 to maintain O(1) performance.
Q3: How do you handle hash table resizing? Create a new table with double the size, rehash all existing entries into the new table (since indices change with table size), then free the old table.
Q4: What's the difference between HashMap and HashSet? HashMap stores key-value pairs; HashSet stores only keys (values are implicit). Both use hash tables internally.
Q5: How is a hash table different from a binary search tree? Hash table: O(1) average lookup, unordered. BST: O(log n) lookup, ordered. Use hash tables for fast lookups; use BSTs when you need sorted order or range queries.
Summary
Hash tables provide the fastest average-case lookup of any data structure – O(1) for insert, search, and delete. The key challenge is handling collisions: separate chaining uses linked lists per bucket, while open addressing probes for empty slots. Choose your hash function carefully for uniform distribution, monitor the load factor, and resize when needed. Hash tables are indispensable in real-world software for implementing dictionaries, caches, sets, and database indexes.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Hash Tables in C – Implementation, Collision Handling, and Chaining.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this C Programming topic.
Search Terms
c-programming, c programming, programming, data, structures, hash, tables, hash tables in c – implementation, collision handling, and chaining
Related C Programming Topics
Continue learning this concept
Data Structures In CGraphs in C – Adjacency Matrix, Adjacency List, BFS, and DFSLearn graph data structure in C with adjacency matrix and adjacency list representations, BFS and DFS traversal algorithms, and complete implementation examples.Data Structures In CLinked List in C – Singly, Doubly, and Circular with ImplementationComplete guide to implementing linked lists in C covering singly linked list, doubly linked list, circular linked list, all operations with code examples and output.Data Structures In CQueue in C – Linear, Circular, and Priority Queue ImplementationLearn queue data structure in C with linear queue, circular queue, and priority queue implementations using arrays and linked lists with complete code examples.Data Structures In CStack in C – Array and Linked List Implementation with ApplicationsLearn stack data structure in C with array-based and linked list implementations, push/pop operations, applications like expression evaluation, and interview questions.Data Structures In CTrees in C – Binary Search Tree Implementation with TraversalsLearn tree data structure in C with BST implementation covering insertion, deletion, searching, inorder/preorder/postorder traversals, and tree operations.BasicsComments in C ProgrammingLearn about comments in C — single-line comments, multi-line comments, best practices, nested comments, and when to use comments effectively in your code.