C++ Hash Table Performance
Understand behaviors of hash tables in C++ so we can use them more correctly.
People often talk about how one type of data structure is better than another, such as hash tables. It has operations such as insert, retrieve and delete which have O(1) time complexity and O(n) space complexity. That’s what we understand from the theory we learn. But in practice, that theory is not very precise, some details are missed. If the application you are building is performance dependent, I recommend that you understand the details of hash tables.
I’ve gone into detail about how hash tables are implemented in C++ along with the full source code I published on GitHub.
This article explains how to measure the time and space complexity of data structure operations, especially hash tables. All examples compare my implementation of hash tables and GCC’s std::unordered_map, but the same technique can be used to profile other data structures.
