Joh*_*ler 5 arrays lua memory-management lua-table
lua如何处理表的增长？
它等同ArrayList于Java吗？即需要连续内存空间,并且随着它比已经分配的空间增大,内部数组被复制到另一个内存空间.
是否有一种聪明的方式来领导它？
我的问题是,如何将表存储在内存中？我不是在问Lua如何实现数组.
(假设你指的是Lua的最新版本;描述5.3的行为(对于5.0-5.2应该是(几乎？)相同.)
在引擎盖下,表包含一个数组和一个哈希部分.两者(独立地)以两个幂的步长增长和缩小,并且如果不需要则两者都可以不存在.
大多数键值对将存储在散列部分中.但是,所有正整数键(从1开始)都是存储在数组部分中的候选.数组部分仅存储值而不存储键(因为它们等同于元素在数组中的位置).允许最多一半的已分配空间为空(即包含nils - 作为间隙或尾随空闲槽).(将留下太多空插槽的数组候选者将被放入散列部分.如果数组部分已满但散列部分中有剩余空间,则任何条目都将转到散列部分.)
对于阵列和散列部分,插入可以触发调整大小,如果先前已经移除了足够多的条目,则可以触发下一个更大的2的幂或者更小的2的任何更小的幂.(实际上触发向下调整大小是不平凡:rehash在其中表的大小(与两个部分同时调整)的唯一地方,而且只从被称为如果在任一没有足够的空间两部分1.)luaH_newkey
有关更多信息,您可以查看Lua 5.0实现的第4章,或检查源:基本上所有相关内容都发生在ltable.c,有趣的读取起点是rehash(in ltable.c)(调整大小函数)和主解释器循环luaV_execute( in lvm.c)或更具体地luaV_settable(也在那里)(当在表中存储键值对时会发生什么).
1 例如,为了缩小包含大型数组部分且没有散列的表,您必须清除所有数组条目,然后向散列部分添加一个条目(即使用非整数键,值可能是任何包括 nil),最终得到一个不包含数组部分和1元素哈希部分的表.
如果两个部分都包含条目,则必须首先清除哈希部分,然后向数组部分添加足够的条目以填充数组和哈希组合(以触发调整大小,这将留下一个包含大数组部分的表,没有哈希),然后清除上面的数组.2(首先清除数组,然后散列不起作用,因为在清除了两个部分之后,你将没有数组和一个巨大的散列部分,并且你不能触发调整大小,因为任何条目都只会转到散列.)
2 实际上,扔掉桌子并制作新桌子要容易得多.为了确保一个表缩小,你需要知道实际分配的容量(这不是当前的条目数,Lua不会告诉你,至少不是直接告诉你),然后得到所有的步骤和所有大小恰到好处 - 混合步骤的顺序或无法触发调整大小,你最终得到一个巨大的表,如果你把它作为一个数组使用它甚至可能会执行得更慢...(数组候选存储在hash还存储它们的密钥,例如缓存行中有用数据量的一半.)