David Yuan David Yuan - 11 months ago 69
C++ Question

unordered_map vs vector + custom hashing for small number of elements

Current I have a nested hashmap. The inner map key has a very large range but the outer map key has only 10 different possible strings.

unordered_map<string, unordered_map<int, list<string>>> nestedHashMap;

Would it be more efficient for me to switch to

vector<unordered_map<int, list<string>>>

and have my own hashfunction

static int hashFunc(string stringToBeHashed){
case "example1":
return 0;
case "example10":
return 9;
return -1;

and do my own hashing before every look up? In terms of space complexity, due to the fact that the unordered_map is a node based container, I think this vector approach would save me some per-node memory required by unordered_map. Also, I am assuming the inner hashmap would guarantee fastest retrieval even though the key is an int. The key has a large range so I don't think using a vector here would increase performance. Right? Any comments/tips would be appreciated.

Memory is not an issue here.

Answer Source

The inner map key has a very large range

That's exactly why hashmap is a right choice here

but the outer map key has only 10 different possible strings

And there you're misusing the hashmap.
Replace it with a tree(std::map) instead.
(Yes, you can choose std::vector if you want to write a lookup function youself)
BTW, you should not be concerned with space complexity topic when you have only 10 elements :) Update:
Your outer container's purpose is basically to store 10 elements.
It is a tiny number so in theory you can chose whatever
cotainer you want (array, tree, hashtable).
So you should choose the best fit.
Choices are:

  • std::map: least code to write, sorts elements automatically
  • std::vector: best use of space, but you should write a lookup function youself
  • std::hashmap: shooting out of cannon into sparrows. You don't need 99% of functionality it provides. This contaner has different purpose than yours