Well, if you can't do queries in O(1) time, you can't do
deletes in O(1) time (because to delete something, you first
need to find it), and you can only do inserts in O(1) if
you accept duplicates - which Perl hashes don't.
Re: A short meditation about hash search performance
Replies are listed 'Best First'.
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
* Cormen, Leiserson, Rivest 1990: Introduction to Algorithms. MIT Press,
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.