CODEWITHSUNDEEP
c++hashstlunordered-mapunordered-set
Shooki Matzliah
Shooki Matzliah

Reputation: 3

C++: How do unordered containers prevent duplications?

Let's take unordered_set for example. The default predicate for determining if two elements are equal is std::equal_to<T>(t1,t2), which is simply t1==t2. Now lets suppose that for this T type I've implemented operator==() so that not all member variables are part of this comparison, i.e two different T elements t1,t2 can be equal on comparison.

If the underlying hashtable calculates a different hash for each of these t1 and t2, when does it even perform the t1==t2 check for duplication of keys? and if there are more checks, how does it stay constant-time on average?

Upvotes: 0

Views: 105

Answers (3)

eerorika
eerorika

Reputation: 238331

If the underlying hashtable calculates a different hash for each of these t1 and t2, when does it even perform the t1==t2 check for duplication of keys?

When the hash function causes newly inserted element to be placed into a non-empty bucket. Comparison will be made between pre-existing elements in that bucket to ensure uniqueness.

how does it stay constant-time on average?

By assuming that the hash function distributes random keys into the buckets evenly, and by increasing the number of buckets as the number of elements grows.

how could std::hash know how i implement openrator==()

Whoever writes the specialisation of std::hash for your class must know how you implement operator==.

The hash function must produce same hash for all elements that compare equal. If it doesn't, then the behaviour of the program will be undefined. Standard refs: [unord.req], [defns.required.behavior]

Upvotes: 1

Marshall Clow
Marshall Clow

Reputation: 16670

I think the key point that you're missing is that you supply two functors to the unordered container, and they have to work together.

There's the hash function, which calculates a number from an object.

There's a comparison function, which compares two objects for "equivalence".

As @Eljay said in his comment, for two objects that compare "equivalent" (the comparison function returns true), the hash function must return the same value.

If your functions do not provide this guarantee, then the containers will not work correctly.

Relatively good reference (though not authoritative)

std::unordered_set: Meets the requirements of UnorderedAssociativeContainer.
UnorderedAssociativeContainer: are parameterized by Key/Hash/Pred.
With the requriement:
* If two Keys are equal according to Pred.
* Hash must return the same value for both keys.

Upvotes: 5

Miles Budnek
Miles Budnek

Reputation: 30494

The unordered associateive containers require that any two keys that compare equal also have the same hash. From [unord.req]:

The container's object of type Hash — denoted by hash — is called the hash function of the container. The container's object of type Pred — denoted by pred — is called the key equality predicate of the container.

Two values k1 and k2 are considered equivalent if the container's key equality predicate pred(k1, k2) is valid and returns true when passed those values. If k1 and k2 are equivalent, the container's hash function shall return the same value for both.

Your operator== and std::hash implementations must be consistent. If they are not then you have not fulfilled the prerequisites required to use your class as the key in an unordered associative container.

Upvotes: 1

Related Questions