哈希表处理相同哈希值或碰撞值时为何不具备线性时间复杂度？

Great question about hashing mechanisms and the challenge of getting bucket sizes efficiently! Let's break down why this operation isn't as straightforward with linear probing or double hashing compared to other methods like chaining.

Here's what happens when you try to count all elements with a specific hash value using these open addressing techniques:

• First, you compute the hash of your target value to get the starting index in the hash table.
• Next, you have to traverse the probe sequence starting from that index, checking every non-empty slot along the way. But here's the catch: elements with the same hash aren't grouped together neatly. Earlier collisions from other keys could have pushed them further down the probe chain, and you can't just stop at the first empty slot (since some implementations use "tombstone" markers for deleted entries instead of clearing slots). You might end up scanning a large portion of the table just to find all matching elements.

The critical issue here is time complexity:

• With chaining, you can jump directly to the linked list at the bucket index and count the nodes in O(k) time, where k is the number of elements with the target hash. This is linear relative to the number of matching elements.
• With linear probing or double hashing though, there's no dedicated collection for elements sharing the same hash. You have to sift through every element in the probe chain—including those with different hashes—to tally up the matches. That means the time it takes isn't tied to k; it's dependent on the table's load factor and the length of the probe sequence, making it far less efficient than the chaining approach.

内容的提问来源于stack exchange，提问作者rb612