On 2017-03-01 11:05:33 +0530, Kuntal Ghosh wrote:
> On Wed, Mar 1, 2017 at 10:53 AM, Andres Freund <andres@anarazel.de> wrote:
> > On 2017-03-01 10:47:45 +0530, Kuntal Ghosh wrote:
> >> if (insertdist > curdist)
> >> {
> >> swap the entry to be inserted with the current entry.
> >> Try to insert the current entry in the same logic.
> >> }
> >>
> >> So, the second approach will not cause all the followers to be shifted by 1.
> >
> > How not? You'll have to do that game until you found a free slot.
> You can skip increasing the curdist of some elements for which it is
> already pretty high. Suppose, we've the following hash table and an
> element e,
> _,_,_,i,_,_,j,j+1,j+2,_,_
> We want to insert e at i but there is a collision and we start doing
> probing. At j, the condition if (insertdist > curdist) satisfies and
> we'll swap e with the element at j. Now, we try to insert e( = element
> at j) and so on. In this process, if the element at j+1,j+2 has
> already high distance from their optimal location, you can skip those
> element and go ahead. But, in the existing approach, we increase their
> distance further. Thoughts?
All the following elements already are at their "optimal" position given
the previous occupation of the hash-table. As we only start to move
once the insert-distance of the existing element is lower than the one
of the to-be-inserted one, the following elements will all be moved.
Doing the swap on a element-by-element basis would be possible, but just
achieves the same result at a higher cost.
Regards,
Andres
