tags:

views:

59

answers:

1

I have a pair I know the value of the pair.first cannot be more than 1000. I also know that the pair.second , the string, is always 1 word. Never more than 1 word.
So, to construct the Hash value for the pair I am doing the following:

pair<int,string> p;
hash<char*> H;
hash_vale = H(p.second)*1000 + p.first;

I think this will give unique values as long as the hash value of strings is not too huge and that H(p.second) will give 1-1 mappings. Are these assumptions valid?

Thanks,

+4  A: 

By definition, a hash can't be one-to-one due to the pigeonhole principle. I.E., there are 2^32 possible hash values, but far more possible strings. So there must be two strings with the same hash value.

Second of all, you are almost certainly causing overflow by multiplying your hash value by 1000, since a hash should use all 32 bits. You are much better off hashing the int and then mixing the hashes. Boost has a hash_combine function: a + 0x9e3779b9 + (b << 6) + (b >> 2);

rlbond
Agreed. So, the the hash_map class will internally do chaining, manage collisions, do rehashing if needed and all that to maintain the O(1) amortized time?
ajay
Well, you really should use the c++ `unordered_map` if it's available, but yes, it will.
rlbond