lua - Lua表的一个有趣现象

Question

我是 Lua 的新手，这些天我正在学习 table 的用法。从教程中我知道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% 密集的 2 的最大幂(这意味着如果数组部分这么大，至少 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 可以摆脱您注意到的对于在其整数序列中有孔的表的奇怪行为。