Re: A question about table's length

[Philippe Lhoste <PhiLho@...>]

On 30/12/2009 08:52, steve donovan wrote:
> So, what ultimately _is_ the array part?  What is the least suprising
> definition?

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
> problems.

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 
plain C...

That said, what h visli shown is the kind of code we write when 
exploring the language and asking some questions ("what if..."). :)

--
Philippe Lhoste
--  (near) Paris -- France
--  http://Phi.Lho.free.fr
--  --  --  --  --  --  --  --  --  --  --  --  --  --