时间戳

首页 > 解决方案 > 是什么让 Lua 表的键顺序不确定？

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

问题描述

我知道，在 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

这么少的行（其中确定性似乎很明显），解释器怎么可能转储不同的结果？是什么让这里的键顺序随机？在表的创建或表的迭代中顺序是随机的吗？

谢谢！

标签： lualua-table

解决方案

表（关联数组）用于按键查找，因此在迭代时没有明确定义的顺序。 关于 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 */

推荐阅读