2

I'm trying to implement a hash functionality for my objects in C++, since I want to access each element by it's key as fast as possible. I'm using unordered_map container and I've written custom hash and equality functions for my class.

My question is about how the unordered_map uses my custom hash function? It uses a basic modulo operation after summing two IP addresses and ports. After the modulo operation, the result is between 0 and X, where X is a large prime number. I know that an unordered_map starts with 10 buckets initially. Does this mean that it re-hashes the value returned from my hash function with a second modulo operation so that the values fit in 0-9? I also know that I can set the number of buckets to X. But I'm not sure that I'm using the unordered_map properly. Am i missing something?

Thanks.

Caveman
  • 343
  • 3
  • 8
  • 3
    It will pretty much do `bucket = your_hash_fn(key) % num_buckets;` – Barry Oct 29 '14 at 18:54
  • 2
    I think your modulo operation is completely redundant, as `unordered_map` would do modulo operation again. Btw how many elements you expect to have in your map? – Slava Oct 29 '14 at 19:01
  • 3
    Your function should return a value representable as `std::size_t`. The unordered map template will use this with its own functional logic to determine where and it manages your item. *How* it does this is implementation-specific. If you're truly interested in the gory details of your implementation you can always read the source, as you have it in the header. 23.2.5p8 of the standard gives the only organizational requirement regarding buckets, and frankly its pretty vague. – WhozCraig Oct 29 '14 at 19:04
  • FWIW, "summing two IP addresses and ports" is fast but not a good quality hash, as if you're dealing in large numbers of elements you may well get the many duplicate sums... hashing each IP address and port separately then [combining them](http://stackoverflow.com/questions/2590677/how-do-i-combine-hash-values-in-c0x) will be far less collision prone.... – Tony Delroy Oct 30 '14 at 02:33

0 Answers0