Re: [Boost-users] unordered_map memory footprint

From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2008-04-03 16:47:56

AMDG

Robert Dailey wrote:
> On Thu, Apr 3, 2008 at 3:26 PM, Robert Dailey <rcdailey_at_[hidden] 
> <mailto:rcdailey_at_[hidden]>> wrote:
>
>     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?
>

lookup is O(n) if the hash function happens to return the same value for
all the elements.

>       1.
>
>
>        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.
>

unordered_map takes the user's hash function and reduces it mod the
current number of buckets.

>     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.
>
>
>
> Also, the definition of 'bucket' eludes me. If someone could explain 
> what buckets are in relation to unordered associative containers I'd 
> appreciate it.

Does the following (very naive) example implementation give some idea of 
how a hash table works?

const int num_buckets = 167;
std::vector<int> buckets[numBuckets];

void insert(int x) {
    buckets[hash(x) % numBuckets].push_back(x);
}

In Christ,
Steven Watanabe