This is the 8th Part of Tutorial Series on unordered_map. In this tutorial, we will discuss about the time complexity of certain operations in unordered_map like Insertion, Seraching, and Deletion of elements.
The Standard Template Library in C++, provides an associative container unordered_map. It is implemented as a hash table, and the time complexity of its common operations such as insert, find, and remove is important for understanding its performance characteristics.
Let’s know about average and worst case complexities of these operations
Time complexity of Insertion in unordered_map
- Average case: ( O(1) ) – Typically, insertion in an unordered_map is a constant-time operation. The hash function computes the position where the element should be inserted, and then the element is placed into the appropriate bucket.
- Worst case: ( O(n) ) – In the worst-case scenario, if all elements are hashed to the same bucket, the complexity becomes linear in the size of the map, because the new element needs to be inserted into a bucket that already contains ( n ) elements, making it necessary to traverse through all of them.
Time complexity of Searching in unordered_map
- Average case: ( O(1) ) – Finding an element, given a key, is usually a constant-time operation. The hash of the key is computed to find the appropriate bucket, and then the bucket is searched, which is typically fast if the hash function is good and the load factor is maintained properly.
- Worst case: ( O(n) ) – If hash collisions occur frequently, or if the hash function is not distributing the elements uniformly across the buckets, the time to search for an element can degrade to ( O(n) ).
Time complexity of Deletion in unordered_map
- Average case: ( O(1) ) – Removing an element is generally a constant-time operation. The hash function identifies the bucket, and the element is then removed from it.
- Worst case: ( O(n) ) – Like with insertion and search, the worst-case scenario occurs when all elements are in the same bucket, requiring a traversal of all elements to find and remove the specific element.
Factors that controls the performance of unordered_map in C++
Load Factor and Rehashing in unordered_map:
The time complexity of these operations also depends on the load factor of the unordered_map. The load factor is the ratio of the number of elements to the number of buckets in the hash table. When the load factor grows beyond a certain threshold (which can be controlled in C++), rehashing occurs where the hash table increases the number of buckets and redistributes the elements. Rehashing can momentarily cause a higher cost for the operation that triggers it.
Quality of Hash Function in unordered_map:
A good hash function that distributes elements uniformly across the buckets can significantly impact performance. Poor hash functions leading to many hash collisions will degrade the performance of an unordered_map.
Bucket Count in unordered_map:
If the number of buckets is set too high relative to the number of elements, it can lead to excessive memory usage, whereas too few buckets can lead to poor performance due to collisions.
Understanding these complexities and factors affecting is crucial for optimizing the performance of an unordered_map in C++ programs, especially in scenarios where time efficiency is critical.
In this tutorial, we learned about the