How does Lua 5.x represent sparse arrays?

Question

Say, I have an array like this:

T = {1,2,[1000] = 3, [-1] = -1}

I know 1 and 2 will be in continous array part and -1 will be in hash part. But I don't know where 3 will be. How it will be represented 'inside' Lua. Would there be 997 wasted spaces between 2 and 3? Would 3 be delegated to hash part for efficency? Would there be 2 linked continous tables, one starting from index 1 and second starting from index 1000?

Answer 1

It depends on which version of Lua you use. In Lua 4, tables are implemented strictly as hash tables. In Lua 5, tables are part hash tables and part arrays, see the Lua Implementation where Section 4 covers tables and sparse arrays.

The array part tries to store the values corresponding to integer keys from 1 to some limit n. Values corresponding to non-integer keys or to integer keys outside the range are stored in the hash part. ... The computed size of the array part is the largest n such that at least half the blocks between 1 and n are in use... and there is at least one slot used between n/2+1 and n.

In your example, 1000 would likely be outside the initial n, and would not cause the array part to grow as it would be too sparse.