考虑两个查找函数：
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 如何在内部存储关联数组？
本质上，所有表都是哈希表，您的第一个表只是隐式使用整数键1..n。一个写得体面的哈希表和一个体面的散列函数（两者都是给定的）需要预期的恒定时间，尽管在极不可能的最坏情况下它可能需要线性时间。您的第二个函数利用了它，第一个函数没有 - 它总是需要与表格大小成线性关系的时间。
如Lua 5.0 的实现中所述，对用作数组（连续整数键）的表进行了优化（您还可以在其中找到有关哈希表的一些详细信息）。如果本文中的信息是准确的，并且我正确地解释了它，那么这种优化也应该由您的第二个表触发（1..5使用的 5 个索引中的 3 个）。因此，它很可能只会在一个 C 数组中存储五个值，并对该数组进行有保证的恒定时间索引。
无论哪种方式，您都可以打赌第二个会渐近更快。也就是说，随着元素的数量接近无穷大，它会变得比线性扫描更快。在实践中，你不需要去任何接近无限的地方（我的直觉是几十个就足够了，可能更少）就能看到显着的差异。
第二个当然更快。Lua 使用基于哈希的表实现，这意味着在大多数情况下直接读取将是次线性的，甚至是O(1).
第一个是Ω(n)。