HashTable Key vs Value Fetch Complexity
I just read an interview question that asked hash key complexity and hash value. I always assumed that both, at O (1 + n / k) (where k is the number of buckets). What am I missing?
Getting a hash key is O (lk) in key length because you have to use it, but n/k
it is assumed to be constant for any hash table. This is usually called O (1) since it is independent of n
, but not strictly O (1) unless the key size is fixed.
But getting the hash value would require iterating over the whole table looking for it, assuming you didn't preorder it (you can create hash tables that can support binary search too for O (log (n)), but this is unusual ).
The hash value is the starting location of the search. If the required data is not stored in this index, the hash key is obtained by iterating until the desired data is found.