While answering Data structure algorithm questions, if we use a Hashtable(say the one in Java's collection framework) to solve the question, shall we consider underlying complexity of Hashtable or can we safely assume it as O(1)?
I have seen many posts where it is being treated as O(1) but I am wondering why are we ignoring the underlying operations, like hashing algorithm that runs to get values for the given key, performed by Java?
To answer your question you will have to consider how hash tables actually work. HashTables are essentially arrays which map keys to its values. Where each key's location in the array depends upon the hashing function(the hashing function maps an input to a single output value). Let's assume the hashing function is O(1).
Inserting a value:
If we want to insert something into a hash table we use the hashing function (f) on the key to locate a place to store it, then we store the value at that location. Each time we insert something into the array it will take O(1) time since the hashing function is O(1). The same is true for searching for values in the hash table.
Searching for a value:
If we want to search for a value x we have to solve for f(x) which will tell us the location of x within the hashtable. This means searching through the hash table would also be O(1).
Acknowledging the underlying complexity:
The answers above are true, but only if the hashing function never produces the same output for any given input (which can be difficult to accomplish). This means that hashing functions sometimes use alternative methods to avoid such collisions. These alternative methods will often be O(1) to arrive at the first location, but will call for additional operations (such as a linear search) in order to find an empty location.
Essentially hash table operations (insert and search) are O(1) however in cases where there are collisions within the table(multiple keys pointing to the same location) these operations can take a little longer.
