2

I have to write a hash function, so that I can place an std::pair<int,std::string> in an unordered_set.

Regarding the input:

  1. The strings that will be hashed are very small (1-3 letters in length).
  2. Likewise, the integers will be unsigned numbers which are small (much smaller than the limit of unsigned int).

Does it make sense to use the hash of the string (as a number), and just use Cantor's enumeration of pairs to generate a "new" hash?

Since the "built-in" hash function for std::string should be a decent hash function...

    struct intStringHash{
    public:
        inline std::size_t operator()(const std::pair<int,std::string>&c)const{
            int x = c.first;
            std::string s = c.second;
            std::hash<std::string> stringHash;
            int y = stringHash(s);

            return ((x+y)*(x+y+1)/2 + y); // Cantor's enumeration of pairs
        }
    };
Rahul Iyer
  • 19,924
  • 21
  • 96
  • 190
  • 1
    You can `boost::hash_combine`, or, if you can't use Boost for some reason, examine what they did and copy the code – milleniumbug Sep 01 '16 at 10:02
  • I can't use boost. Can you explain how to do it ? I've read another post about creating the function http://stackoverflow.com/questions/2590677/how-do-i-combine-hash-values-in-c0x , but I'm not sure how to use it regarding my function above ? – Rahul Iyer Sep 01 '16 at 10:10

2 Answers2

5

boost::hash_combine is an easy way to create hashes: even if you can't use the Boost, the function is quite simple, and so it's trivial to copy the implementation.

Usage sample:

struct intStringHash 
{
public:
    std::size_t operator()(const std::pair<int, std::string>& c) const
    {
        std::size_t hash = 0;
        hash_combine(hash, c.first);
        hash_combine(hash, c.second);
        return hash;
    }
};
milleniumbug
  • 15,379
  • 3
  • 47
  • 71
3

Yes you would generate hashes for each type that you have a hash function for.

It's normal to exclusive or hashes to combine them:

int hash1;
int hash2;

int combined = hash1 ^ hash2;
keith
  • 5,122
  • 3
  • 21
  • 50
  • can you explain why its normal ? – Rahul Iyer Sep 01 '16 at 10:14
  • For performance and brevity it's typical to use this approach to combine hashes. If each hash function is good (low collision rate) the result of combining hashes using *exclusive or* is generally good (low collision rate). After all it does not look like you are doing anything security related or creating a minimal perfect hashing function. – keith Sep 01 '16 at 10:20