5 ms·
It's not erase(), it's begin(). It's going to do a linear scan of the hash table from the beginning to find the first non-empty cell.
by eck 12y ago
It's not erase(), it's begin(). It's going to do a linear scan of the hash table from the beginning to find the first non-empty cell.
- xyzzyz 12y agoIts expected value will likely still be linear - since values are distributed among cells uniformly, and there ratio of empty cells to all cells is bounded from above (otherwise rebucketting occurs), expected position of the first nonempty cell is also close to the beginning. Calculating it is a good exercise, helpful Google keywords are "order statistics of discrete uniform distribution".
- alexbecker 11y agoNo, because you're erasing the cells in order. So the first nonempty cell will get progressively further from the beginning.