是什么让 Lua 表的键顺序不确定？

Question

我知道，在 Lua 中，表键不按创建顺序保存。到目前为止，我认为这是由于内部实现可能会不断重新排列树节点以提高性能。但是，我不明白为什么以下代码片段不会转储相同的结果，即使它是在独立运行中执行的（例如，lua每次运行都运行解释器）：

-- Example script
local t = {a = 1, b = 2}
for k,v in pairs(t) do
  print(k,v)
end

有时上面的代码会转储：

a   1
b   2

或者：

b   2
a   1

为什么用这么少的行（其中决定论似乎很明显），解释器会转储不同的结果？是什么让这里的键顺序随机？顺序是在表创建时还是表迭代时随机的？

谢谢你！

Answer 1

表（关联数组）用于按键查找，因此在迭代时没有明确定义的顺序。 Notes on the Implementing of Lua 5.3 很好地概述了Lua如何实现表数据结构。即哈希表。如果对手可以触发（键）冲突，则哈希表的插入性能将从每次操作的 O(1) 变为 O(n)，如果执行 n 次操作，您将获得 O(n^2) 行为。因此，最好使用对手无法预测行为的哈希函数。一种方法是使用随机种子作为哈希函数的一部分：

lstate.h: typedef struct global_State {
...
lstate.h: unsigned int seed;  /* randomized seed for hashes */