Hacker News Reader

What's the problem with iterator increment being (amortized) constant time for closed addressing? The algorithm could iterate over each bucket and on each bucket iterate over each element. Going from the end of one bucket to the start of the next one may be slower than within the same bucket, but still constant time.

View on HN

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.

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.

Reply on news.ycombinator.com