lua table # 取长度问题

任何语言都不是完美无瑕的，在使用中都有各种问题，lua 也不例外。而 lua 使用中，绝对绕不开的一个问题就是 # 取 table 长度问题。

问题描述

先看下 # 的一些使用情况，希望引起你的困惑：

> t = {1,1,nil,1}
> #t
4
> t = {nil,nil,1,nil}
> #t
0
> t = {1,nil,nil,nil,nil,nil,nil,1}
> #t
8
> t[9] = 1
> #t
1
> t = {1,nil,nil,nil,nil,nil,nil,1,1}
> #t
9

当 table 有部分值为 nil 时，你很难清楚 # 取得的结果是什么。（如果你想知道 table 实际长度，只能遍历 table）

问题分析

实际上， lua # 不是取得的结果 table t 的长度，而是取得 t 的边界值 i。他只是设法让 i 的结果达成： t[i] ~= nil 且 t[i+1] == nil

lua table 实现上有两个组成部分，数组和哈希表。如果 key 都是比较小的连续数字，那使用数组就有天然的优势，除此之外，就利用哈希表实现。

但是，就算使用了数组，也无法保证用户的 key 一定是连续的，这样，数组的部分值就是 nil，除非遍历所有结果，否则无法得到实际的长度。

现在看下 # table 的源码实现：

// ltable.c

/*
** 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])) {
    /* 数组最后一个元素为 nil，二分查找 */
    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 if (isdummy(t)) 
    /* 只用到数组部分，且最后一个元素不为 nil，直接返回数组长度 */
    return j;
  else
    /* 查找哈希表的边界值 */
    return unbound_search(t, j);
}

再看下哈希表查找的代码

// ltable.c

static lua_Unsigned unbound_search (Table *t, lua_Unsigned j) {
  lua_Unsigned i = j;
  j++;
  /* 哈希表是数组放不下后存放的，所以先从数组长度 + 1 开始查找
   * 以倍增法确定key的最大范围，然后二分查找锁定最终key
   */
  while (!ttisnil(luaH_getint(t, 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;
}

至此，# 查找 table 的过程已经讲完。# 取得的结果是 table 数字 key 的边界值。

问题探讨

难道 # 取长度意义就不大了，我觉得作用还是很大的。
第一个，当你一直都是 table.insert 插入数据，没有移出数据，或者使用 table.remove，# 取长度就是准确的，而且效率非常高。
第二个，当 table 元素非常多的时候，lua 态遍历 table 的开销已经不能忽视了，# 可以快速估算 table 长度。当然，你也可以另外加个计数器。