是什么使Lua表的键顺序不确定? [英] What makes Lua tables key order be undeterministic?

问题描述

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

I know that, in Lua, table keys are not preserved in order of creation. So far I thought it'd be due to the internal implementation which might continuosly rearrange the tree nodes in order to improve performance. However, I don't understand why the following snippet doesn't dump the same result even if it's executed in independent runs (e.g. running lua interpreter for each run):

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

有时上面的代码会转储:

Sometimes the code above dumps either:

a   1
b   2

或:

b   2
a   1

在这么少的行(确定性似乎很明显)的情况下，解释器如何可能转储不同的结果?是什么使密钥顺序在这里随机?在创建表时或在表迭代时顺序是随机的吗?

How is it possible that, with so few lines (in which determinism seems obvious), the interpreter dumps different results? What makes keys order random here? Is the order random at table's creation or at table's iteration?

谢谢！

推荐答案

表(关联数组)用于按键查找，因此在对其进行迭代时没有明确定义的顺序.关于Lua 5.3实施的说明很好地概述了Lua如何实现表数据结构.IE.哈希表.如果对手可以触发(键)冲突，则哈希表的每次操作从O(1)插入性能变为O(n)，如果执行n次操作，则行为为O(n ^ 2).因此，可取的是使用攻击者无法预测的行为的散列函数.一种方法是使用随机种子作为哈希函数的一部分:

A table (associative array) is used for lookup by key and as such does not have well-defined order when iterating through it. Notes on the Implementation of Lua 5.3 is a good overview of how Lua implements the table data structure. I.e. hash table. If an adversary can trigger a (key) collision the hash table goes from O(1) insert performance to O(n) per operation, and for if you do that n operations you get O(n^2) behavior. Therefor, it's desirable to use a hash function which behavior an adversary cannot predict. One way to do that is using a randomized seed as part of the hash function:

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

这篇关于是什么使Lua表的键顺序不确定?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！