Let's have a hash table with n keys, and each key has a bucket of only one value. Suppose that we look for a key that doesn't exist in the hash table, what will be the worst-case time complexity of this operation?
In my opinion, it'll be O(n). The hashfunction will have to review all its keys in order to figure out that the given key doesn't exist in the hash.
What do you think? Am I right?
It depends on the implementation. I would expect the time complexity to be O(1) because, by nature, hash tables do not iterate through elements to find elements, but index directly in memory based on the hashing method. The only time it is beyond O(1) is when it needs to re-size the memory or runs into collisions. Of course, there are lots of little details beyond this and differences between hashing algorithms that affect things. Here is a good thread to look at for more information:
