Lua设计里面，Table是一个特别关键的部分。它可以表示很多的数据结构，可以是Array，可以是Map，可以根据自己的需要实现栈，队列等等，使用起来方便。源码里面的设计显得特别重要了，它是被很频繁地使用，提高性能是设计者重中之中。

首先先看一下Lua的总体设计：它分为两部分，分别是数组Array和Hash部分。数组部分主要是存储下标从1开始的连续不为空的节点内容，如果是中间断开部分会存到hash部分。Hash部分是存储各种类型的离散数据。如下图

1.对于一个Table初始化的时候，如果是空表，即Array和Hash部分长度都为0；下面着重看Hash部分
    lua代码： local tb = {};
    c代码: lua_newtable(L);
    t->lsize = 0;
    t->lsizenode = 0; //指数，用来计算2的指数，结果为当前内存分配node数量(包括空的或使用的)
    t->node = dummynode; //内存的头，在分配内存时，分配了一个数量为lsizenode连续的Node类型的内存块
    t->lastfree = gnode(t,0); //内存的尾部，实际为dummynode
    假设我们现在初始Hash部分长度为2，2的指数，即为4个，会生成长度为4个节点，每个节点内容都为空，next也置为空（实        际作用是作为一个相同hash值的key的链表），初始化后的结构如下：

2.现在我们要给Table赋值，例如执行：tb["k0"] = "v0"， key为"k0", value为:"v0"
(1)根据key去查找有没有已经存在的。
(2)如果有，更新一下value即可。(显然，现在是没有的)
(3)如果没有，需要newkey(hash部分最最最核心的函数), newkey过程：
a.检查需要查找的key的mainposition是否为空;(mainposition实际为根据key的hash值计算得出来一个Node)
b.如果mainposition是可用并且是空的（在t->node指向的内存空间内找到没有占用的Node）,就使用它，设置key和value。（这个时候，4个节点都为空，可以设置了）。假设它找到的位置是第3个，此时结构图为：注意，lastfree并不是在这个时候移动的。

3.现在赋值： tb["k1"] = "v1"，通过key查找mainposition的时候，回到刚上一步newkey的过程。此时假如查找"k1"的mainposition和"k0"的一样时候，这时"k1"发现自己的mainposition被占用了。既然被占用了，那我总得找个地方安放吧？好，那我去找一个空的坑填一下。怎么找？通过lastfree从后往前找，一个一个找。根据此时内存结构，应该找的到下标为2的节点，同时lastfree会停留在这里。既然"k0"占了"k1"的位置，"k1"要想办法协调了。要检查"k0"的mainposition到底是不是现在的位置。如果是的话，那就是"兄弟了"（两个key通过hash计算出来的mainposition一样），如果不是就需要让位了。如果是"兄弟"，那就将就下，但是要通过链表连接起，表明一下“兄弟”关系。把"k1"指向"k0"的下一个节点，再把“k0”的next指向“k1”，此时内存结构图为：

4.再赋值多一次(我也不想啊，一定要操作这么多次才能把情况说完)，tb["k2"] = "v2"。目前的情况是：k0是在自己的mainposition上面，k1不是在自己的mainposition（这个位置不属于k1自己的小天地）。此时，“k2”来搞事了，它计算得出来，“k1”所在的节点是"k2"的mainposition。既然不是“兄弟”，那就把属于自己的东西拿回来啊。拿归拿，先找一个freepos来谈判。通过lastfree继续向前找，找到下标为1的节点，lastfree此时停留在1的位置。好了，找到位置了，然后呢，让"k1"自己搬过去空位置去，同时让“k0”的下一个继续指向“k1”所在的位置，这样子，把"k1"的mainposition腾出来了，大家都乐得其所。此时内存结构图为：

5.再来再来，还没完。假设现在赋值， tb["k3"] = "v3"，刚好"k3"毫无差池地落入了第0个里，好了，刚好填空坑了。

6.你以为这样就完了吗？怎么可能呢。这个时候，再来一个 tb["k4"] = "v4"。噢，找不位置了，一个位置都没有了。怎么办？扩容啊，麻烦给我扩大点。扩大的规则是：根据当前lsizenode来增加，当前指数为2，2的2次方，为4。在这个基础上指数增加一级，就是lsizenode即为3了，变成2的3次，扩容后数量为8，亦即为rehash。rehash的过程是：先分配一块新的内存块，像这里的情况是分配了长度为8的节点大小内存块。此时，要把旧的迁移过来新内存块。但是，它并不是按顺序一个一个对位拷贝的，遍历每一个节点的时候，需要重新去找一次mainposition，所以分配前后的位置可能会不一样（它和Array部分不一样，Array部分是直接一对一，位置不变地拷贝的）。这个时候有rehash之后可能是（注意！这仅仅是可能，只是要表达，它的位置需要重新找）：

rehash以后，再重新去找"k4"的位置，重复第3步的逻辑。

用和源码比较一致的逻辑来复习一遍newkey的过程：
1.检查需要查找的key的mainposition是否为空;(mainposition实际为根据key的hash值计算得出来一个Node)
2.如果mainposition是可用并且是空的（在t->node指向的内存空间内找到没有占用的Node）,就使用它，设置key和value。
3.如果mainposition是被占用着或是dummynode(如果是新建的表，第一次赋值，必定是dummynode)，记这个mainposition为mp, 则需要走下面的流程
    a.在内存块里查一个空节点：从最后往前找（即是从lastfree开始往node方向找，地址大小递减）
    b.如果找不到空节点，表明：当前所有node都已经用完了，需要rehash重新分配一块大的内存，重新再跑一次set的流程。
    c.如果找到了，记这个空节点为n, 此时记录有mp(key自己应该所属的位置)，和一个空节点n。
        i.首先把mp已经把已经占有的值的key拿出来再计算一次它的mainposition,记为othern，看看othern是不是也是它自己应该占的位置
        ii.如果不是，就是原来占用的node丢到空节点n那里去，让mp占回属于自己应该占的位置。
        iii.如果是，就把mp节点放到othern单向链表里，并且是othern下一个，再把mp的下一个节点指向othern原来的下一个（简单来说就是把mp插到othern的前面去，othern这个链表的实际意义是：根据key计算出来的mp都一样，就把它做成一个链表，在hash有冲突的时候可以在这个链表里查找，提高性能）

整个Table的hash部分是最为关键核心的，需要理清楚实际的内部原理。