CODEWITHSUNDEEP
arrayslua
user3905355
user3905355

Reputation: 61

Will this code add hash-part to Lua array-like table?

Lua code

local var = {} 

for i = 1, 10000, 1 do
    table.insert ( var, i )
end

var[5] = { some = false, another = 2 }
var[888] = @userdata
var[10000] = {}
var[1] = 1
var[1] = false

1 ) After this, is var still only with array-part, or it has hash-part too?

2 ) Does code

var[10001] = 1

add hash-part to var or it only forces table rehash without adding hash-part ?

3) How it affects on size of table?

Thanks!

Upvotes: 1

Views: 514

Answers (1)

Alex
Alex

Reputation: 1017

The table will only have an array part after both 1 and 2. The reason is that you have a contiguous set of indices. Specifically, you created entries from 1 to 10,001 and Lua will have allocated space for them.

If for example, you had created 1 to 1000 then added 10001, it would have added the last one in the hash part rather than create nil entries for all the entries between.

It doesn't matter what type of data you put in as the value for the entries, Lua is only interested in the indices when deciding between array and hash. The exception here is setting values to nil. This can get a bit complicated but if table space is your primary concern, I don't believe Lua ever reduces the array an hash parts if you nil sets of them out. I could be mistaken on this.

As to the size, Lua uses a doubling strategy. So, after you hit entry 8192, Lua added another 8192 so there was no extra array space created between 10000 and 10001.

BTW Lua doesn't rehash every table addition. When it adds buckets, it gives itself some headroom. I believe it doubles there too. Note, if your data is sparse i.e. you aren't going to fill most of the indices between 1 and your max, then this approach to hashing can be very beneficial for space even if your indices are numbers. The main downside is it means you can't use ipairs across all your entries.

Upvotes: 1

Related Questions