What makes Lua tables key order be undeterministic?

user_1570711 0
Viewed 185

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

or:

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?

Thank you!

lua-table lua
1 Answers

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 */
Allan_Wind_97060
Related