Hash Tables
Description
Hash tables are data structures that implement an associative array abstract data type, allowing rapid lookup, insertion, and deletion of key-value pairs. They achieve this by using a hash function to compute an index (hash code) into an array of buckets or slots, from which the desired value can be found. Hash tables offer average-case constant time complexity for search, insert, and delete operations.
C++ Code
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<int, string> hashTable;
hashTable[1] = "One";
hashTable[2] = "Two";
hashTable[3] = "Three";
cout << "Value at key 2: " << hashTable[2] << endl;
if (hashTable.find(4) == hashTable.end()) {
cout << "Key 4 not found in hash table" << endl;
}
hashTable.erase(3);
return 0;
}
Time and Space Complexity
| Operation | Average Time Complexity | Worst-case Time Complexity | Space Complexity |
|---|---|---|---|
| Insertion | O(1) | O(n) | O(n) |
| Deletion | O(1) | O(n) | O(n) |
| Search | O(1) | O(n) | O(n) |
Where:
- n: Number of key-value pairs in the hash table.