[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: A question about table's length
- From: Philippe Lhoste <PhiLho@...>
- Date: Wed, 30 Dec 2009 11:05:28 +0100
On 30/12/2009 08:52, steve donovan wrote:
So, what ultimately _is_ the array part? What is the least suprising
Perhaps the comment from ltable.c:
Implementation of tables (aka arrays, objects, or hash tables).
Tables keep its elements in two parts: an array part and a hash part.
Non-negative integer keys are all candidates to be kept in the array
part. The actual size of the array is the largest `n' such that at
least half the slots between 0 and n are in use.
Hash uses a mix of chained scatter table with Brent's variation.
A main invariant of these tables is that, if an element is not
in its main position (i.e. the `original' position that its hash gives
to it), then the colliding element is in its own main position.
Hence even when the load factor reaches 100%, performance remains good.
On 29/12/2009 13:48, Vaughan McAlley wrote:
> As everyone says, keep your table hole-free and there will be no
Good advice, we rarely need holes in plain arrays, or manage them
differently (as Steve shown). After all, we have to do it this way in
That said, what h visli shown is the kind of code we write when
exploring the language and asking some questions ("what if..."). :)
-- (near) Paris -- France
-- -- -- -- -- -- -- -- -- -- -- -- -- --