Re: Growable arrays?

[Daniel Hartwig]

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?