一般情況下，你不需要知道Lua實(shí)現(xiàn)表的細(xì)節(jié)，就可以使用它。實(shí)際上，Lua花了很多功夫來(lái)隱藏內(nèi)部的實(shí)現(xiàn)細(xì)節(jié)。但是，實(shí)現(xiàn)細(xì)節(jié)揭示了表操作的性能開銷情況。因此，要優(yōu)化使用表的程序（這里特指Lua程序），了解一些表的實(shí)現(xiàn)細(xì)節(jié)是很有好處的。
Lua的表的實(shí)現(xiàn)使用了一些很聰明的算法。每個(gè)Lua表的內(nèi)部包含兩個(gè)部分：數(shù)組部分和哈希部分。數(shù)組部分以從1到一個(gè)特定的n之間的整數(shù)作為鍵來(lái)保存元素（我們稍后即將討論這個(gè)n是如何計(jì)算出來(lái)的）。所有其他元素（包括在上述范圍之外的整數(shù)鍵）都被存放在哈希部分里。
正如其名，哈希部分使用哈希算法來(lái)保存和查找鍵。它使用被稱為開放地址表的實(shí)現(xiàn)方式，意思是說(shuō)所有的元素都保存在哈希數(shù)組中。用一個(gè)哈希函數(shù)來(lái)獲取一個(gè)鍵對(duì)應(yīng)的索引；如果存在沖突的話（意即，如果兩個(gè)鍵產(chǎn)生了同一個(gè)哈希值），這些鍵將會(huì)被放入一個(gè)鏈表，其中每個(gè)元素對(duì)應(yīng)一個(gè)數(shù)組項(xiàng)。當(dāng)Lua需要向表中添加一個(gè)新的鍵，但哈希數(shù)組已滿時(shí)，Lua將會(huì)重新哈希。重新哈希的第一步是決定新的數(shù)組部分和哈希部分的大小。因此，Lua遍歷所有的元素，計(jì)數(shù)并對(duì)其進(jìn)行歸類，然后為數(shù)組部分選擇一個(gè)大小，這個(gè)大小相當(dāng)于能使數(shù)組部分超過(guò)一半的空間都被填滿的2的最大的冪；然后為哈希部分選擇一個(gè)大小，相當(dāng)于正好能容納哈希部分所有元素的2的最小的冪。
當(dāng)Lua創(chuàng)建空表時(shí)，兩個(gè)部分的大小都是0。因此，沒(méi)有為其分配數(shù)組。讓我們看一看當(dāng)執(zhí)行下面的代碼時(shí)會(huì)發(fā)生什么：
復(fù)制代碼 代碼如下:
local a = {}
for i = 1, 3 do
a[i] = true
end
這段代碼始于創(chuàng)建一個(gè)空表。在循環(huán)的第一次迭代中，賦值語(yǔ)句
復(fù)制代碼 代碼如下:
a[1] = true
觸發(fā)了一次重新哈希；Lua將數(shù)組部分的大小設(shè)為1，哈希部分依然為空；第二次迭代時(shí)
復(fù)制代碼 代碼如下:
a[2] = true
觸發(fā)了另一次重新哈希，將數(shù)組部分?jǐn)U大為2.最終，第三次迭代又觸發(fā)了一次重新哈希，將數(shù)組部分的大小擴(kuò)大為4。
類似下面的代碼
復(fù)制代碼 代碼如下:
a = {}
a.x = 1; a.y = 2; a.z = 3
做的事情類似，只不過(guò)增加的是哈希部分的大小。
對(duì)于大的表來(lái)說(shuō)，初期的幾次重新哈希的開銷被分?jǐn)偟秸麄€(gè)表的創(chuàng)建過(guò)程中，一個(gè)包含三個(gè)元素的表需要三次重新哈希，而一個(gè)有一百萬(wàn)個(gè)元素的表也只需要二十次。但是當(dāng)創(chuàng)建幾千個(gè)小表的時(shí)候，重新哈希帶來(lái)的性能影響就會(huì)非常顯著。
舊版的Lua在創(chuàng)建空表時(shí)會(huì)預(yù)選分配大?。?，如果我沒(méi)有記錯(cuò)的話），以防止在初始化小表時(shí)產(chǎn)生的這些開銷。但是這樣的實(shí)現(xiàn)方式會(huì)浪費(fèi)內(nèi)存。例如，如果你要?jiǎng)?chuàng)建數(shù)百萬(wàn)個(gè)點(diǎn)（表現(xiàn)為包含兩個(gè)元素的表），每個(gè)都使用了兩倍于實(shí)際所需的內(nèi)存，就會(huì)付出高昂的代價(jià)。這也是為什么Lua不再為新表預(yù)分配數(shù)組。
如果你使用C編程，可以通過(guò)Lua的API函數(shù)lua_createtable來(lái)避免重新哈希；除lua_State之外，它還接受兩個(gè)參數(shù)：數(shù)組部分的初始大小和哈希部分的初始大小[1]。只要指定適當(dāng)?shù)闹?，就可以避免初始化時(shí)的重新哈希。需要警惕的是，Lua只會(huì)在重新哈希時(shí)收縮表的大小，因此如果在初始化時(shí)指定了過(guò)大的值，Lua可能永遠(yuǎn)不會(huì)糾正你浪費(fèi)的內(nèi)存空間。
當(dāng)使用Lua編程時(shí)，你可能可以使用構(gòu)造式來(lái)避免初始化時(shí)的重新哈希。當(dāng)你寫下
復(fù)制代碼 代碼如下:
{true, true, true}
時(shí)，Lua知道這個(gè)表的數(shù)組部分將會(huì)有三個(gè)元素，因此會(huì)創(chuàng)建相應(yīng)大小的數(shù)組。類似的，如果你寫下
復(fù)制代碼 代碼如下:
{x = 1, y = 2, z = 3}
Lua也會(huì)為哈希部分創(chuàng)建一個(gè)大小為4的數(shù)組。例如，執(zhí)行下面的代碼需要2.0秒：
復(fù)制代碼 代碼如下:
for i = 1, 1000000 do
local a = {}
a[1] = 1; a[2] = 2; a[3] = 3
end
如果在創(chuàng)建表時(shí)給定正確的大小，執(zhí)行時(shí)間可以縮減到0.7秒：
復(fù)制代碼 代碼如下:
for i = 1, 1000000 do
local a = {true, true, true}
a[1] = 1; a[2] = 2; a[3] = 3
end
但是，如果你寫類似于
復(fù)制代碼 代碼如下:
{[1] = true, [2] = true, [3] = true}
的代碼，Lua還不夠聰明，無(wú)法識(shí)別表達(dá)式（在本例中是數(shù)值字面量）指定的數(shù)組索引，因此它會(huì)為哈希部分創(chuàng)建一個(gè)大小為4的數(shù)組，浪費(fèi)內(nèi)存和CPU時(shí)間。
兩個(gè)部分的大小只會(huì)在Lua重新哈希時(shí)重新計(jì)算，重新哈希則只會(huì)發(fā)生在表完全填滿后，Lua需要插入新的元素之時(shí)。因此，如果你遍歷一個(gè)表并清除其所有項(xiàng)（也就是全部設(shè)為nil），表的大小不會(huì)縮小。但是此時(shí)，如果你需要插入新的元素，表的大小將會(huì)被調(diào)整。多數(shù)情況下這都不會(huì)成為問(wèn)題，但是，不要指望能通過(guò)清除表項(xiàng)來(lái)回收內(nèi)存：最好是直接把表自身清除掉。
一個(gè)可以強(qiáng)制重新哈希的猥瑣方法是向表中插入足夠多的nil。例如：
復(fù)制代碼 代碼如下:
a = {}
lim = 10000000
for i = 1, lim do a[i] = i end -- 創(chuàng)建一個(gè)巨表
print(collectgarbage("count")) --> 196626
for i = 1, lim do a[i] = nil end -- 清除所有元素
print(collectgarbage("count")) --> 196626
for i = lim + 1, 2 * lim do a[i] = nil end -- 創(chuàng)建一堆nil元素
print(collectgarbage("count")) --> 17
除非是在特殊情況下，我不推薦使用這個(gè)伎倆：它很慢，并且沒(méi)有簡(jiǎn)單的方法能知道要插入多少nil才夠。
你可能會(huì)好奇Lua為什么不會(huì)在清除表項(xiàng)時(shí)收縮表。首先是為了避免測(cè)試寫入表中的內(nèi)容。如果在賦值時(shí)檢查值是否為nil，將會(huì)拖慢所有的賦值操作。第二，也是最重要的，允許在遍歷表時(shí)將表項(xiàng)賦值為nil。例如下面的循環(huán)：
復(fù)制代碼 代碼如下:
for k, v in pairs(t) do
if some_property(v) then
t[k] = nil – 清除元素
end
end
如果Lua在每次nil賦值后重新哈希這張表，循環(huán)就會(huì)被破壞。
如果你想要清除一個(gè)表中的所有元素，只需要簡(jiǎn)單地遍歷它：
復(fù)制代碼 代碼如下:
for k in pairs(t) do
t[k] = nil
end
一個(gè)“聰明”的替代解決方案：
復(fù)制代碼 代碼如下:
while true do
local k = next(t)
if not k then break end
t[k] = nil
end
但是，對(duì)于大表來(lái)說(shuō)，這個(gè)循環(huán)將會(huì)非常慢。調(diào)用函數(shù)next時(shí)，如果沒(méi)有給定前一個(gè)鍵，將會(huì)返回表的第一個(gè)元素（以某種隨機(jī)的順序）。在此例中，next將會(huì)遍歷這個(gè)表，從開始尋找一個(gè)非nil元素。由于循環(huán)總是將找到的第一個(gè)元素置為nil，因此next函數(shù)將會(huì)花費(fèi)越來(lái)越長(zhǎng)的時(shí)間來(lái)尋找第一個(gè)非nil元素。這樣的結(jié)果是，這個(gè)“聰明”的循環(huán)需要20秒來(lái)清除一個(gè)有100,000個(gè)元素的表，而使用pairs實(shí)現(xiàn)的循環(huán)則只需要0.04秒。
[1] 盡管重新哈希算法始終設(shè)置數(shù)組的大小為2的冪，數(shù)組的大小依然可以為任何自然數(shù)值。而哈希的大小必須為2的冪，所以第二個(gè)參數(shù)總是會(huì)被圓整為不小于原值的最小的2的冪。
您可能感興趣的文章:- Lua性能優(yōu)化技巧（一）：前言
- Lua性能優(yōu)化技巧（二）：基本事實(shí)
- Lua性能優(yōu)化技巧（四）：關(guān)于字符串
- Lua性能優(yōu)化技巧（五）：削減、重用和回收
- Lua性能優(yōu)化技巧（六）：最后的提示
