CODEWITHSUNDEEP
c#hashtable
NealR
NealR

Reputation: 10669

Why is HashTable Delete O(1)?

I understand why a HashTable Add is O(1) (however please correct me if I'm wrong): The item being added is always allocated to the first available spot in the backing array.

I understand why a Lookup is O(n) (again, please correct me if I'm wrong): You need to walk through the backing array to find the value/key requested, and the running time of this operation will be directly proportional to the size of the collection.

However, why, then, is a Delete constant? Seems to me the same principals involved in an Add/Lookup are required.

EDIT

The MSDN article refers to a scenario where the item requested to be deleted isn't found. It mentions this as being an O(1) operation.

Upvotes: 1

Views: 1163

Answers (2)

TheEvilPenguin
TheEvilPenguin

Reputation: 5672

O(1) is the best case, and probably the average case if you appropriately size the table. Worst case deletion for a HashTable is O(n).

Upvotes: 1

AlexD
AlexD

Reputation: 32576

The worst cases for Insert and Delete are supposed to be O(n), see http://en.wikipedia.org/wiki/Hash_table.

When we Insert, we have to check if the value is in the table or not, hence O(n) in the worst case.

Just imagine a pathological case when all hash values are the same.

Maybe MSDN refers to average complexity.

Upvotes: 4

Related Questions