Data Structure - Hash Table
A hash table is a data structure that maps keys to specific positions in an array via a hash function, thereby achieving O(1) average time complexity for search, insertion, and deletion operations.
Hash Function and Hash Collision
Red slot = collision! key=1 and key=11 map to the same position
Hash functionThe design goal of the hash function is to convert arbitrary input (keys) into an integer (array index) within a fixed range.
A good hash function should have fast computation and uniformly distributed results.
However, since the capacity of a hash table is always limited,hash collisions—two different keys mapped to the same position—are an unavoidable phenomenon.
Collision Resolution Methods
Chaining
Each slot stores a linked list; colliding keys are appended
Advantages: simple implementation, easy deletion
Disadvantages: pointer overhead, cache unfriendly
Load factor can exceed 1.0
Open Addressing
On collision, probe the next empty slot
Advantages: no pointers, cache friendly
Disadvantages: deletion requires lazy marking
Load factor must be ≤ 0.7
| Method | Principle | Advantages | Disadvantages |
|---|---|---|---|
| Chaining | Each slot stores a linked list; colliding keys are appended to the linked list | Simple implementation, easy deletion, load factor can be greater than 1 | Extra pointer overhead, cache unfriendly |
| Open Addressing | On collision, find the next empty slot in the array according to probing rules | No pointers needed, cache friendly | Complex deletion (requires lazy deletion), load factor must be controlled |
In open addressing, when deleting an element, you cannot simply empty the slot, otherwise it will break the search chain for subsequent elements. The usual approach is to use "lazy deletion" — mark the position as "deleted" rather than "empty".
Chaining Implementation
Example
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10 /* hash table capacity */
/* hash table node */
struct HashNode {
int key;
int value;
struct HashNode* next; /* pointer to the next node in the same slot */
};
/* hash function: simple modulo method */
int hashFunc(int key) {
return key % TABLE_SIZE;
}
/* Insert key-value pair (chaining)
Time complexity: O(1) average, O(n) worst case (all keys map to the same slot) */
void insert(struct HashNode* table[], int key, int value) {
int index = hashFunc(key);
struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
newNode->key = key;
newNode->value = value;
newNode->next = table[index]; /* Head insertion */
table[index] = newNode;
}
/* Lookup: get value by key
First compute the hash value to locate the slot, then traverse the linked list to find the matching key */
int search(struct HashNode* table[], int key) {
int index = hashFunc(key);
struct HashNode* cur = table[index];
while (cur != NULL) {
if (cur->key == key) {
return cur->value; /* Found */
}
cur = cur->next;
}
return -1; /* Not found */
}
int main() {
struct HashNode* table[TABLE_SIZE] = {NULL}; /* Initialize all slots to empty */
insert(table, 1, 100); /* key=1, value=100, index=1 */
insert(table, 2, 200); /* key=2, value=200, index=2 */
insert(table, 11, 300); /* key=11, value=300, index=1 — collides with key=1! */
printf("key=1 → %d\n", search(table, 1)); /* Output: 100 */
printf("key=2 → %d\n", search(table, 2)); /* Output: 200 */
printf("key=11 → %d\n", search(table, 11)); /* Output: 300 (chaining correctly handled the collision) */
printf("key=99 → %d\n", search(table, 99)); /* Output: -1 (not found) */
return 0;
}
Application Scenarios
| Scenario | Description |
|---|---|
| Dictionary/Map | Storage and fast lookup of key-value pairs, e.g., Python's dict, Java's HashMap |
| Cache Systems | Underlying implementation of cache systems such as LRU Cache |
| Database Indexing | Hash indexing enables O(1) lookup for equality queries |
| Compiler Symbol Table | Records the mapping of variable names, function names, and their types |