Lua表在内存中是如何处理的？

Question

lua如何处理表格的增长？

它是否等同于Java中的ArrayList？即需要连续的内存空间，当其大小超过已分配的空间时，内部数组将被复制到另一个内存空间。

有没有聪明的方法来处理这个问题？

我的问题是，表格如何存储在内存中？我不是在问如何在Lua中实现数组。

- Johnny Willer

---

我们在Lua中通过使用整数索引表来实现数组。因此，数组没有固定的大小，而是随着我们的需要而增长。 - Robert Harvey

@RobertHarvey，我已经编辑了我的问题，我的疑惑是Lua如何处理这种“内存视觉”。 - Johnny Willer

"数组"是一个“底层”的术语。Lua表是一组键值对，其中键和值都不能为nil。如果一个表具有连续的正整数键且从1开始，则称该表具有“序列”。长度运算符#仅适用于序列（或“空序列”），ipairs在第一个缺失的正整数键之前结束。从而得到了实现的可能性。 - Tom Blodget

Answer 1

（假设您是指Lua的最新版本；描述5.3的行为应该与5.0-5.2几乎相同。）表在底层包含一个数组部分和一个哈希部分。两者（独立地）以2的幂次方步长增长和缩小，如果不需要，两者都可以不存在。大多数键值对将存储在哈希部分中。然而，所有正整数键（从1开始）都可能被存储在数组部分中。数组部分仅存储值，并且不存储键（因为它们等同于元素在数组中的位置）。允许最多一半的分配空间为空（即包含nil作为空隙或作为空闲插槽）。 （会导致太多空插槽的数组候选项将放入哈希部分。如果数组部分已满但哈希部分有剩余空间，任何条目都将直接进入哈希部分。）对于数组和哈希部分，插入操作可能会触发调整大小，要么增加到下一个更大的2的幂次方，要么向下调整到任何更小的2的幂次方，如果之前已经删除了足够多的条目。（实际上触发向下调整大小是非常困难的：rehash是调整表大小的唯一地方（两个部分同时调整大小），并且仅在luaH_newkey中从if调用（如果两个部分都没有足够的空间）。）要了解更多信息，可以查看Lua 5.0实现的第4章，或检查源代码：基本上所有相关内容都发生在ltable.c中，有趣的阅读起点是rehash（在ltable.c中）（调整大小函数），以及主解释器循环luaV_execute（在lvm.c中）或更具体地说luaV_settable（也在那里）（在表中存储键值对时发生了什么）。

¹_{举个例子，如果要缩小一个包含大型数组部分和没有哈希的表格，你需要清除所有数组条目，然后添加哈希部分的一个条目（即使用非整数键，该值可以是任何东西，包括nil），以得到一个不包含数组部分和一个元素哈希部分的表格。
如果两个部分都包含条目，则必须首先清除哈希部分，然后添加足够的条目到数组部分以填充数组和哈希的组合（以触发调整大小，这将使您拥有一个大型数组部分和没有哈希的表格），然后像上面一样清除数组。²（先清除数组再清除哈希是行不通的，因为在清除两个部分之后，您将没有数组和一个巨大的哈希部分，并且您无法触发调整大小，因为任何条目都只会进入哈希。）}

²_{实际上，更简单的方法是放弃原表格并新建一个表格。要确保表格被缩小，您需要知道实际分配的容量（它并不是当前条目数量，并且Lua不会直接告诉您），然后正确地获取所有步骤和所有大小 - 如果步骤的顺序错了或无法触发调整大小，则会得到一个巨大的表格，甚至可能在将其用作数组时性能更慢...（存储在哈希中的数组候选项也会存储它们的键，因此实际有用数据的数量是缓存行的一半。）}

- nobody

---

我相信只有插入操作才能触发重新调整大小。这就是为什么在迭代过程中使用next()清除现有字段是允许的，但如果添加字段，则未定义。 - siffiejoe

首先，感谢您的帮助，但很抱歉，我对C语言一窍不通。我已经阅读了Itable.c文件，但是有些地方我还是不太明白：如果键哈希冲突会发生什么？如果哈希部分增长（或缩小），它是否会被复制到内存的另一个部分（以保持连续分配）？我找不到关于这个问题的详细解释。 - Johnny Willer

@JohnnyWiller：哈希算法在实现论文的第4章中有简要介绍（请参见该章节的第8页，最后一段），更多信息可以在引用的论文中找到。至于调整大小：你有阅读实现论文吗？它在那里描述了（第7页，第2段）- 是复制，是连续的。 - nobody

@siffiejoe 对，完全忽略了那部分的思考 - 感谢您的注意！现在应该已经修复了，在更多阅读和测试之后，我相信我现在所描述的就是真正发生的事情。 - nobody

Answer 2

自从Lua 5.0版以来，表格是哈希表和数组的混合体。来自Lua 5.0实现：

优化用作数组的表的新算法：

与其他脚本语言不同， Lua不提供数组类型。相反，Lua程序员使用带整数索引的常规表来实现数组。Lua 5.0使用一种新的 算法，检测表是否被用作数组并自动将与数字索引相关联的值存储在实际数组中， 而不是将它们添加到哈希表中。这个算法在第4节中讨论。

早期版本只有哈希表。

- Diego

---

@JohnnyWiller 你问什么？GC会扫描表的数组部分和哈希部分。 - Colonel Thirty Two

@ColonelThirtyTwo 是的，我知道。我在问的是，如果表哈希部分增长，它是否会被复制到内存的另一部分，以保持连续分配（就像Java一样）？ - Johnny Willer

@JohnnyWiller：在计算新尺寸之后，Lua会创建新的部分并将旧部分中的元素重新插入到新部分中。因此，在扩展后它们应该仍然是连续的。请阅读我提供的链接文件的第4节，他们可以比我更好地解释这个问题 :-) - Diego