「�TODO�」: 表的查找和新增元素

取长度操作

Lua中可以用 # 符号对表进行取长度操作. 对Lua中的表进行取长度操作时, 如果没有该表的元方法 __len, 则该取长度操作只对表的数组部分进行.

取长度的入口函数为 luaH_getn, 该函数的目的是找到表 t 的一个边界值i, 并且t[i]不为nil, t[i+1]为nil (如果t[1]为nil, 则i为0) 它的伪代码如下:

如果表存在数组部分:
    在数组部分二分查找返回位置i,其中i足满足条件 t[i] != nil 且 t[i+1] == nil 的最大数据
否则前面的数组部分查不到满足条件的数据, 进入散列部分查找:
    在散列桶部分二分查找返回位置i. 其中i是满足条件 t[i] != nil 且 t[i+1] == nil 的最大数据

使用表时需要注意的事项

  • 尽量不要将一个表混用数组和散列桶部分, 即一个表最好只存放一类数据. Lua 的实现上确实提供了两者统一表示的遍历, 但是这不意味着使用者就应该混用这两种方式.
  • 尽量避免进行重新散列操作, 因为重新散列操作的代价极大. 通过预分配, 只使用数组部分等策略规避这个Lua解释器背后的动作, 能提升不少效率.

Lua53相关源码

luaH_getn

//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])) {
    /* 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? */
    return j;  /* that is easy... */
  else return unbound_search(t, j);
}

//ltable.c
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))) {
    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;
}