lua-users home
lua-l archive

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

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