| Thank you for the answer. > if you observe an entry with displacement 5 after already having visited 5 entries you can already conclude you wont find what you are looking for. Exactly. If I have already visited 5 slots without finding what I was looking for, and I'm examining the 6th one, where my target would then be "off by 6" from its natural place, and I find it filled with something that is off by 5 or less from ITS natural place, then I can abort the search knowing that my target has never been inserted because if it was inserted and arrived at this slot, the algorithm would have evicted the former occupant of the slot (smaller displacement means wealthier in Robin Hood's metaphor, so prone to be robbed of the slot). To summarize, I can abort the search when I find an entry with a displacement lower than my target would have in the same position. But the docs read higher. Hence my puzzlement. > I think it would be at most one division per lookup It's one division per visited slot, because in each slot I need to calculate the displacement of the entry that I find there. And to calculate the displacement I need to know the "natural" slot, which I calculate as hash % size. > Deletions are implemented as a special tombstone entry in the log file Agreed. > which then causes a removal from the index slot as well. That's the part that I'm missing. If you simply remove it without rearranging all the neighbor slots, the nice properties we discussed before becomes void. |
For deletions, neighbour entries would bubble up into their correct slots to preserve that property.