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 关于 的指教。

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180201G04SEZ00?refer=cp_1026

同媒体快讯

相关快讯

扫码关注云+社区