Hash Table v.s. Mutable Array

It’s common sense that the time complexity of insertion and removal of a hash table are all both O(1), while array takes O(n) for removal. However, when the data size(n) is small, the array will beat the hash table.

Here is the result from my test(gist here)

By the results, if you are pretty sure the data size is less than 50 then you should use std::vector instead of std::unordered_map.

On the other hand, if you need to insert and remove itmes frequently, and the data size is greater than 50, then you should use std::unordered_map instead of std::vector. If items are inserted frequently but removed rarely, std::vector is fine.