CODEWITHSUNDEEP
c++hashxorunordered-map
thinkdeep
thinkdeep

Reputation: 1033

C++ unordered_map self defined hash function collision

Below code is for counting number of lines in a plane for different slope value. It is recommended to use a pair of x-axis and y-axis positions to denote the slope of line, b/c directly calculating the division y / x will have float precision issue. All x and y positions are integers.

Although Method I is working in test code, there are still something unclear to me:

1) For method I, pair {5, 3} and {3, 5} will have the same hash value (x ^ y), but these two lines have different slope! Why does not it cause the problem of considering both lines the same slope? Or the hash function value only determines the slot to be hashed, while comparing the equivalence of actual pair value determines whether to count them as equal?

2) Since the pair {5, 3} and {3, 5} will be hashed into the same slot, and there are lots of other similar collisions like {a, b} and {b, a}. Why does the collision hash table still produces correct final result?

3) XOR for negative integers is fine, right? Is there a better hash function we usually use here to avoid high collision?

struct hashfunc
{
    //Method I:
    size_t operator() (const pair<int,int>& l) const
    { return l.first ^ l.second; }   

    //Method II is WRONG: can NOT left shift negative int!!
    size_t operator() (const pair<int, int>& l) const {
         return l.first << 32 | l.second; 
    }
};

unordered_map< pair< int,int >, int, hashfunc> lines;

Upvotes: 0

Views: 196

Answers (1)

user10316011
user10316011

Reputation:

Complete absence of collisions is not achievable in any function whose output is smaller than the combined inputs. Correctness does not depend on lack of collisions, only perfomance does. You should get the correct results even with a hash function that returns zero all the time (try it).

the hash function value only determines the slot to be hashed, while comparing the equivalence of actual pair value determines whether to count them as equal?

Correct.

The usual method is to mash the numbers together in an unpredictable way, like

choose distinct primes a,b,c
hash(x,y) = (a*x + b*y) % c

see e.g. https://en.wikipedia.org/wiki/Universal_hashing#Hashing_integers

Upvotes: 4

Related Questions