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?
--
Thanks & Regards,
Kuntal Ghosh
EnterpriseDB: http://www.enterprisedb.com
