CODEWITHSUNDEEP
optimizationhashmaphashtable
steveclark
steveclark

Reputation: 537

How is a hash map stored?

I have an upcoming interview and was looking through some technical interview questions and I came across this one. It is asking for the time complexity for the insertion and deletion functions of a hash map. The consensus seems to be that the time complexity is O(1) if the has map is distributed evenly but O(n) if they are all in the same pool.

I guess my question is how exactly are hash maps stored in memory? How would these 2 cases happen?

Upvotes: 0

Views: 59

Answers (1)

schnaader
schnaader

Reputation: 49719

One answer on your linked page is:

insertion always would be O(1) if even not properly distributed (if we make linked list on collision) but Deletion would be O(n) in worst case.

This is not a good answer. A generalized answer to time complexity for a hashmap would come to a similar statement as the Wikipedia article on hash tables:

Time complexity
in big O notation

          Average   Worst case
Space     O(n)      O(n)
Search    O(1)      O(n)
Insert    O(1)      O(n)
Delete    O(1)      O(n)

To adress your question how hash maps are stored in memory: There are a number of "buckets" that store values in the average case, but must be expanded to some kind of list when a hash collision occurs. Good explanations of hash tables are the Wikipedia article, this SO question and this C++ example.

The time complexity table above is like this because in the average case, a hash map just looks up and stores single values, but collisions make everything O(n) in worst case, where all your elements share a bucket and the behaviour is similar to the list implementation you chose for that case.

Note that there are specialized implementations that adress the worst cases here, also described in the Wikipedia article, but each of them has other disadvantages, so you'll have to choose the best for your use case.

Upvotes: 1

Related Questions