A question about problem 13.1 in v1.4.11, groups of anagrams

#1

Hi,

I have a question about the solution of problem 13.1 in v1.4.11. The solution uses unordered_map to map all strings with the same sorted value into the same vector of string. Thus this vector of string is a group of anagrams and multiple groups are represented by multiple vectors.

My question is: when two different sorted strings are hashed, is it possible that they have the same hash value, i.e. a collision happens? If it is possible, then two group of anagrams might be combined together. If it is not possible, it simply means that unordered_map never have any collision. I’m wondering how it achieves this. I googled for collision avoidance of unordered_map, but didn’t find any. I’m rookie to unordered_map.

Thanks,

0 Likes
#2

Sorry but I figured it out. My question was not quite valid…

0 Likes
#3

Hey Wuyang,

Thanks for your question, and personally I think it is a great question. Although you might figure it out, I still want to mention that we use sorted string as the key in unordered_map won’t have collision issue because sorted string is more like a “fingerprint” instead of “hash”. As a result, we don’t need to worry about collision here.

Again, it is a great question, and please feel free to provide more your thoughts by either sending email to us or posting here.

0 Likes