std::hash and separate chaining

Question

I'm attempting to implement my own generic hash table using separate chaining. I'm using the std::hash() method to create my hash function. I noticed in the description of std::hash() that:

For two different parameters k1 and k2 that are not equal, the probability that std::hash()(k1) == std::hash()(k2) should be very small, approaching 1.0/std::numeric_limits::max()

Does this mean that given any two unequal strings, std::hash() will more than likely not select the same bucket? Does this mean my attempt to implement the hash table using separate chaining is moot considering this?

I'm implementing my hash table as a vector of lists. I thought there would be more collisions and therefore more elements in each list, but using the above function pretty much always gives me only one element in each list.

Please let me know if I'm misunderstanding this. Thanks.

Answer 1

No, 1/numeric_limits::max() is the probability that two randomly picked objects have same hash code, not more.

Probability of collisions during insertion into hash table is calculated differently.

Given your vector has size M (i. e. $M$ buckets), and you already inserted $N$ entries into the hash table, the fraction of empty slots, i. e. the slots with zero entries, is $e^{-N/M}$, because in hash tables with separate chaining slots with 0, 1, 2, ... entries are Poisson-distributed. This means that the probability of any collision during inserting N+1-th entry is $1 - e ^{-N/M}$.

For example, if your vector has size 64 and you inserted 32 entries, probability of collision during insertion 33-th entry is $1 - e ^{-0.5} \approx 0.39$.