CODEWITHSUNDEEP
lua
kuniqs
kuniqs

Reputation: 308

How does Lua 5.x represent sparse arrays?

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?

Upvotes: 3

Views: 1872

Answers (2)

lhf
lhf

Reputation: 72312

You shouldn't need to worry about these details: just trust that Lua tables are implemented efficiently with expected constant-time access to an entry given its key. The array part is just an implementation detail to reduce memory usage by not needing to store some keys.

As explained by rpattiso, there is no memory waste in your example.

Upvotes: 1

ryanpattison
ryanpattison

Reputation: 6251

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.

Upvotes: 9

Related Questions