CODEWITHSUNDEEP
c++data-structureshashunordered-map
Arun R Nambiar
Arun R Nambiar

Reputation: 147

How to get chained values in case of Collision in unordered_map?

If the unordered_map in c++ uses chaining as collision resolution. How can the chained values /Linked lists be accessed?

    unordered_map<int,int> diff;
    //collision : inserting two entries with same key 1
    diff.insert(make_pair(1, 7));
    diff.insert(make_pair(1, 26));

    cout<<diff[1];

The output is just 7 How can I get both 7 and 26 assuming chaining is used in unordered_map for collision resolution.What is the behavior of unordered_map in such scenarios?

Upvotes: 0

Views: 616

Answers (3)

Tony Delroy
Tony Delroy

Reputation: 106086

This question shows a misunderstanding of how chaining is used, and what people normally mean by a collision.

In your example code:

unordered_map<int,int> diff;
//collision : inserting two entries with same key 1
diff.insert(make_pair(1, 7));
diff.insert(make_pair(1, 26));

The two insertions have the same key, so they map to the same bucket in the hash table. The first insert finds the bucket empty, so {1,7} is linked from that bucket. The second time, the insert function finds the already-inserted key 1 linked from the bucket, and gives up on the insertion.

You shouldn't call this a "collision" though: it was the same key for both insert calls, which gets hashed by a hash function and mapped to a "bucket" in the hash table, but the same key will always map to the same bucket - that's an inherent property of hash functions and tables.

A collision is when two distinct keys map to the same bucket.

Hash tables support collisions: they let you store many {key,value} pairs with distinct keys that collide to the same bucket.

unordered_map does not support duplicate keys: i.e. multiple {key, value} pairs with the same key.

The output is just 7 How can I get both 7 and 26 assuming chaining is used in unordered_map for collision resolution.What is the behavior of unordered_map in such scenarios?

You can't get the two key-value pairs {1,7} and {1,26} into the same unordered_map at the same time. To actually allow the same key to be associated with multiple values - so insert doesn't search the bucket's chained elements to see if the key was already inserted and abort when it's found - you must use an unordered_multiset instead.

When using unordered_multiset, there's some logical justification for calling it a collision when multiple same-key values are inserted, as both pairs can't be first in the list of chained nodes - one has to push the other out of the way or go to the back of the line - so to speak, just as for a differenting-key collision at that bucket. Still, to avoid confusion, I recommend you reserve the "collision" terminology for differenting-key collisions.

Upvotes: 4

Jeffrey
Jeffrey

Reputation: 11400

If you want more than one value per key, you need to use an unordered_multimap. Your current code doesn't store a second value for 1.

https://en.cppreference.com/w/cpp/container/unordered_multimap

You'll lose the ability to use operator[] though.

Upvotes: 1

MikeCAT
MikeCAT

Reputation: 75062

The second insertion with key that is already exists will fail.

quote from std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::insert - cppreference.com:

insert_return_type insert(node_type&& nh); (7) (since C++17)

7) If nh is an empty node handle, does nothing. Otherwise, inserts the element owned by nh into the container, if the container doesn't already contain an element with a key equivalent to nh.key().

7) Returns an insert_return_type with the members initialized as follows: if nh is empty, inserted is false, position is end(), and node is empty. Otherwise if the insertion took place, inserted is true, position points to the inserted element, and node is empty. If the insertion failed, inserted is false, node has the previous value of nh, and position points to an element with a key equivalent to nh.key().

Upvotes: 2

Related Questions