@mattneub In hashed collections, collisions can occur whenever the number of buckets is smaller than the keyspace. When you're creating a new Set without specifying a minimum capacity, the set might have only one bucket, so when you're inserting the second element, a collision occurs. The insert method will then decide if the storage should be grown, using something called a load factor. If the storage was grown, the existing elements have to be migrated over to the new storage buffer. That's when you're seeing all those extra calls to hashValue when inserting 4.

The reason you're still seeing more calls to == than you would expect if the number of buckets is equal or higher to the number of elements has to do with an implementation detail of the bucket index calculation. The bits of the hashValue are mixed or "shuffled" before the modulo operation. This is to cut down on excessive collisions for types with bad hash algorithms.

Comment by Alexis Beingessner (JIRA)

What's actually happening:

• We hash a value only once on insertion.

• We don't use hashes for comparison of elements, only ==. Using hashes for comparison is only reasonable if you store the hashes, but that means more memory usage for every Dictionary. A compromise that needs evaluation.

• We try to insert the element before evaluating if the Dictionary can fit that element. This is because the element might already be in the Dictionary, in which case we don't need any more capacity.

• When we resize the Dictionary, we have to rehash everything, because we didn't store the hashes.

So what you're seeing is:

• one hash of the search key

• some =='s (searching for a space)

• hashes of every element in the collection (resize)

• one hash of the search key (actually totally wasteful, but not a big deal considering it only happens after an O👎 reallocation)

• some =='s (searching for a space in the new buffer)

Beingessner (JIRA User) Thanks so much. Valuable indeed (and eye-opening). It is very kind of you to give such full and precise information.

The talkative struct shows how useful the initializers that reserve capacity are—all the resizing is gone if you create 's' with 'Set.init(minimumCapacity:)':

var t = Set<S>(minimumCapacity: 5)
for i in 1...5 {  
    print("inserting", i)  
    t.insert(S(i)) 
} 
inserting 1
called hashValue for 1
inserting 2
called hashValue for 2
inserting 3
called hashValue for 3
inserting 4
called hashValue for 4
called == for 3 4
called == for 1 4
inserting 5
called hashValue for 5

To prevent accidentally quadratic behavior when merging dictionaries/sets (as well as an extra layer of protection against HashDoS attacks), each Set/Dictionary now uses a different hash seed, and this seed also needs to change whenever the hash table is resized. This requires rehashing every key whenever we resize the table.

This means this is now desirable/expected behavior; we cannot change it without incurring a large performance regression. (As well as an ABI break, since hash table layouts are part of the stdlib ABI.)