[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Growable arrays?

From: Daniel Hartwig
Subject: Re: Growable arrays?
Date: Fri, 15 Jun 2012 01:23:16 +0800

On 15 June 2012 01:15, David Kastrup <address@hidden> wrote:
> Daniel Hartwig <address@hidden> writes:
>> What is this half-in-place algorithm that makes this efficient?  If
>> the table is to remain balanced, all items should be rehashed and
>> reallocated to a new bucket and there is no correlation between an
>> items old and new buckets (hash).
> Huh?  Hashing computes a hash value, and the bucket is determined by
> hash % vectorsize.  Double the vector size, and the new bucket locations
> are at bucket and bucket+vectorsize, so you need to coalesce the bucket
> at bucket into the buckets at bucket and bucket+vectorsize.
> Why would there be no correlation between old and new buckets when they
> are calculated based on the same hash code?

I see.  So starting from the old tail there is little contention for
the new buckets.  This seems obvious now in hindsight :-)

Regarding the data type for your application, this is something which
needs to be accessible from the c side also?

reply via email to

[Prev in Thread] Current Thread [Next in Thread]