CODEWITHSUNDEEP
c++algorithmhash
MaiaVictor
MaiaVictor

Reputation: 52977

What is a fast hash function for pairs of ints?

I am trying to figure out a fast datatype to store pairs of ints, where the API is just add, remove and isMember. Considering isMember must be fast, the obvious idea is to use a hash-map. Hash functions are mostly made for unbounded strings, so, my question is: considering what I am trying to hash is just a pair of ints, what is a fast hash-function with good collision properties?

Upvotes: 4

Views: 3924

Answers (2)

Arkajyoti Banerjee
Arkajyoti Banerjee

Reputation: 466

For a pair of ints you can go for Szudzik's Function. It 'elegantly' pairs two natural numbers to a unique single number.

Since you mentioned ints, it can also be negative. In that case, use different hashmaps for positive-positive, positive-negative, negative-positive, negative-negative pairs.

Upvotes: 2

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

The best you can get is to use a hash function for long long(e.g. in C++ it is built in) and use (p.first * (INT_MAX + 1) + p.second). This will work quite well in c++11 and also most of the common implementations of hash_map have a hash function for long long if this is not available you can use (((long long)p.first * prime1) + (long long)p.second) % prime2 where prime1 and prime2 are prime numbers that fit in integer.

Upvotes: 0

Related Questions