On 15 June 2012 01:15, David Kastrup <d...@gnu.org> wrote: > Daniel Hartwig <mand...@gmail.com> 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?
