Lua Table Gap避免

Question

当我使用不同的语法时，为什么lua表（rehashes？）避免间隙？

inspect function

d = require "core/modules/inspect"

案例1：标准语法第1个元素是间隙

t = {1,2,3}
t[1] = nil
d(t)
__________
{ nil, 2, 3 }

Case2：用括号语法没有间隙

 t = {
    [1] = 1,
    [2] = 2,
    [3] = 3,
}
t[2] = nil
d(t)
__________
{ 1,
  [3] = 3
}

案例3：动态阵列 - 没有差距

t = {}
t[1] = 1
t[2] = 2
t[3] = 3
t[2] = nil
d(t)
__________
{ 1,
  [3] = 3
}

Case4：在第一个元素中设置为nil时的动态数组 - 是一个间隙

t = {}
t[1] = 1
t[2] = 2
t[3] = 3
t[1] = nil
d(t)
__________
{ nil, 2, 3 }

Case5：用括号语法在第一个元素中设置nil仍然没有间隙

t = {
    [1] = 1,
    [2] = 2,
    [3] = 3,
}
t[1] = nil
d(t)
__________
{
  [2] = 2,
  [3] = 3
}

Answer 1

Lua没有为非顺序索引定义长度运算符的行为，但Why does Lua's length (#) operator return unexpected values?的接受答案进入了Lua 5.2的标准实现中实际发生的情况。也就是说，这个答案本身并不能完全解释这种行为，所以这里是一个案例解释，使用Lua 5.3.5的标准实现。

注意：我使用长度运算符来清楚地显示出现孔的情况。关于它如何应用于您使用的检查功能，从我可以看到的行为，它只是明确地陈述范围1 <= index <= #table之外的任何索引。

情况1：

> t = {1,2,3}
> t[1] = nil
> print(#t)
3

Lua表的数组部分的大小基于2的幂 - 除非使用预设值构造表。行t = {1,2,3}创建一个包含大小为3的数组部分的表。当你执行t[1] = nil时，数组部分没有理由重新调整大小，因此它的大小保持为3.由于数组部分中的最后一项是非零的，并且散列部分为空，返回数组大小-3。

案例2：

> t = {[1] = 1, [2] = 2, [3] = 3}
> t[2] = nil
> print(#t)
1

如果要在表构造函数中定义表值，Lua会将方括号内的任何键与表的哈希部分相关联。因此，表的数组部分实际上是空的。该实现对数组的哈希部分执行二进制搜索，得到1。

案例3：

> t = {}
> t[1] = 1
> t[2] = 2
> t[3] = 3
> t[2] = nil
> print(#t)
1

当在构造函数之外使用方括号时，Lua将检查数字索引以查看它们是否应该进入数组部分或散列部分。在这种情况下，每个索引都将进入数组部分，但由于这些值是在构造函数之外定义的，因此将根据2的幂来调整数组的大小。因此，在最初的三个赋值之后，数组部分的大小将为4. nil赋值不会触发重新大小，因此它保持为4.因此，当应用length运算符时，它会看到最终值在数组的空间中为nil，因此它在第一个nil值（即1）之前搜索索引。

案例4：

> t = {}
> t[1] = 1
> t[2] = 2
> t[3] = 3
> t[1] = nil
> print(#t)
3

这种情况与案例3完全相同，但二进制搜索看到t[2]是非零的，因此不考虑2之前任何索引处的值。这导致搜索在2之后继续搜索索引，这得出结论长度是3。

案例5：

> t = {[1] = 1, [2] = 2, [3] = 3}
> t[1] = nil
> print(#t)
0

这就像案例2一样，表项是表的哈希部分的成员。但是，在这种情况下，搜索过程结果为0.这是因为在尝试二进制搜索之前，该函数确定应搜索的整数索引范围。在第一个索引处存在nil值意味着确定范围的循环不运行。有关搜索过程如何工作的更多信息，您可以看到函数here。当我说循环没有运行时，我特别指的是while条件，!ttisnil(luaH_getint(t, j))。

奖金案例：

> t = {}
> t[1] = 1
> t[4] = 4
> print(#t)
1
> g = {}
> g[1] = 1
> g[3] = 3
> g[4] = 4
> print(#g)
4

在案例3中，我提到了Lua决定是否在数组部分或散列部分中放入数字索引的事实。在上面的表t的组成中，索引1在数组部分中，而在散列部分中是4。因此，返回的长度为1.在g的情况下，所有值都放入数组部分。这是因为在为索引分配值时，Lua尝试以最佳方式重新调整数组部分的大小。为了更好地理解这个重新调整大小的过程，您可以查看源here。