Re: Why are tables constructed randomly?

[Coda Highland <chighland@...>]

On Thu, Oct 24, 2013 at 12:16 AM, Luther <lutheroto@gmail.com> wrote:
> Consider the following program (in Lua 5.2.2):
>
> -------------------------------------------------------------------------
> local data = {
>   Troll = 25,
>   Doppelganger = 25,
>   ['Dragon man'] = 25,
>   Draven = 25,
>   Dwarf = 50,
>   Elf = 44,
>   ['Death elf'] = 11,
>   ['Seelie fey'] = 30,
>   ['Unseelie fey'] = 30,
>   Orc = 30,
>   Gnome = 30,
>   Goblin = 30,
>   Human = 55,
>   ['Lizard man'] = 20,
>   Ogre = 20,
>   Gargoyle = 15,
>   Seraphim = 15,
>   Daemourn = 15,
>   halfBreed = 5
> }
>
> -- Run the pairs loop twice to show that the order of keys is identical.
> for _ = 1, 2 do
>   print()
>   for race in pairs(data) do
>     print(race)
>   end
> end
> -------------------------------------------------------------------------
>
> The loop shows two identical sequences of keys. However, in different
> runs of the program, the order of keys changes, as if the order is
> completely random. I know Lua doesn't give any guarantees about the
> order of keys, but I can't think of any reason why the hash table would
> be constructed differently on each run. Can anyone tell me what's going
> on here?
>
> (I know C, so you can point me to the relevant source code if you think
> it will help me understand.)
>
> Luther
>
>

Because Lua's tables are hash tables. They're an unordered collection
-- they're organized according to an internal hash code for
performance, and that hashing function has some randomization involved
to help avoid pathological worst cases or maliciously-constructed
attacks.

I don't know the Lua internals well enough to point you at the code,
but hash tables are fairly common so if you want to know more about
the general concept you should have no trouble looking it up.

/s/ Adam