hash table lookup time

At a minimum, hash tables consist of an array and hash function. When an object is added to the table, the hash function is computed on the object and it is stored in the array at the index of the corresponding value that was computed. e.g., if hash(obj) = 2 then arr[2] = obj.

The average insert/lookup on a hash table is O(1).

However it is possible to have collisions when objects compute the same hash value.

In the general case there are "buckets" at each index of the array to handle these collisions. Meaning, all three objects are stored in some other data structure (maybe a linked list or another array) at the index of the hash table.

Therefore, the worst case for lookup on a hash table is O(n) because it is possible that all objects stored in the hash table have collided and are stored in the same bucket.

The hashtable hashes your key and put it in array.

For example, hash(x) = 3, where x is your key. The table then puts it into array[3]. Accessing from array is O(1).