How to identify whether or not std::unordered_map has experienced hash collisions?

Question

How to identify whether or not the keys in a std::unordered_map have experienced hash collisions?

That is, how to identify if any collision chaining is present?

Cissoid

I suspect you want to enforce some policy if it is the case, then ask the unordered_map to enforce it don't try to force it from client code. Check if max_load_factor member function solves the underling question. – Gemsbok

Answer 1

You can use the bucket interface and its bucket_size method.

std::unordered_map<int, int> map;
bool has_collision = false;

for(size_t bucket = 0; bucket < map.bucket_count(); bucket++) {
    if(map.bucket_size(bucket) > 1) {
        has_collision = true;
        break;
    }
}

Embayment

If two elements happens to be in the same bucket it does not mean that there was a hash collision. – Unaunabated

@Unaunabated -- sure it does; that's the definition of a collision. – Goya

a simple if (map.bucket_count() < map.size()) can be done to quickly check if there are any collisions to avoid the for loop in many cases – Gibeon

@Gibeon there can be empty buckets, so a total count check won't suffice. – Temuco