lua表分為數(shù)組和散列表部分，數(shù)組部分從 1 開(kāi)始作為第一個(gè)索引，散列表部分要求鍵值不能為 nil。因?yàn)楸戆ㄉ⒘斜砗蛿?shù)組兩部分?jǐn)?shù)據(jù)，所以一個(gè)以正整數(shù)作為鍵值的數(shù)據(jù)寫(xiě)入lua表時(shí)不確定是寫(xiě)入了數(shù)組還是散列表中帚桩。接下來(lái)討論這部分的操作原理。
雖然正整數(shù)作為鍵值的數(shù)據(jù)寫(xiě)入lua表時(shí)不確定是寫(xiě)入了數(shù)組還是散列表中嘹黔，但 0 和 負(fù)數(shù)做 key 時(shí)是肯定放在散列表中账嚎。

查找

如果輸入的 key 是一個(gè)正整數(shù)莫瞬，并且它的值 > 0 && <= 數(shù)組大小
    嘗試在數(shù)組部分查找
否則嘗試在散列表部分查找：
    計(jì)算出該 key 的散列值，根據(jù)此散列值訪問(wèn) Node 數(shù)組得到散列值所在的位置
    遍歷該散列桶下的所有鍵表元素郭蕉，直到找到該 key 為止

可以看到疼邀，即使是一個(gè)正整數(shù)的key，其存儲(chǔ)部分也不見(jiàn)得會(huì)一定落在數(shù)組部分召锈，這完全取決于它的大小是否落在了當(dāng)前數(shù)組可容納的空間范圍內(nèi)旁振。

新增

添加新元素的流程比較復(fù)雜，因?yàn)樯婕爸匦路峙浔碇袛?shù)組和散列表部分的流程涨岁。

散列表部分的數(shù)據(jù)組織是拐袜，首先計(jì)算數(shù)據(jù)的key所在的桶數(shù)組位置，這個(gè)位置稱(chēng)為 mainposition梢薪。相同mainposition的數(shù)據(jù)以鏈表形式組織蹬铺。當(dāng)找不到對(duì)應(yīng)的key時(shí)，則會(huì)調(diào)用內(nèi)部的newkey函數(shù)分配一個(gè)新的key來(lái)返回：

    (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);
    }

這個(gè)函數(shù)的操作流程如下
1秉撇、如果該mainposition上已經(jīng)有其他數(shù)據(jù)或者第一次插入情況：
（1）首先獲得lastfree指向的空間甜攀，若找不到空閑位置放置新鍵值，則調(diào)用rehash函數(shù)琐馆，增加或減少哈希表的大小规阀，重新插入元素。
（2）若該mp被占了瘦麸，檢查占領(lǐng)該位置的node的mp是不是在這個(gè)地方谁撼，若不在這個(gè)地方，則移動(dòng)該node到一個(gè)新的位置瞎暑，并且把要插入的元素插入到相應(yīng)的位置彤敛；若在這個(gè)地方（即占領(lǐng)該位置的node的mp就是要插入的位置），則把要插入的元素插入到一個(gè)新的空node中了赌。
2、如果該mp為空玄糟，則直接把相應(yīng)的元素插入到這個(gè)node中勿她。

以上操作涉及重新對(duì)表空間進(jìn)行分配的情況。這一部分比較復(fù)雜阵翎，入口函數(shù)是rehash逢并，顧名思義，這個(gè)函數(shù)的作用就是為了做重新散列操作：

    /*
    ** 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) 分配一個(gè)位圖nums砍聊，將其中的所有位置0。這個(gè)位圖的意義在于：nums數(shù)組中第i個(gè)元素存放的是 key 在 2^(i-1) 和 2^i 之間的元素?cái)?shù)量贰军。
(2) 遍歷Lua表中的數(shù)組部分玻蝌，計(jì)算其中的元素?cái)?shù)量，更新對(duì)應(yīng)的nums數(shù)組中的元素?cái)?shù)量（numusearray函數(shù)）。
(3) 遍歷lua表中的散列桶部分俯树，因?yàn)槠渲幸部赡艽娣帕苏麛?shù)帘腹，需要根據(jù)這里的正整數(shù)數(shù)量更新對(duì)應(yīng)的nums數(shù)組元素?cái)?shù)量（numusehash函數(shù)）。
(4) 此時(shí)nums數(shù)組已經(jīng)有了當(dāng)前這個(gè)Table中所有正整數(shù)的分配統(tǒng)計(jì)许饿，逐個(gè)遍歷nums數(shù)組阳欲，獲得其范圍區(qū)間內(nèi)所包含的整數(shù)數(shù)量大于50%的最大索引，作為重新散列之后的數(shù)組大小陋率，超過(guò)這個(gè)范圍的正整數(shù)球化，就分配到散列桶部分了（computesizes函數(shù)） 。
(5) 根據(jù)上面計(jì)算得到的調(diào)整后的數(shù)組和散列桶大小調(diào)整表（resize函數(shù)）瓦糟。

Lua的設(shè)計(jì)思想是赊窥，簡(jiǎn)單高效，并且還要盡量節(jié)省內(nèi)存資源狸页。
在重新散列的過(guò)程中锨能，除了增大Lua表的大小以容納新的數(shù)據(jù)之外，還希望能借此機(jī)會(huì)對(duì)原有的數(shù)組和散列桶部分進(jìn)行調(diào)整芍耘，讓兩部分都盡可能發(fā)揮其存儲(chǔ)的最高容納效率址遇。那么嘴瓤，這里的標(biāo)準(zhǔn)是什么呢屋灌？希望在調(diào)整過(guò)后，數(shù)組在每一個(gè)2次方位置容納的元素?cái)?shù)量都超過(guò)該范圍的50%奸鸯。能達(dá)到這個(gè)目標(biāo)的話坝初，我們就認(rèn)為這個(gè)數(shù)組范圍發(fā)揮了最大的效率浸剩。
設(shè)想一個(gè)場(chǎng)景來(lái)模擬前面的算法流程。假設(shè)現(xiàn)在有一個(gè)Lua表鳄袍，經(jīng)過(guò)一些變化之后绢要，它的數(shù)組有以下key的元素：1, 2, 3, 20。首先拗小，算法將計(jì)算這些key被分配到了哪些區(qū)間重罪。
在這個(gè)算法里，我們使用數(shù)組來(lái)保存落在每個(gè)范圍內(nèi)的數(shù)據(jù)數(shù)量哀九，其中每個(gè)元素存放的是 key 在 2^(i-1) 和 2^i 之間的元素?cái)?shù)量剿配。
前面關(guān)于數(shù)字鍵值的統(tǒng)計(jì)跑完之后，得到的結(jié)果是:

    nums[0] = 1（1落在此區(qū)間）
    nums[1] = 1（2落在此區(qū)間）
    nums[2] = 1（3落在此區(qū)間）
    nums[3] = 0
    nums[4] = 0
    nums[5] = 1（20落在此區(qū)間）
    nums[6] = 0
    ...
    nums[n] = 0（其中n > 5 且 n <= MAXBITS）

計(jì)算完畢后阅束，我們得到了這個(gè)數(shù)組每個(gè)元素的數(shù)據(jù)呼胚，也就是得到了落在每個(gè)范圍內(nèi)的數(shù)據(jù)數(shù)量。接著息裸，我們來(lái)計(jì)算怎樣才能最大限度地使用這部分空間蝇更。這個(gè)算法由函數(shù)computesizes實(shí)現(xiàn)：

    /*
    ** 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;
    }

這個(gè)函數(shù)的輸入?yún)?shù)nums是前面已經(jīng)計(jì)算好的計(jì)數(shù)數(shù)組沪编。pna 存放的是前面計(jì)算得到的數(shù)字鍵值的數(shù)量，這是一個(gè)指針簿寂，說(shuō)明會(huì)在這個(gè)函數(shù)中被修改漾抬，最后作為重新散列操作時(shí)數(shù)組部分的大小。這個(gè)函數(shù)的原理就是循環(huán)遍歷數(shù)字鍵值部分常遂，找到滿足前面提到的條件的最大值：該范圍內(nèi)的數(shù)據(jù)滿足大于50%的值纳令。結(jié)合前面的測(cè)試數(shù)據(jù)來(lái)“試運(yùn)行”一下這個(gè)函數(shù)。此時(shí)傳入的 pna 參數(shù)是 4克胳，也就是目前數(shù)組部分的數(shù)據(jù)數(shù)量平绩。

    首先，初始值漠另，twotoi為1捏雌，i為0，a在循環(huán)初始時(shí)為0笆搓，它表示的是循環(huán)到目前為止數(shù)據(jù)小于2^i的數(shù)據(jù)數(shù)量性湿。
    i = 0，twotoi = 1满败，滿足（twotoi > 0 && *pna > twotoi / 2）肤频，nums[i] = 1 > 0成立，a += nums[i], a = 1算墨，滿足a > twotoi/2宵荒，也就是滿足這個(gè)范圍內(nèi)數(shù)組利用率大于50%的原則，此時(shí)記錄下這個(gè)范圍净嘀，也就是 optimal = twotoi = 1报咳，到目前為止的數(shù)據(jù)數(shù)量 na = a = 1

    i = 1，twotoi = 2挖藏，滿足（twotoi > 0 && *pna > twotoi / 2）暑刃，nums[i] = 1 > 0成立，a += nums[i], a = 2熬苍，滿足a > twotoi/2稍走，記錄下這個(gè)范圍，也就是 optimal = twotoi = 2柴底，到目前為止的數(shù)據(jù)數(shù)量 na = a = 2

    i = 2，twotoi = 4粱胜，滿足（twotoi > 0 && *pna > twotoi / 2）柄驻，nums[i] = 1 > 0成立，a += nums[i], a = 3焙压，此時(shí)滿足a > twotoi/2鸿脓，記錄下這個(gè)范圍抑钟，也就是 optimal = twotoi = 4，到目前為止的數(shù)據(jù)數(shù)量 na = a = 3

    i = 3野哭，twotoi = 8在塔，不滿足（twotoi > 0 && *pna > twotoi / 2），結(jié)束拨黔，返回 optimal 為4蛔溃。

得到數(shù)組的大小是4篱蝇，也就是說(shuō)key為1贺待、2零截、3這三個(gè)元素落在了數(shù)組部分麸塞，而20則落在了散列桶部分。這個(gè)過(guò)程可以看出涧衙，一個(gè)整數(shù)的key在同一個(gè)表中不同的階段可能被分配到數(shù)組或者散列桶部分哪工，而這一點(diǎn)是很多人經(jīng)常忽視的。

另外弧哎，從上面的分析可以看到雁比，Lua解釋器背著我們會(huì)對(duì)表進(jìn)行重新散列的動(dòng)作，而這個(gè)操作的代價(jià)是挺大的傻铣，如下面的代碼：

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

在這段代碼中章贞，主要做了如下工作。
(1) 最開(kāi)始非洲，Lua創(chuàng)建了一個(gè)空表a鸭限。
(2) 在第一次迭代中，a[1]為true觸發(fā)了一次重新散列操作两踏，Lua將數(shù)組部分的長(zhǎng)度設(shè)置為2^0败京，即1，散列表部分仍為空梦染。
(3) 在第二次迭代中赡麦，a[2]為true再次觸發(fā)了重新散列操作，將數(shù)組部分長(zhǎng)度設(shè)為2^1帕识，即2泛粹。
(4) 最后一次迭代又觸發(fā)了一次重新散列操作，將數(shù)組部分長(zhǎng)度設(shè)為2^2肮疗，即4晶姊。
只有三個(gè)元素的表會(huì)執(zhí)行三次重新散列操作，然而有100萬(wàn)個(gè)元素的表僅僅只會(huì)執(zhí)行20次重新散列操作而已伪货，因?yàn)?^20 = 1048576 > 1000000们衙。但是钾怔，如果創(chuàng)建了非常多的長(zhǎng)度很小的表，這可能會(huì)造成巨大的影響蒙挑。
如果你有很多很小的表需要?jiǎng)?chuàng)建宗侦，就可以預(yù)先填充以避免重新散列操作。比如：{true, true, true}忆蚀，Lua知道這個(gè)表有3個(gè)元素矾利，所以直接創(chuàng)建了3個(gè)元素的數(shù)組。類(lèi)似地蜓谋，{x=1, y=2, z=3}梦皮，Lua創(chuàng)建長(zhǎng)度為3散列部分。

這里對(duì)比以下兩段代碼桃焕，首先看沒(méi)有使用預(yù)填充技術(shù)的代碼：

    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)

再看使用了預(yù)填充技術(shù)的代碼：

    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)

測(cè)試得到剑肯，使用了預(yù)填充技術(shù)的代碼比沒(méi)有使用這個(gè)優(yōu)化的代碼的速度提高了多倍。所以观堂，當(dāng)需要?jiǎng)?chuàng)建非常多的小表時(shí)让网，應(yīng)預(yù)先填充好表的大小，減少解釋器被動(dòng)地進(jìn)行重新散列操作的過(guò)程师痕。