Re: [Boost-users] unordered_map memory footprint

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

On Thu, Apr 3, 2008 at 3:47 PM, Steven Watanabe <watanabesj_at_[hidden]>
wrote:

> 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

According to your example, what happens if I do:

insert(167);
insert(334);

???