| Tip |
|---|
BLUF A hash table is a data structure that provides constant-time average-case access to elements based on their key. A hash table uses a hash function to map the key of each element to an index in an array. |
...
A hash table in C++ is a data structure that implements an associative array, a structure that can map keys to values. In C++, hash tables are typically implemented using the Standard Template Library (STL) containers such as unordered_map or unordered_set.
Key Characteristics of Hash Tables:
Efficient Data Access: Hash tables provide efficient data access. Ideally, the time complexity for insert, delete, and search operations is O(1) on average.
Hash Function: A hash function is used to map keys to specific locations (buckets or slots) in the hash table. A good hash function aims to distribute keys uniformly across the table to minimize collisions (where two keys hash to the same location).
Handling Collisions: Collisions are handled using techniques like chaining (where each bucket contains a list of all elements that hash to that bucket) or open addressing (where a collision results in the algorithm probing the table to find an empty slot).
Dynamic Resizing: To maintain efficient operations, hash tables may dynamically resize. This involves rehashing all existing keys to new bucket locations when the load factor (ratio of the number of elements to the number of buckets) reaches a certain threshold.
Containers for Hash Tables:
unordered_map:
A hash table that stores key-value pairs.
Keys are unique.
Provides fast access to values based on keys.
Example:
Code Block language cpp #include <unordered_map> std::unordered_map<std::string, int> ageMap; ageMap["Alice"] = 30; ageMap["Bob"] = 25;unordered_set:
A hash table that stores individual elements (keys only).
All elements are unique.
Useful for operations like checking the presence of an element.
Example:
Code Block language cpp #include <unordered_set> std::unordered_set<int> numbers; numbers.insert(1); numbers.insert(2);
Performance Considerations:
While average-case time complexity is O(1), worst-case time complexity is O(n), where n is the number of elements in the table. This happens when the hash function does not distribute elements well, leading to many collisions.
The choice of a hash function and the load factor threshold for resizing are crucial for performance.