关联数组查找开销

Question

考虑两个查找函数：

simple={1,3,5}
function isX(id) 
 for _,v in ipairs(simple) do 
  if v==id then return true end 
 end 
 return false 
end

assoc={[1]=true,[3]=true,[5]=true}
function isX2(id) 
 return assoc[id] or false 
end

哪个函数的查找成本更低？或者他们是平等的？Lua如何在内部存储关联数组？

Answer 1

本质上，所有表都是哈希表，第一个表只是隐式使用整数键1..n。一个写得不错的哈希表和不错的哈希函数（都是给定的）需要预期的恒定时间，尽管在非常不可能的最坏情况下，它可能需要线性时间。您的第二个函数利用了这一点，而第一个函数则没有——它总是以表的大小为线性来花费时间。

如Lua 5.0的实现中所述，对用作数组（连续整数键）的表进行了优化（您还可以在其中找到有关哈希表的一些细节）。如果本文中的信息是准确的，并且我对其解释正确，那么您的第二个表也应该触发此优化（使用了1..5中5个索引中的3个）。因此，它很可能只在一个C数组中存储五个值，并保证对该数组进行恒定时间索引。

无论哪种方式，你都可以用你的房子打赌，第二个速度会逐渐加快。也就是说，随着元素数量接近无穷大，它将变得比线性扫描更快。在实践中，你不需要去任何接近无限的地方（我的直觉是，几十个就足够了，可能更少）就能看到显著的差异。

Answer 2

第二个肯定更快。Lua使用基于哈希的表实现，这意味着在大多数情况下直接读取将是次线性的，甚至是O(1)。

第一个是Ω(n)。