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,