lua - 为什么 Lua 的长度 (#) 运算符会返回意外值？

Question

Lua 有 # 运算符来计算用作数组的表的“长度”。
我检查了这个运算符，我很惊讶。

这是我在 Lua 5.2.3 下运行的代码:

t = {};
t[0] = 1;
t[1] = 2;
print(#t); -- 1 aha lua counts from one
t[2] = 3;
print(#t); -- 2 tree values, but only two are count
t[4] = 3;
print(#t); -- 4  but 3 is mssing?
t[400] = 400;
t[401] = 401;
print(#t); -- still 4, now I am confused?


t2 = {10, 20, nil, 40}
print(#t2); -- 4 but documentations says this is not a sequence?

有人能解释一下规则吗？

Answer 1

引用 Lua 5.2 引用手册:

the length of a table t is only defined if the table is a sequence, that is, the set of its positive numeric keys is equal to {1..n} for some integer n

非序列上的 # 运算符的结果是未定义的。
但是 what happens in C implementation of Lua when we call # on a non-sequence 呢？

背景:Lua 中的表在内部分为数组部分和哈希部分。那是一种优化。 Lua 试图避免经常分配内存，所以它预先分配了 2 的下一个幂。这是另一个优化。

当数组部分的最后一项是 nil 时，# 的结果是对数组部分进行binsearch找到第一个nil-followed key的最短有效序列的长度。

当数组部分最后一项不是nil且哈希部分为空时，#的结果就是数组部分的物理长度。

当数组部分的最后一项不是 nil 并且散列部分不为空时，# 的结果是通过 binsearch 散列部分找到的最短有效序列的长度，以查找第一个 nil-followed 键(即这样正整数 i 即 t[i] ~= nil 和 t[i+1] == nil )，假设数组部分充满了非零(!)。

所以 # 的结果几乎总是最短有效序列的(期望的)长度，除非数组部分中表示非序列的最后一个元素是非零。然后，结果比预期的要大。

这是为什么？似乎 又是另一个优化 (对于大小为 2 的数组)。此类表上 # 的复杂度为 O(1) ，而其他变体为 O(log(n)) 。