[tomerv]

There's a link in the article to a paper (N2023) proving this is not constant time. The issue is that as you delete elements, and the hash table becomes sparse, finding the next nonempty bucket is not so fast. However, I believe that the paper conveniently glosses over the fact that there will be rehashing into a smaller table which would fix this issue.

[londgine]

thanks. I got confused between constant time relative to the number of elements in the table (as typically calculated) and constant time relative to the number of slots in the table.