Lua之table长度求解
取长度使用到的函数
/*
** Try to find a boundary in table 't'. A 'boundary' is an integer index
** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
*/
lua_Unsigned luaH_getn (Table *t) {
unsigned int j = t->sizearray;
if (j > 0 && ttisnil(&t->array[j - 1])) { // 数组最后一个元素为空，二分法查找
/* there is a boundary in the array part: (binary) search for it */
unsigned int i = 0;
while (j - i > 1) {
unsigned int m = (i+j)/2;
if (ttisnil(&t->array[m - 1])) j = m;
else i = m;
}
return i;
}
/* else must find a boundary in hash part */
else if (isdummy(t)) /* hash part is empty? */ // 数组最后一个元素不为空，但是 hash 部分为空
return j; /* that is easy... */
else return unbound_search(t, j); // 数组最后一个元素不为空，hash 部分也不为空
}
/*
首先判断的是，数组最后一个元素是否为空
为空
二分法查找
不为空，但 hash 部分为空
返回数组长度作为要获取的长度
不为空，hash 也不为空
unbound_search(t, j)，实现如下
*/
static lua_Unsigned unbound_search (Table *t, lua_Unsigned j) {
lua_Unsigned i = j; /* i is zero or a present index */
j++;
/* find 'i' and 'j' such that i is present and j is not */
while (!ttisnil(luaH_getint(t, j))) { // 找到 t[j] 不为空， t[2*j] 为空，那么长度在 j 与 2*j 之间
i = j;
if (j > l_castS2U(LUA_MAXINTEGER) / 2) { /* overflow? */
/* table was built with bad purposes: resort to linear search */
i = 1;
while (!ttisnil(luaH_getint(t, i))) i++;
return i - 1;
}
j *= 2;
}
/* now do a binary search between them */
while (j - i > 1) {
lua_Unsigned m = (i+j)/2; // 二分法查找
if (ttisnil(luaH_getint(t, m))) j = m;
else i = m;
}
return i;
}
数组的长度为 j，hash 部分从 j+1 开始遍历，j 每次扩大两倍，找到t[j] 不为空， t[2*j] 为空，然后通过二分法查找，找到最终的值。
实例
例1 （全部为数组部分）
local t = {1, 2, 3, 4}
print(#t) -- 4
解释：t 没有 hash 部分，数组长度为4。t[4] 不为空，所以返回 j = 4。
例2
local t = {1, nil, 3}
print(#t) -- 3
解释：t没有 hash 部分，数组长度为3。t[3] 不为空，所以返回 j = 3。
例3
local t = {1, nil, 3, nil}
print(#t) -- 1
解释：t 没有 hash 部分，数组长度为4。t[4] 为空，所以利用二分法查找
i = 0, j = 4, m = (i+j)/2 = 2, array[2] 为空, j = m = 2;
i = 0, j = 2, m = (i+j)/2 = 1, array[1] 不为空, i = m = 1;
i = 1, j = 2, 条件 j - i > 1 不满足，循环终止，返回 i = 1。
例4（全部为 hash 部分）
local t = {[1] = 1, [3] = 3, [5] = 5, [6] = 6, [7] = 7}
print(#t) -- 1
解释：t没有数组元素。调用 unbound_search 函数，hash 部分从 j = 1 开始遍历，其中 i记录的是上一个 j的值
i = 0, j = 1, t[1] 不为空, i = j = 1, j = 2
i = 1, j = 2, t[1] 为空, j - i = 1 > 1 不成立，返回 i = 1。
例5
local t = {[1] = 1, [2] = 2, [4] = 4, [6] = 6}
print(#t) -- 6
解释：t没有数组元素，调用 unbound_search 函数，hash 部分从 j = 1 开始遍历
i = 0, j = 1, t[1] 不为空, i = j = 1, j = 2
i = 1, j = 2, t[2] 不为空, i = j = 2, j = 4
i = 2, j = 4, t[4] 不为空, i = j = 4, j = 8
i = 4, j = 8, t[8] 为空, j - i = 4 > 1 成立，通过二分法查找值
i = 4, j = 8, m = (i+j)/2 = 6, t[6] 不为 nil, i = m = 6;
i = 6, j = 8, m = (i+j)/2 = 7, t[7] 为 nil, j = m = 7;
i = 6, j = 7, 条件 j - i > 1 不满足，循环终止，返回 i = 6。
例6（既包含数组部分，包含hash 部分）
local t = {1, 2, 3, [5] = 5}
print(#t) -- 3
解释：数组部分长度为3，hash 部分长度为1。由于 t[3] 不为空，同时 hash 部分不为空，所以调用 unbound_search 函数，hash 部分从 j = 4 开始遍历
i = 3, j = 4, t[4] 为空, j - i = 1 > 1 不成立，返回 i = 3
例7
local t = {1, 2, 3, [4] = 4}
print(#t) -- 4
解释：数组部分长度为3，hash 部分长度为1。由于 t[3] 不为空，同时 hash 部分不为空，所以调用 unbound_search 函数，hash 部分从 j = 4 开始遍历
i = 3, j = 4, t[4] 不为空, i = j = 4, j = 8
i = 4, j = 8, t[8] 为空, j - i = 4 > 1 成立
通过二分法查找，最终返回 i = 4
例8
local t = {1, 2, 3, nil, [5] = 5}
print(#t) -- 3
解释：数组部分长度为4，hash 部分长度为1。由于 t[4] 为空，则在数组部分利用二分法查找，参考例3，最终返回 i = 3。
以上都是在创建 table 时确定好了数组部分和 hash 部分，但是如果新增键值的话，可能会造成调用 rehash 函数，重新分配数组和 hash 部分。
例9
local t = {1, [4] = 4}
print(#t) -- 1
t[3] = 3 -- 添加键值
print(#t) -- 4
第一个为1，可以参考上面的例子，当添加键值的时候，重新分配，结果是数组部分长度为4，hash 部分为0，等价于
local t = {1, nil, 3, 4}
参考Lua之table新增整数键值。由于数组部分 t[4]不为空，返回 i = 4。
例10
local t = {1, [5] = 5}
t[3] = 3
print(#t) -- 1
当添加键值的时候，重新分配，结果是数组部分长度为1，hash 部分为2，等价于
local t = {1, [3] = 3, [5] = 5}
例11
local t = {1, 2, [5] = 5}
t[4] = 4
print(#t) -- 5
等价于
local t = {1, 2, nil, 4, [5] = 5}
总结
（1）尽量不要在一个表中混用数组或散列桶部分，即一个表最好只存放一类数据。lua的实现上确实提供了两者统一表示的遍历，但是这并不意味着使用者就应该混用这两种方式。
（2）尽量不要在表中存放nil值，这会让取长度操作的行为不稳定。
（3）尽量避免重新散列操作，因为这个操作的代价极大，通过预分配、只使用数组部分等策略规避这个lua解释器背后的动作，能提升不少效率。
