CODEWITHSUNDEEP
hashmapcomplexity-theory
stack-dot-push
stack-dot-push

Reputation: 73

hashmap remove complexity

So a lot of sources say the hashmap remove function is O(1), but I don't see how this could be unless a hashmap were backed by a linkedlist because list removals are O(n). Could someone explain?

Upvotes: 5

Views: 8979

Answers (3)

Ahmed Nabil
Ahmed Nabil

Reputation: 18996

If your HashMap is backed by a LinkedList buckets array
The worst case of the remove function will be O(n)

If your HashMap is backed by a Balanced Binary Tree buckets array
The worst case of the remove function will be O(log n)

The best case and the average case (amortized complexity) of the remove function is O(1)

Upvotes: 0

Sujit
Sujit

Reputation: 101

I don't think the remove(key) complexity is O(1). If we have a big hash table with many collisions, then it would be O(n) in worst case. It very rare to get the worst case but we can't neglect the fact that O(1) is not guaranteed.

Upvotes: 2

tb-
tb-

Reputation: 1290

You can view a Hasmap as an array. Imagine, you want to store objects of all humans on earth somewhere. You could just get an unique number for everyone and use an array with a dimension of 10*10^20. If someone is born, she/he gets the next free number and is added to the end. If someone dies, her/his number is used and the array entry is set to null.

You can easily see, to add some or to remove someone, you need only constant time. calculate array address, done (if you have random access memory).

What is added by the Hashmap? There are 2 motivations. On the one side, you do not want to have such a big array. If you only want to store 10 people from all over the world, nearly all entries of the array are free. On the other side, not all data you want to store somewhere have an unique number. Sometimes there are multiple times the same number, some numbers do now show overall and sometimes you do not have any number. Therefore, you define a function, which uses the big numbers from the input and reduce them to numbers in a smaller range. This reduction should be in a way, that the resulting number is most likely unique for different inputs.

Example: Lets say you want to store 10 numbers from 1 to 100000000. You could use an array with 100000000 indices. Or you could use an array with 100 indices and the function f(x) = x % 100. If you have the number 1234, f(1234) = 34. Mark 34 as assigned.

Now you could ask, what happens if you have the number 2234? We have a collision then. You need some strategy then to handle this, there are several. Study some literature or ask specific questions for this.

If you want to store a string, you could imagine to use the length or the sum of the ascii value from every characters.

As you see, we can easily store something, and easily access it again. What we have to do? Calculate the hash from the function (constant time for a good function), access the array (constant time), store or remove (constant time).

In real world, a good hash function is not that easy. Try to stick with the included ones in java.

If you want to read more details, the wikipedia article about hash table is a good starting point: http://en.wikipedia.org/wiki/Hash_table

Upvotes: 4

Related Questions