losophy

lua Table

发表于 更新于

table实现了关联数组，即可以同时用数字和字符串索引的数组。
table是一种强大的语言构造。因为table的泛型特点，简化了使用lua编写程序所用的数据结构和算法。

哈希与数组

直到Lua 4.0为止，table都是作为纯哈希表实现的，所有的键值对都是显式存储的。在Lua 5.0版本引入了table的混合表示：每个table包含了一个哈希部分和一个数组部分，两个部分都可以是空的。Lua检测一个table是不是作为一个数组来使用，并自动将数字索引的值移动到数组部分，而非原本的存储在哈希部分。这种分裂只在底层实现层次进行；访问table域是透明的，即使是对虚拟机来说。table会自动根据内容使用两个部分。
这个混合机制有两个优点。第一，访问整型key的操作会变得更快了，因为不再需要哈希。第二，更重要的是，数组部分只占原来哈希部分的一半大小，因为哈希部分需要同时存储key和value，而数组部分的key已经隐含在下标了。结果是，如果一个table是作为数组使用的，它的表现就像数组一样，只要它的整型key是密集分布的。而且，哈希部分没有内存或者时间的代价，因为作为数组使用时，哈希部分不存在。反过来说，如果table是作为记录使用而非数组，那么数组部分就是空的。这些节省下来的内存是重要的。

Lua核心突出角色

从Lua 4.0开始，全局变量就存储在普通的Lua table里，称为全局table。Lua 5.0用元表和元方法取代了tag和tag方法（Lua 3.0引入的）。元表是普通的Lua table，元方法是作为元表的域存储的。Lua 5.0也引入了环境table，可以附加到Lua函数上；它们就是Lua函数索引的全局环境。Lua 5.1将环境变量table扩展到C函数、userdata和协程，取代了全局的环境变量。这些改动简化了Lua的实现、Lua和C程序员所用的API，因为全局变量和元方法可以在Lua里操控，不再需要特殊函数了。

实现

先看看表的数据类型定义：

1
2
3
4
5
6
7
8
9
10
11
typedef struct Table {
  CommonHeader;
  lu_byte flags; //这是一个byte类型的数据，用于表示这个表中提供了哪些元方法。最开始这个flags是空的，也就是0，当查找一次之后，如果该表中存在某个元方法，那么将该元方法对应的flag bit置为1，这样下一次查找时只需要比较这个bit就行了。每个元方法对应的bit定义在ltm. h文件中。
  lu_byte lsizenode;  //该表中以2为底的散列表大小的对数值。同时由此可知，散列表部分的大小一定是2的幕，即如果散列桶数组要扩展的话，也是以每次在原大小基础上乘以2的形式扩展。
  struct Table *metatable;//存放该表的元表
  TValue *array;  //指向数组部分的指针
  Node *node;  //指向该表的散列桶数组起始位置的指针 
  Node *lastfree;  //指向该表散列桶数组的最后位置的指针
  GCObject *gclist; //GC相关的链表
  int sizearray;  //数组部分的大小
} Table;

从Node类型来看，它包含两个成员，一个是key，另一个是value（TValue）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef union TKey {
  struct {
    TValuefields;
    struct Node *next;  /* for chaining */
  } nk;
  TValue tvk;
} TKey;

#define TValuefields	Value value; int tt

typedef union {
  GCObject *gc;
  void *p;
  lua_Number n;
  int b;
} Value;

typedef struct Node {
  TValue i_val;
  TKey i_key;
} Node;

表查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const TValue *luaH_getnum (Table *t, int key) {
  /* (1 <= key && key <= t->sizearray) */
  if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray))//如果输入的Key是一个正整数，并且它的位大于0并且少等于或等于数组的大小，尝试在数组部分查找
    return &t->array[key-1];
  else {//如果不是，尝试在散列表部分查找，计算出该`Key`的散列值，根据此散列值访问`Node`数组得到散列桶所在的位置，遍历该散列桶下的所有链表元素，直到找到该`Key`为止。
    lua_Number nk = cast_num(key);
    Node *n = hashnum(t, nk);
    do {  /* check whether `key' is somewhere in the chain */
      if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk))
        return gval(n);  /* that's it */
      else n = gnext(n);
    } while (n);
    return luaO_nilobject;
  }
}

可以看到，即使是一个正整数的key，其存储部分也不见得会一定落在数组部分，这完全取决于它的大小是再落在了当前数组可容纳的空间范围内（OP_NEWTABLE中GETARG_B）。也解释了ipairs遍历断裂的问题。

1
2
3
local t = {}
t[1] = 0 -- 1作为数组部分存储下来
t[100] = 0 --100存储到散列表部分中

新增元素

当找不到对应的key时，最终都会调用内部的newkey函数分配一个新的key来返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
static TValue *newkey (lua_State *L, Table *t, const TValue *key) {
  Node *mp = mainposition(t, key);//根据key来查找其所在散列桶的mainposition
  if (!ttisnil(gval(mp)) || mp == dummynode) {//如果该mainposition上已经有其他数据了，需要重新分配空间给这个新的key，然后将这个新的Node串联到对应的散列桶上
    Node *othern;
    Node *n = getfreepos(t);  /* get a free place */
    if (n == NULL) {  /* cannot find a free place? */
      rehash(L, t, key);  /* grow table */
      return luaH_set(L, t, key);  /* re-insert key into grown table */
    }
    lua_assert(n != dummynode);
    othern = mainposition(t, key2tval(mp));
    if (othern != mp) {  /* is colliding node out of its main position? */
      /* yes; move colliding node into free position */
      while (gnext(othern) != mp) othern = gnext(othern);  /* find previous */
      gnext(othern) = n;  /* redo the chain with `n' in place of `mp' */
      *n = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
      gnext(mp) = NULL;  /* now `mp' is free */
      setnilvalue(gval(mp));
    }
    else {  /* colliding node is in its own main position */
      /* new node will go into free position */
      gnext(n) = gnext(mp);  /* chain new position */
      gnext(mp) = n;
      mp = n;
    }
  }
  gkey(mp)->value = key->value; gkey(mp)->tt = key->tt;//如果该Node的值为nil，那么直接将key赋值并且返回Node的TValue指针就可以了
  luaC_barriert(L, t, key);
  lua_assert(ttisnil(gval(mp)));
  return gval(mp);
}

散列表部分的数据组织是，首先计算数据的key所在的桶数组位置，这个位置称为mainposition。相同mainposition的数据以链表形式组织。
整个过程都是在散列桶部分进行的，理由是即使key是一个数字，也已经在调用newkey函数之前进行了查找，结果却没有找到，所以这个key都会进入散列桶部分来查找。

rehash

以上操作涉及重新对表空间进行分配的情况。入口函数是rehash，顾名思义，这个函数的作用就是为了做重新散列操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void rehash (lua_State *L, Table *t, const TValue *ek) {
  int nasize, na;
  int nums[MAXBITS+1];  //分配一个位图nums，将其中的所有位置0。这个位图的意义在于：nums数组中第 i个元素存放的是key在2(i-l）和i之间的元素数量。
  int i;
  int totaluse;
  for (i=0; i<=MAXBITS; i++) nums[i] = 0;  
  nasize = numusearray(t, nums);  //遍历Lua表中的数组部分，计算其中的元素数量，更新对应的nums数组中的元素数量
  totaluse = nasize;  /* all those keys are integer keys */
  totaluse += numusehash(t, nums, &nasize);  //遍历lua表中的散列桶部分，因为其中也可能存放了正整数，需要根据这里的正整数数量更新对应的nums数组元素数量
  /* count extra key */
  nasize += countint(ek, nums);
  totaluse++;
  /* compute new size for array part */
  na = computesizes(nums, &nasize);//此时nums数组已经有了当前这个Table中所有正整数的分配统计，逐个遍历nums数组，获得其范围区间内所包含的整数数量大于50%的最大索引，作为重新散列之后的数组大小，超过这个范围的正整数，就分配到散列桶部分了
  /* resize the table to new computed sizes */
  resize(L, t, nasize, totaluse - na);//根据上面计算得到的调整后的数组和散列桶大小调整表
}

在重新散列的过程中，除了增大Lua表的大小以容纳新的数据之外，还希望能借此机会对原有的数组和散列桶部分进行调整，让两部分都尽可能发挥其存储的最高容纳效率。那么，这里的标准是什么呢？希望在调整过后，数组在每一个2次方位置容纳的元素数量都超过该范围的50%。 能达到这个目标的话，就认为这个数组范围发挥了最大的效率。

当数字键值的统计跑完之后，得到了这个数组每个元素的数据，也就是得到了落在每个范围内的数据数量。接着会计算怎样才能最大限度地使用这部分空间 。这个算法由函数computesizes实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static int computesizes (int nums[], int *narray) {
  int i;
  int twotoi;  /* 2^i */
  int a = 0;  /* number of elements smaller than 2^i */
  int na = 0;  /* number of elements to go to array part */
  int n = 0;  /* optimal size for array part */
  for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) {
    if (nums[i] > 0) {
      a += nums[i];
      if (a > twotoi/2) {  /* more than half elements present? */
        n = twotoi;  /* optimal size (till now) */
        na = a;  /* all elements smaller than n will go to array part */
      }
    }
    if (a == *narray) break;  /* all elements already counted */
  }
  *narray = n;
  lua_assert(*narray/2 <= na && na <= *narray);
  return na;
}

迭代

在一般算法库的设计中，针对容器类的迭代，会提供一个迭代器的数据，这个数据主要用于维护当前迭代到容器的哪部分数据了，下次再根据这个位置查找下一部分数据。表迭代不是这样设计的，很大的原因是为了兼容数组部分和散列桶部分的访问 。 迭代操作传入的不是一个迭代器，而是key。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int luaH_next (lua_State *L, Table *t, StkId key) {
  int i = findindex(L, t, key);  /* find original element */
  for (i++; i < t->sizearray; i++) {  /* try first array part */
    if (!ttisnil(&t->array[i])) {  /* a non-nil value? */
      setnvalue(key, cast_num(i+1));
      setobj2s(L, key+1, &t->array[i]);
      return 1;
    }
  }
  for (i -= t->sizearray; i < sizenode(t); i++) {  /* then hash part */
    if (!ttisnil(gval(gnode(t, i)))) {  /* a non-nil value? */
      setobj2s(L, key, key2tval(gnode(t, i)));
      setobj2s(L, key+1, gval(gnode(t, i)));
      return 1;
    }
  }
  return 0;  /* no more elements */
}

不管是在数组部分还是散列桶部分查找数据，查找成功都会返回该key的下一个数据。
这个函数一开始就进入findindex中进行查询，并区分数组和散列桶部分。findindex函数的返回结果是一个整数索引，如果这个索引在表的sizearray之内，则说明落入到数组部分，否则就落入到散列桶部分。在luaH_next函数中使用这个返回值时，看起来是两个循环，实际上已经根据这个值的范围进行了区分，不会同一个key走入两个循环中。而在返回散列桶部分时，这个索引值为”sizearray＋对应散列桶索引的值”。

取长度操作

在Lua中，可以使用#符号对表进行取长度操作。对Lua中的表进行取长度操作时，如果没有提供该表的元方法_len，那么该操作只针对该表的序列（ sequence ）部分进行。 “序列”指的是表的一个子集{1 ... n}，其中n是一个正整数，并且里面每个键对应的数据都不为nil。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int 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 (t->node == dummynode)  /* hash part is empty? */
    return j;  /* that is easy... */
  else return unbound_search(t, j);
}

如果表中混合了这两种风格的数据，那么优先取数组部分的长度。如果表存在数组部分，在数组部分二分查找返回位置。如果前面的数组部分查不到满足条件的数据，进入散列表部分查找。
所以，尽量不要将一个表混用数组和散列桶部分，即一个表最好只存放一类数据。Lua的实现上确实提供了两者统一表示的遍历，但是这不意味着使用者就应该混用这两种方式。

从lua-5.1.1中分离出来的table实现代码

ltable

reference

《Lua设计与实现》

Un hermano puede no ser un amigo, pero un amigo será siempre un hermano.

相关文章