9 Nov
2009
9 Nov
'09
3:42 a.m.
The problem arises because we're systematically unbalancing the hash table. The iterator returns the first valid entry in the hash table, which we remove. Repeat several times and pretty soon the iterator has to spend O(n) time scanning through empty entries to find the first remaining valid entry.
Interesting. Something goes wrong, it seems: if items get removed over and over again, I think the set should shrink (not sure whether it actually does). Then, I think you should end up with an amortized O(1) for selecting an element (assuming that the underlying hashes don't collide).
Regards, Martin