Hash Table Insertion Time Complexity Confusion

user_16846267 0
Viewed 94

I understand that insertion for hash tables is O(1) and sometimes O(n) depending on the load factor. This makes sense to me, however, I'm still confused. When talking about insertion, are we including the hash function in that measurement or is it just placing some value at that index? For ints, I could see how it could be O(1), but what about strings or any other objects?

Edit: This seemed to answer my question, sorry about the confusion. Time complexity of creating hash value of a string in hashtable

time-complexity hashtable algorithm
1 Answers

Yes, the hash function needs to be included in the cost of lookup in a hash table, just the like comparison function needs to be included in the cost of lookup in a sorted table. If the keys have unbounded size, then the key length must be somehow accounted for.

You could stop computing the hash at a certain fixed key length. (Lua does that, for example). But there is a pathological case where every new key is a suffix of the previously inserted key, which would eventually reduce a bounded-length hash function to a linear search.

Regardless of the hash function, the hash table lookup must eventually compare the found key --if there is one-- with the target key, to ensure that they are the same. So that must take time proportional to the size of the key.

In short, constant average-time hash table lookup requires that keys have a bounded size, which is not necessarily the case. But since alternative lookup algorithms would also be affected by key size, this fact doesn't generally help in comparing different lookup up algorithms.

user_15662210
Related