Associative array lookup cost

Question

Consider two lookup functions:

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

Which function has lower lookup cost? Or are they equal? How does Lua store associative arrays internally?

Answer 1

In essence, all tables are hash tables and your first table just implicitly uses the integer keys 1..n. A decently-written hash table with decent hash functions (both a given) takes expected-constant time, though in the very unlikely worst case it can take linear time. Your second function makes use of that, the first does not - it always takes time linear in the size of the table.

There's an optimization for tables used as arrays (consecutive integer keys) as described in The Implementation of Lua 5.0 (where you'll also find a few details about the hash table). If the information in this paper is accurate, and I interpret it correctly, this optimization should be triggered by your second table too (3 out of the 5 indices in 1..5 used). So it's quite likely it will just store five values in a C array and do guaranteed-constant-time indexing of this array.

Either way, you can bet your house that the second is asymptotically faster. That is, as the number of elements approaches infinity, it will become faster than the linear scan. In practice, you need not go anywhere close to infinite (my gut feeling is that a few dozen will suffice, possibly less) to see a significant difference.

Answer 2

The second is certainly faster. Lua uses hash-based implementation of tables, which means direct reads in most cases will be sublinear or even O(1).

The first one is Ω(n).