Question

由浅入深的理解Lua的数据结构——table

Answer 1

思考一下：如果现在定义了一个table a，将table a赋值给table b，此时它们的内存情况是什么样呢？
ab都会指向同一个内存块，如果a设置为nil，b依旧能访问该内存块的元素，直到b设置为nil后，Lua的垃圾回收机制会清理相应的内存。所以当b在更改table内的值后，a再去访问的时候，值也是改变的。

table的for循环写法

先解释一下上面的各个变量

在table中，我们无法对两个table之间进行操作，比如：table a+ table b。为了解决这个问题，就引入了元表的概念，它允许我们 改变table的行为 。

当我们在进行表a+b的时候：

其实逼逼了这么多，我觉得元表和元方法其实就相当于 重载 ，比如_add，我们就是重载了+操作符
也可以将它理解成 事件驱动 ，元表中的键对应着不同的事件名，关联的值是元方法，元方法里就是我们事件对应的操作。

继续接上面的分析

每个Node都是一个键值对 ,里面包含了key和value。tvk是key的值，但是当我们出现hash冲突，此时lua的hash算法比较特殊，一般情况下，我们的hash算法都是根据key算出hash，然后如果有冲突的话，就放在改位置的链表上。而lua不同， 当它出现hash冲突的时候，会在hash表中找到一个空的位置x，来存放key，并且让冲突处的节点的nk.next指向x 。
这意味着什么呢？发生冲突我们无需重新分配空间来存储冲突的key，而是利用hash表上未用过的空白处来存储。刚才我们将key放在了空位置x， 如果此时存在另一个key2，它算出的hash值是空位置x，而我们刚才的key只是因为hash冲突了，占用了其他key的位置，这个时候我们就讲key2放在x上，将key再放到另一个空白处 。

忍不住想总结一波table的实现，和上面我们的Node类型进行对照

lua的table其实由 数组段 和 hash 两部分组成，当你的key值不会过于离散的时候，lua就会将它存储在数组段（也就是下图的array），反正会存储在hash段（也就是下图的node），这个分割线是以数组段的利用率不低于50%为准。hash段采用闭散列的算法，它将有冲突的key存储在空闲槽中，而不额外分配内存。

在我们table结构体中，array和sizearray都是表示数组段。
而lsizenode和node，lastfree是表示hash段。node指向hash表的起始位置，lsizenode是log2(node指向的哈希表的节点数目)， lastfree指向node里面最后一个未使用的节点 （因为我们在hash冲突的时候，是从后往前查找未使用的节点，lastfree存储最后一个未使用节点就可以方便查找）

如果此时hash表中已经没有空格了，那么lua就会resize这个hash表（等会再谈lua的动态扩增）

lua创建新表的时候 先为新表分配内存 Table * t = luaM_new(L, Table)，然后将表 连接到gc 上并设置标志位luaC_link(L, obj2gco(t), LUA_TTABLE)，然后 初始化 一些必要的属性，使用setarrayvector为数组段分配内存，setnodevector为hash部分分配内存，最后返回表指针。

table的查找会根据key进行判断，如果key为空就直接返回空，key为字符串就调用luaH_getstr(t, rawtsvalue(key))，key为数字则根据它是否整数调用luaH_getnum(t, k)，否则，计算出key的位置，遍历table的node节点，找到对应键所在的节点返回。

因为key为数字比较特殊，所以研究一把luaH_getnum函数的实现

如果key大于等于1，小于数组的长度，则从数组中取出对应的键值，否则利用hashnum找到key对应的node位置，遍历node链表，返回对应的值

dummynode是带头结点的指针。
往table中插入新值，先检测 key的主位置 （main position）是否为空，主位置就是key的哈希值在node中的位置。
如果主位置为空，就直接插入，主位置不为空，检查占领该位置的key的主位置是不是在这个地方，如果不在，则将该key移动到其他空闲位置，将要插入的key插入到这个位置中。如果在这个地方，则将要插入的key插入到一个 空槽 中。
如果找不到空闲位置放新键值，就 rehash函数 ，扩增hash表的大小，再找出新位置，再调用luaH_set把要插入的key插入到新的哈希表中，直接返回LuaH_set的结果。