[Boost-users] unordered_map memory footprint

From: Robert Dailey (rcdailey_at_[hidden])
Date: 2008-04-03 16:26:51

Hey guys,

Hash tables are new to me since they have never been part of the C++
standard template library, and having started C++ as my first language I
have never been exposed to them. Ever since unordered_map appeared in the
Boost library, I've been trying to understand how they function in terms of
functionality, memory, and performance. A major source of information has
been from Wikipedia, specifically this
page<http://en.wikipedia.org/wiki/Hash_table>.
Below I have outlined a few questions concerning boost::unordered_map:

   1. From what I've read, the performance of a hash table is O(1),
   however it mentions that depending on specific situations it may be O(n). Is
   this true with unordered map? If so, what conditions would force it to
   maintain O(n) complexity?
   2. What is the memory footprint of an unordered_map? From my research,
   hash tables seem to be a simple wrapper over an array in that the size of
   the "internal array" in the hash table will contain as many elements as the
   largest hash value generated by one of the key elements. So if I put two
   elements in my hash table and the generated keys are 200 and then 1,000,000,
   then the hash table would be 1,000,000 elements in size (which is at least a
   megabyte of memory in the most optimistic scenario). This logic is rather
   ridiculous and impractical, so I am pretty sure I'm misunderstanding how the
   memory mechanics work under the hood for an unordered_map.

Those are the biggest questions I have now and if I think of more I'll most
certainly be providing follow-up posts. I thank everyone in advance for
reading and helping.