pairs 的遍历顺序

在 Lua 中，我们经常使用 来遍历一个 "hashmap"，但是你有没有想过， 遍历的顺序到底依据的是啥？

为了搞清楚这个问题，这里先来做个测试：

注：以下测试结果均基于 Lua 5.1.4

case 1

在一个 Lua 实例中执行上面的用例，发现两次循环得到的结果是一样的。因此可以得出结论：在遍历的过程中，并不是随机的。

在 golang 中，map 每次遍历顺序都是不一致的。是因为 go 的底层实现并不保证这一点。因此，go 索性对 key 次序做随机化，以提醒大家不要依赖 遍历返回的 key 次序。

case 2

接着在另外一个 Lua 实例中执行上面的用例，可以看到输出和 case 1 的结果相同。这可以说明：的遍历，也不会和 VM 有关联。

Lua 5.3 中，为了解决 String Hash Dos 问题，使用了一个随机种子用于字符串哈希值的计算，这个种子是放在全局表中的，会导致相同的字符串在不同的 Lua VM 中，总是有不同的 hash，因此遍历的顺序也是不同的。

根据上面的两个测试，我们知道在 Lua 中 的遍历不是随机的。其实 内部依赖于 来做表遍历， 则是根据 key 的 hash 值来按顺序遍历的。

严格来说，遍历的顺序是在 hash 之后对 tablesize 取模后的大小。

根据前面的文章，这里可以轻松的算出 key 的遍历顺序：

注意，这里的 tablesize 表示的是幂次，而不是实际大小。它是不小于 hash 区域数量的 2n形式的整数。

按照大小排列之后：

原生 Lua 5.1.4 中 的结果是：

可以看到遍历的顺序基本是按照 key 的 hash 值排列的的。不一致的两个是由于 hash 冲突而引起的重新定址（table 用的是闭散列算法）。

值得一提的是：lua string hash 用的开散列算法；而 table hash 使用的是闭散列算法。

最后，感谢知乎用户 @PaintDream 关于 的指教。