Lua表的一个有趣现象

Question

我是Lua的新手,这些天我正在学习桌子的用法.从教程中我知道Lua对数字索引项和非数字索引项的处理方式不同,所以我自己做了一些测试,今天我发现了一个有趣的现象,我无法解释它:

代码

t = {1, 2, 3, a='a', b='b'}
print(#t)

得到

3

因为#运算符仅计算数字索引项.然后我测试了以下代码

t = {1, 2, 3, a='a', b='b'}
print(#t)

for i = 100,200 do
    t[i] = i
end
print(#t)

我明白了

3
3

直到现在我认为Lua将稍后添加的不连续项目视为非数字索引项目.但是,在我更改代码之后

t = {1, 2, 3, a='a', b='b'}
print(#t)

for i = 100,300 do
    t[i] = i
end
print(#t)

我明白了

3
300

我对这种现象感到困惑,有谁知道原因？谢谢.

(这种现象可以在http://www.lua.org/cgi-bin/demo上复制)

更新:

我试过这段代码

t = {1, 2, 3, a='a', b='b'}
print(#t)

for i = 100,300 do
    t[i] = i
    print("add", i, #t)
end

for i = 100,300 do
    t[i] = nil
    print("del", i, #t)
end

我明白了

3
add 100 3
add 101 3
add 102 3
...
add 223 3
add 224 3
add 225 3
add 226 226
add 227 227
add 228 228
...
add 298 298
add 299 299
add 300 300
del 100 300
del 101 300
del 102 300
...
del 253 300
del 254 300
del 255 300
del 256 3
del 257 3
del 258 3
...
del 298 3
del 299 3
del 300 3

这个例子表明Lua确实在稀疏和密集之间转换了一个表.

Answer 1

我没有看过#运算符是如何实现的,但是我打赌正在发生的是通过添加额外的100个索引,你已经使得范围1-300变得足够密集以至于索引100-300最终在"数组"部分中表实现而不是"哈希"部分.

更新:

好的,我查看了原始表长度的来源.如果数组部分中的最后一个条目是nil,则它对数组进行二进制搜索以找到最低的"边界"(非零索引后跟一个nil索引).如果它不是nil,则它决定边界必须在散列中并搜索它.

因此,对于包含数字索引的表{1, 2, 3, 100..200},我认为它不够密集且数组部分只包含{1, 2, 3}.但是对于包含的表{1, 2, 3, 100..300},它可能足够密集,阵列部分在100..300部分内的某处结束(我认为数组部分总是2的幂,所以它不可能结束300,但我不是100%正面) .

更新2:

当重新处理lua表时,它会计算整数键的数量.然后它将两个不超过积分键数量的两个幂的所有权力提升,并找到最大的2的幂,其密度至少为50%(这意味着如果阵列部分如此大,至少50%所有价值观都是非零的.

因此{1, 2, 3, 100..200},它走了

1: 100% dense; good
2: 100% dense; good
4: 75% dense; bad
8: 37.5% dense; bad
16: 18.75% dense; bad
32: 9.375% dense; bad
64: 4.6875% dense; bad
128: 25% dense; bad
256: 40.625% dense; bad

最好的值是2,因此最终得到的数组大小为2.因为它2是非零的,所以它会搜索哈希的边界并找到3.

一旦你添加201..300了最后一步就变成了

256: 62.5% dense; good

这导致数组部分覆盖1..256,并且因为它256是非零的,它再次搜索哈希中的边界并得到300`.

最后,Lua 5.2将一个"序列"定义为一个表,其中只有整数键从1开始向上并且没有孔.它定义#为仅对序列有效.这样Lua就可以逃脱你注意到的那些在其整数序列中有漏洞的表格的奇怪行为.

Answer 2

仅当表是序列时,才定义表t的长度,即,对于某个整数n,其正数字键的集合等于{1..n}.