How to handle the case where two string has the same hash but not anagrams


  • 0
    C

    I see quite a few solutions here in C++ is using unordered_map to check if a string is anagram of another after sorting. Unordered_map internally uses std::hash to calculate the hash value of a string. Some solutions here assumes if the hash value is the same, then they must be anagrams.

    But isn't that assumption incorrect? I mean two completely different string could have the exact same hash value, correct? Then the solutions using unordered_map isn't going to be correct in this case, because it will output those two completely different strings as anagrams.


  • 0
    E

    I think this is not the point you should take into consideration. Briefly speaking, this situation will not happen. If you want to know why, you can have a look at the implementation of the HashMap and Hash Function.


  • 0
    C

    I thought the standard hash function has a collision chance of 1/numeric_limits < size _ t >::max). Given enough number of different strings, we should be able to come with a collision, no?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.