作者：糊涂小蜗牛
链接：https://www.jianshu.com/p/42d7d0b82708
来源：简书

lua表分为数组和散列表部分，数组部分从 1 开始作为第一个索引，散列表部分要求键值不能为 nil。因为表包括散列表和数组两部分数据，所以一个以正整数作为键值的数据写入lua表时不确定是写入了数组还是散列表中。接下来讨论这部分的操作原理。
虽然正整数作为键值的数据写入lua表时不确定是写入了数组还是散列表中，但 0 和 负数做 key 时是肯定放在散列表中。

查找

如果输入的 key 是一个正整数，并且它的值 > 0 && <= 数组大小
    尝试在数组部分查找
否则尝试在散列表部分查找：
    计算出该 key 的散列值，根据此散列值访问 Node 数组得到散列值所在的位置
    遍历该散列桶下的所有键表元素，直到找到该 key 为止

可以看到，即使是一个正整数的key，其存储部分也不见得会一定落在数组部分，这完全取决于它的大小是否落在了当前数组可容纳的空间范围内。

新增

添加新元素的流程比较复杂，因为涉及重新分配表中数组和散列表部分的流程。

散列表部分的数据组织是，首先计算数据的key所在的桶数组位置，这个位置称为 mainposition。相同mainposition的数据以链表形式组织。当找不到对应的key时，则会调用内部的newkey函数分配一个新的key来返回：

    (ltable.c)
    /*
    ** inserts a new key into a hash table; first, check whether key's main
    ** position is free. If not, check whether colliding node is in its main
    ** position or not: if it is not, move colliding node to an empty place and
    ** put new key in its main position; otherwise (colliding node is in its main
    ** position), new key goes to an empty position.
    */
    TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
      Node *mp;
      TValue aux;
      if (ttisnil(key)) luaG_runerror(L, "table index is nil");
      else if (ttisfloat(key)) {
        lua_Integer k;
        if (luaV_tointeger(key, &k, 0)) {  /* does index fit in an integer? */
          setivalue(&aux, k);
          key = &aux;  /* insert it as an integer */
        }
        else if (luai_numisnan(fltvalue(key)))
          luaG_runerror(L, "table index is NaN");
      }
      mp = mainposition(t, key);
      if (!ttisnil(gval(mp)) || isdummy(t)) {  /* main position is taken? */
        Node *othern;
        Node *f = getfreepos(t);  /* get a free place */
        if (f == NULL) {  /* cannot find a free place? */
          rehash(L, t, key);  /* grow table */
          /* whatever called 'newkey' takes care of TM cache */
          return luaH_set(L, t, key);  /* insert key into grown table */
        }
        lua_assert(!isdummy(t));
        othern = mainposition(t, gkey(mp));
        if (othern != mp) {  /* is colliding node out of its main position? */
          /* yes; move colliding node into free position */
          while (othern + gnext(othern) != mp)  /* find previous */
            othern += gnext(othern);
          gnext(othern) = cast_int(f - othern);  /* rechain to point to 'f' */
          *f = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
          if (gnext(mp) != 0) {
            gnext(f) += cast_int(mp - f);  /* correct 'next' */
            gnext(mp) = 0;  /* now 'mp' is free */
          }
          setnilvalue(gval(mp));
        }
        else {  /* colliding node is in its own main position */
          /* new node will go into free position */
          if (gnext(mp) != 0)
            gnext(f) = cast_int((mp + gnext(mp)) - f);  /* chain new position */
          else lua_assert(gnext(f) == 0);
          gnext(mp) = cast_int(f - mp);
          mp = f;
        }
      }
      setnodekey(L, &mp->i_key, key);
      luaC_barrierback(L, t, key);
      lua_assert(ttisnil(gval(mp)));
      return gval(mp);
    }

这个函数的操作流程如下
1、如果该mainposition上已经有其他数据或者第一次插入情况：
（1）首先获得lastfree指向的空间，若找不到空闲位置放置新键值，则调用rehash函数，增加或减少哈希表的大小，重新插入元素。
（2）若该mp被占了，检查占领该位置的node的mp是不是在这个地方，若不在这个地方，则移动该node到一个新的位置，并且把要插入的元素插入到相应的位置；若在这个地方（即占领该位置的node的mp就是要插入的位置），则把要插入的元素插入到一个新的空node中。
2、如果该mp为空，则直接把相应的元素插入到这个node中。

以上操作涉及重新对表空间进行分配的情况。这一部分比较复杂，入口函数是rehash，顾名思义，这个函数的作用就是为了做重新散列操作：

    /*
    ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
    */
    static void rehash (lua_State *L, Table *t, const TValue *ek) {
      unsigned int asize;  /* optimal size for array part */
      unsigned int na;  /* number of keys in the array part */
      unsigned int nums[MAXABITS + 1];
      int i;
      int totaluse;
      for (i = 0; i <= MAXABITS; i++) nums[i] = 0;  /* reset counts */
      na = numusearray(t, nums);  /* count keys in array part */
      totaluse = na;  /* all those keys are integer keys */
      totaluse += numusehash(t, nums, &na);  /* count keys in hash part */
      /* count extra key */
      na += countint(ek, nums);
      totaluse++;
      /* compute new size for array part */
      asize = computesizes(nums, &na);
      /* resize the table to new computed sizes */
      luaH_resize(L, t, asize, totaluse - na);
    }

它的主要操作如下所示。
(1) 分配一个位图nums，将其中的所有位置0。这个位图的意义在于：nums数组中第i个元素存放的是 key 在 2^(i-1) 和 2^i 之间的元素数量。
(2) 遍历Lua表中的数组部分，计算其中的元素数量，更新对应的nums数组中的元素数量（numusearray函数）。
(3) 遍历lua表中的散列桶部分，因为其中也可能存放了正整数，需要根据这里的正整数数量更新对应的nums数组元素数量（numusehash函数）。
(4) 此时nums数组已经有了当前这个Table中所有正整数的分配统计，逐个遍历nums数组，获得其范围区间内所包含的整数数量大于50%的最大索引，作为重新散列之后的数组大小，超过这个范围的正整数，就分配到散列桶部分了（computesizes函数） 。
(5) 根据上面计算得到的调整后的数组和散列桶大小调整表（resize函数）。

Lua的设计思想是，简单高效，并且还要尽量节省内存资源。
在重新散列的过程中，除了增大Lua表的大小以容纳新的数据之外，还希望能借此机会对原有的数组和散列桶部分进行调整，让两部分都尽可能发挥其存储的最高容纳效率。那么，这里的标准是什么呢？希望在调整过后，数组在每一个2次方位置容纳的元素数量都超过该范围的50%。能达到这个目标的话，我们就认为这个数组范围发挥了最大的效率。
设想一个场景来模拟前面的算法流程。假设现在有一个Lua表，经过一些变化之后，它的数组有以下key的元素：1, 2, 3, 20。首先，算法将计算这些key被分配到了哪些区间。
在这个算法里，我们使用数组来保存落在每个范围内的数据数量，其中每个元素存放的是 key 在 2^(i-1) 和 2^i 之间的元素数量。
前面关于数字键值的统计跑完之后，得到的结果是:

    nums[0] = 1（1落在此区间）
    nums[1] = 1（2落在此区间）
    nums[2] = 1（3落在此区间）
    nums[3] = 0
    nums[4] = 0
    nums[5] = 1（20落在此区间）
    nums[6] = 0
    ...
    nums[n] = 0（其中n > 5 且 n <= MAXBITS）

计算完毕后，我们得到了这个数组每个元素的数据，也就是得到了落在每个范围内的数据数量。接着，我们来计算怎样才能最大限度地使用这部分空间。这个算法由函数computesizes实现：

    /*
    ** Compute the optimal size for the array part of table 't'. 'nums' is a
    ** "count array" where 'nums[i]' is the number of integers in the table
    ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
    ** integer keys in the table and leaves with the number of keys that
    ** will go to the array part; return the optimal size.
    */
    static unsigned int computesizes (unsigned int nums[], unsigned int *pna) {
      int i;
      unsigned int twotoi;  /* 2^i (candidate for optimal size) */
      unsigned int a = 0;  /* number of elements smaller than 2^i */
      unsigned int na = 0;  /* number of elements to go to array part */
      unsigned int optimal = 0;  /* optimal size for array part */
      /* loop while keys can fill more than half of total size */
      for (i = 0, twotoi = 1;
           twotoi > 0 && *pna > twotoi / 2;
           i++, twotoi *= 2) {
        if (nums[i] > 0) {
          a += nums[i];
          if (a > twotoi/2) {  /* more than half elements present? */
            optimal = twotoi;  /* optimal size (till now) */
            na = a;  /* all elements up to 'optimal' will go to array part */
          }
        }
      }
      lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal);
      *pna = na;
      return optimal;
    }

这个函数的输入参数nums是前面已经计算好的计数数组。pna 存放的是前面计算得到的数字键值的数量，这是一个指针，说明会在这个函数中被修改，最后作为重新散列操作时数组部分的大小。这个函数的原理就是循环遍历数字键值部分，找到满足前面提到的条件的最大值：该范围内的数据满足大于50%的值。结合前面的测试数据来“试运行”一下这个函数。此时传入的 pna 参数是 4，也就是目前数组部分的数据数量。

    首先，初始值，twotoi为1，i为0，a在循环初始时为0，它表示的是循环到目前为止数据小于2^i的数据数量。
    i = 0，twotoi = 1，满足（twotoi > 0 && *pna > twotoi / 2），nums[i] = 1 > 0成立，a += nums[i], a = 1，满足a > twotoi/2，也就是满足这个范围内数组利用率大于50%的原则，此时记录下这个范围，也就是 optimal = twotoi = 1，到目前为止的数据数量 na = a = 1

    i = 1，twotoi = 2，满足（twotoi > 0 && *pna > twotoi / 2），nums[i] = 1 > 0成立，a += nums[i], a = 2，满足a > twotoi/2，记录下这个范围，也就是 optimal = twotoi = 2，到目前为止的数据数量 na = a = 2

    i = 2，twotoi = 4，满足（twotoi > 0 && *pna > twotoi / 2），nums[i] = 1 > 0成立，a += nums[i], a = 3，此时满足a > twotoi/2，记录下这个范围，也就是 optimal = twotoi = 4，到目前为止的数据数量 na = a = 3

    i = 3，twotoi = 8，不满足（twotoi > 0 && *pna > twotoi / 2），结束，返回 optimal 为4。

得到数组的大小是4，也就是说key为1、2、3这三个元素落在了数组部分，而20则落在了散列桶部分。这个过程可以看出，一个整数的key在同一个表中不同的阶段可能被分配到数组或者散列桶部分，而这一点是很多人经常忽视的。

另外，从上面的分析可以看到，Lua解释器背着我们会对表进行重新散列的动作，而这个操作的代价是挺大的，如下面的代码：

    local a = {}
    for i=1,3 do
      a[i] = true
    end

在这段代码中，主要做了如下工作。
(1) 最开始，Lua创建了一个空表a。
(2) 在第一次迭代中，a[1]为true触发了一次重新散列操作，Lua将数组部分的长度设置为2^0，即1，散列表部分仍为空。
(3) 在第二次迭代中，a[2]为true再次触发了重新散列操作，将数组部分长度设为2^1，即2。
(4) 最后一次迭代又触发了一次重新散列操作，将数组部分长度设为2^2，即4。
只有三个元素的表会执行三次重新散列操作，然而有100万个元素的表仅仅只会执行20次重新散列操作而已，因为2^20 = 1048576 > 1000000。但是，如果创建了非常多的长度很小的表，这可能会造成巨大的影响。
如果你有很多很小的表需要创建，就可以预先填充以避免重新散列操作。比如：{true, true, true}，Lua知道这个表有3个元素，所以直接创建了3个元素的数组。类似地，{x=1, y=2, z=3}，Lua创建长度为3散列部分。

这里对比以下两段代码，首先看没有使用预填充技术的代码：

    a = os.clock()
    for i = 1,2000000 do
      local a = {}
      a[1] = 1; a[2] = 2; a[3] = 3
    end
    b = os.clock()
    print(b-a)

再看使用了预填充技术的代码：

    a = os.clock()
    for i = 1,2000000 do
      local a = {1,2,3}
      a[1] = 1; a[2] = 2; a[3] = 3
    end
    b = os.clock()
    print(b-a)

测试得到，使用了预填充技术的代码比没有使用这个优化的代码的速度提高了多倍。所以，当需要创建非常多的小表时，应预先填充好表的大小，减少解释器被动地进行重新散列操作的过程。