Loading...
Hash Tables (Hash Maps) provide efficient key-value storage using hash functions to map keys to array indices. They offer near-constant time complexity for insertion, deletion, and lookup operations, making them essential for many applications.
Keys are mapped to array indices using a hash function
Maps keys to array indices for direct access
Constant time operations on average
Efficient storage and retrieval of key-value pairs
Can grow and shrink based on load factor
h(k) = k mod m
h(k) = floor(m * (k * A mod 1))
Randomly chosen hash function family
MD5, SHA-1, SHA-256 for security
Store multiple values in linked lists
Find next available slot sequentially
Use quadratic function to find slots
Use second hash function for probing
n = number of keys, m = table size
Balance between space and performance
Double table size when load factor exceeds threshold
Store frequently accessed data
Fast record lookup by key
Compiler symbol management
Efficient set operations
| Operation | Average Case | Worst Case | Notes |
|---|---|---|---|
| Search | O(1) | O(n) | Worst case with many collisions |
| Insert | O(1) | O(n) | May trigger resize operation |
| Delete | O(1) | O(n) | Depends on collision resolution |
| Space | O(n) | O(n) | Plus overhead for empty slots |
Note: Performance depends heavily on hash function quality and load factor