关联数组查找成本

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。一个体面散列函数（一个给定的）的体面散列表需要预期的恒定时间，尽管在最不可能的情况下它可能需要线性时间。你的第二个功能就是利用这个功能，第一个功能不会 - 它总是需要时间线性表的大小。

如The Implementation of Lua 5.0（其中您还可以找到关于散列表的一些细节）中所述，对用作数组的表（连续整数键）进行优化。如果本文中的信息是准确的，并且我正确解释，则此优化也应由第二个表格触发（使用1..5中的5个索引中的3个）。所以它很可能只是将五个值存储在一个C数组中，并对该数组进行有保证的常量时间索引。

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

Answer 2

第二个肯定比较快。 Lua使用基于散列的表格实现，这意味着在大多数情况下直接读取将是次线性的，甚至是O(1)。第一个是Ω(n)。