lua - Lua中元表访问时的时间复杂度

Question

local cls = {base = "base"}
local ins = {}
cls.__index = cls
setmetatable(ins, cls)

访问 ins.base 的时间复杂度是多少？

Answer 1

官方 Lua 实现的时间复杂度预计为 O(1)。

__index 的代码大致相当于此 Lua 代码，摘自手册:

 function gettable_event (table, key)
   local h
   if type(table) == "table" then
     local v = rawget(table, key)
     if v ~= nil then return v end
     h = metatable(table).__index
     if h == nil then return nil end
   else
     h = metatable(table).__index
     if h == nil then
       error(···)
     end
   end
   if type(h) == "function" then
     return (h(table, key))     -- call the handler
   else return h[key]           -- or repeat operation on it
   end
 end

__index 查找本身没有循环，并且由于 Lua 表由哈希表支持，因此表查找通常是恒定时间操作。