I had a question on a homework that asked if, for a hashtable, the number of primary collisions would be lower if you chose chaining, linear probing, or quadratic probing.

The answer is that it doesn't matter, but I thought that with chaining, there would be more unoccupied spots on the table (since you wouldn't be doing any probing), and thus that would cause less primary collisions.

Can someone help explain why my thinking is incorrect? Thanks.

I had a question on a homework that asked if, for a hashtable, the number of primary collisions would be lower if you chose chaining, linear probing, or quadratic probing.

The answer is that it doesn't matter, but I thought that with chaining, there would be more unoccupied spots on the table (since you wouldn't be doing any probing), and thus that would cause less primary collisions.

Can someone help explain why my thinking is incorrect? Thanks.

• data-structures
• hashmap
• hashtable

Share Improve this question Follow asked Nov 21, 2024 at 1:34 BobodyBobody 2122 bronze badges 2

• 2 The chaining, linear probing, and quadratic probing are about finding a new open slot after a collision. But the collision has already happened the same way in all those cases. Its just about how you resolve the collision to find a new open location. – topsail Commented Nov 21, 2024 at 1:47
• You seem to have been thinking of external chaining (data for colliding keys is kept outside the hash-table) - the question does not seem to have specified this. – greybeard Commented Nov 21, 2024 at 8:36

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 2

To understand the answer, you have to check that you understand what primary collisions are, as the name itself doesn't unambiguously communicate meaning.

Primary collisions are specifically when hashing distinct keys leads you to the same bucket, without consideration for any post-collision resolution strategy. So, it's possible to have an N-way primary collision between N keys all hashing directly to the same "home" bucket, even if the value actually stored at that bucket is another key that ended up there due to probing after a collision at its own hashed-to (home) bucket....

with chaining, there would be more unoccupied spots on the table (since you wouldn't be doing any probing), and thus that would cause less primary collisions.

The mistake here is just in "would cause less primary collisions" - it causes less collisions, but those collisions that differ are all secondary collisions (which is also a bit of a confusing term - it just means non-primary, rather than being specifically the 2nd place tried for a key; there are no "tertiary" collisions - we're not counting, just classifying into primary/direct/at-home and secondary/indirect/not-at-home).

See also: 3 a) at https://courses.cs.vt.edu/~cs3114/Summer14/HW/2/HashingSoln.pdf