On Mon, Nov 9, 2009 at 3:50 PM, "Martin v. Löwis" <martin@v.loewis.de> wrote:

I think for regular removal, the same logic should not apply: if a
series of removals is performed, then further (non-pop) removals
see increasing costs, as do regular lookups. So I think that a removal
should trigger shrinking (with appropriate thresholds) unless it's a
.pop.

Minor technicality, but it's the next() operation of the iterator that has increasing cost as the set/dict becomes sparse. Removals are always O(1). The removal uses the hash to find the item quickly. The iterator has to scan through the table for non-empty entries.

(the above assumes a good hash function with few collisions, of course)

--
Daniel Stutzbach, Ph.D.
President, Stutzbach Enterprises, LLC