Re: Re: A short meditation about hash search performance

Perhaps I need to re-review the analysis of CLR-1990*, because they clearly state on page 223:

The worst-case running time for insertion is O(1). For searching, the worst-case running time is proportional to the length of the list: we shall analyze this more closely below. Deletion of an element x can be accomplished in O(1) time if the lists are doubly linked.

Note, I wasn't referring to perl's hashes in particular, just hashes in general.

* Cormen, Leiserson, Rivest 1990: Introduction to Algorithms. MIT Press, Cambridge Massachusetts.

[Abigail-II]

If you read page 223 carefully, you see that the arguments to the function Chained-Hash-Delete are (T, x) and not (T, k). Now x is here the node to be deleted. That is, you have already found the node with key k to be deleted. So, yes, for a double linked list, the actual deletion is in constant time, but that does not include the time to search for the node to be deleted.

Abigail

[Schemer]

Deletion of an element x can be accomplished in O(1) time if the lists are doubly linked.

It still means you need to find an object before you can delete it.