Question about unordered map

[Anmol444]

This http://www.cplusplus.com/reference/unordered_map/unordered_map/

Says that


---------------------------------------------------------

"Internally, the elements in the unordered_map are not sorted in any particular order with respect to either their key or mapped values, but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values (with a constant average time complexity on average)."

---------------------------------------------------------


So basically a hash function operates on the data sent to it and creates a "bucket (maybe a container)" for that hash value so if other data has the same hash value it can be stored in the bucket? This is called a hash table right?

Also how does the key identify the data if it is stored in a hash table with the hash value identifying it? Is the data stored as a pair? Or is the key actually turned into the hash value?

Also what advantage does this give over other containers in speed and efficiency? Actually not just what, but why?

[keskiverto]

http://www.sgi.com/tech/stl/complexity.html

[MiiNiPaa]

Is the data stored as a pair?

Yes.

Also what advantage does this give over other containers in speed and efficiency?

Hash tables have average O(1) complexity while accessing element by its key, inserting and erasing elements. Normal map (usually created using red-black trees) have O(log(n)) complexity in such cases.

Some info on hash tables:
http://www.cs.auckland.ac.nz/software/AlgAnim/hash_tables.html
http://en.wikipedia.org/wiki/Hash_table

[AbstractionAnon]

This is called a hash table right?

Yes.

Also how does the key identify the data if it is stored in a hash table with the hash value identifying it?

The hash value identifies a bucket. Hash values have a low but non-zero probability of collision (two key values with the same hash). Only when a collision occurs, is the Pred argument is called to determine if key values are the same. How unique keys with the same hash value are maintained is implementation specific, but is commonly implemented as a list anchored by the hash bucket.

Is the data stored as a pair?

Yes. Each list entry is a key-value pair.

Or is the key actually turned into the hash value?

The key is used to compute the hash, but the key must still be maintained since the hash is not guaranteed to be unique.

Also what advantage does this give over other containers in speed and efficiency?

The advantage over a standard map is that inserts and retrievals are very fast compared to a standard map. No ordering is required. In a standard map, each node of the tree must be traversed on insert and retrieval by value and the key compared at each node. With an unordered_map, the only time a comparison is done is when there is a hash collision.

[Anmol444]

By pair I mean the stl class pair. So like in each bucket it is stored as a pair. Well thanks!

[AbstractionAnon]

Yes, I was referring to std::pair, although that would be implementation dependent.

So like in each bucket it is stored as a pair

Not quite. Each bucket contains a std::list<pair<keyT,valT>>. Remember that a bucket does not uniquely identify a key. For example on an insert, the list must be run to ensure the key being inserted is not a duplicate. Likewise on a find, the list must also be run to find a match on the key.

[Anmol444]

In unordered_multimap its a bit different right?

And on insert the key is converted the hash value and then the correct bucket is chosen right?

[keskiverto]

No, it cannot be different, because the list and bucket are parts of the unordered_map.

[MiiNiPaa]

And on insert the key is converted the hash value and then the correct bucket is chosen right?

Right, hash is generated from key and pair <key, value> is stored in appropriate bucket.

[Anmol444]

Alright thanks!


@keskiverto

Then how does unordered_multimap work?

[Peter87]

AbstractionAnon wrote:

Yes, I was referring to std::pair, although that would be implementation dependent.

The interface of std::unordered_map exposes std::pair so the implementation is kind of forced to use it internally.

Anmol444 wrote:

Then how does unordered_multimap work?

It probably stores all elements with the same key in the same bucket.

[Anmol444]

Yea thats what I said but keskiverto said it cant be different.

[keskiverto]

Miscommunication.

unordered_map has bucket per hash and a list in each bucket just in case that two keys have same hash. If you search for a key, you get at most one hit.

unordered_multimap very similar, except it expects to have multiple entries with same key in a list. If you search for a key, you can get multiple answers.

Algorithms differ, but datastructure does not need to.

[Anmol444]

Thanks!