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

思考一下：如果现在定义了一个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的结果。

0.Lua调试工具——LuaEditor

首先，如果你是第一次接触Lua，请补充一下Lua的最基本之中的基础语法，然后下载一个LuaEditor工具，用来查看Lua执行效果，当然也可以调试，本篇内容不解释这个工具。可以百度一下这个工具。

1.什么是table？

table是Lua最复杂最强大的数据结构，Lua本身并不是面向对象语言，但是对面向对象中态耐乎毒比较深的程序员，可以借助table”完美”地模拟面向对象编程。最简帆悉单地，我们可以把table理解为数组，最复杂的，我们可以把table理解为”世间万物”，因为它可以创造出很多你想象不到的东西。一个字，自由度非常大~！

2.如何创建一个table？

创建table是一件很复杂的事情，不知道大家顶不顶得住，试试看，如下：

复制代码 代码如下:

local a = {}

这样就创建了一个table了。

3.如何初始化一个table

嗷，虽然创建table已经很复杂了，更复杂的还在后面，怎么初始化table？看看下面的代码：

复制代码 代码如下:

local a = {["x"] = 12, ["mutou"] = 99, [3] = "hello"}

print(a["x"])

在LuaEditor中创建一个lua文件，输入以上代码，保存，然后按F5运行，我们将看到输出窗口输出了一个数字：12。

这挺神奇的，感觉就像是在定亩改义数组，不是吗？

table间的元素用逗号分隔，["x"] = 12代表构造一个table元素，下标为”x”，值为12。（小若：为毛数组下标可以是字符串？）

嗷~！我就等旁白问这个问题，旁白你笨蛋啊，我只是说table像数组，我没有说它就是数组，table支持几乎是所有类型的下标，包括函数。

---