Lua table 内部实现（上）

这一节介绍 Lua 唯一的数据结构 table ，相对于大部分语言提供 数组和字典 两种类型，Lua将其合二为一，颇为精巧的实现了table。

table充分体现了Lua语言的特点，用最简练的语法表达丰富的信息，但也增加了用户的理解成本。table包含 数组和哈希 两部分功能，所以实现起来颇为复杂。

本文展示的代码来自llamavm，并非Lua源码，C++版本的实现比较容易理解。

实现部分包括：

1. 数据存储

2. 获取key值

3. 修改key值

4. 自动扩容

5. 计算数组长度

6. 遍历table

示例代码：

tb = { 10, 'num', {30}; 
       ['k1']='v1', k2=20 }

print("输出数组部分")
for i=1,#tb do
  print(tb[i])
end

print("输出所有元素")
for k,v in pairs(tb) do
  print(k .. " = " .. tostring(v))
end

执行结果：

输出数组部分
10
num
table: 00396F20

输出所有元素
1 = 10
2 = num
3 = table: 00396F20
k1 = v1
k2 = 20

Part1 数据存储

若将数组下标索引（1到n）作为整数key，用一个 哈希表 就能实现table。

key可以为 nil 之外的任意类型，比如 整数key、字符串key，布尔key ，甚至可以用 函数、table 作为key。

在Lua5.0之前，table内部用一个哈希表实现，5.0版本后拆分为数组和哈希两个部分。

两种实现的区别

（1）一个哈希表实现， 所有key 都存储在哈希表内

Node nodes[];

nodes[1] = 10
nodes[2] = 'num'
nodes[3] = table: 00396F20
nodes['k1'] = 'v1'
nodes['k2'] = 20

（2）数组加哈希表实现， 部分整数key 存放在数组，其余key存放在哈希表

Object arrays[];
Node nodes[];

arrays[1] = 10
arrays[2] = 'num'
arrays[3] = table: 00396F20

nodes['k1'] = 'v1'
nodes['k2'] = 20

将部分整数key放在数组部分，显然是为了性能考虑，这里引用一段 官方说明 ：

混合机制有两个优点：

第一：访问整型key的操作会变得更快了，因为不再需要哈希。

第二：更重要的是，数组部分只占原来哈希部分的一半大小，因为哈希部分需要同时存储key和value，而数组部分的key已经隐含在下标了。

结果是，如果一个table是作为数组使用的，它的表现就像数组一样，只要它的整型key是密集分布的。而且，哈希部分没有内存或者时间的代价，因为作为数组使用时，哈希部分不存在。

反过来说，如果table是作为记录使用而非数组，那么数组部分就是空的。这些节省下来的内存是重要的，因为对于Lua程序来说，创建大量小table是很常见的（比如用table来表示object）。

Lua的table也能优雅的处理稀疏数组：语句a={[1000000000]=1}在哈希部分创建了一个键值对，而非一个10亿元素的数组。

数组部分的实现比较简单，主要介绍 哈希部分 的实现。

在《 字符串实现 》一节里介绍了通过哈希表实现字符串池，采用 链地址法 解决hash冲突。在table里采用 开放地址法 解决hash冲突，table类型定义如下：

struct Table {

  struct Node {
    TObject key;
    TObject value;
    Node* next;
  };

  /*数组部分*/
  TObject* arrayData;
  int arraySize;

  /*哈希部分*/
  Node* hashData;
  int hashSize;
  int last_free;
};

• 数组部分存放在arrayData，每个元素为一个 Object

• 哈希部分存放在hashData，每个元素为一个 Node

• Node包括key、value，以及指向 下一个冲突结点 的指针

• last_free表示最后一个 空闲结点 的位置，避免遍历查找

举例说明

（1）有3个结点，key分别为 aa、bb、cc

{'aa', 100}

{'bb', 200}

{'cc', 300}

其中'aa'和'cc'的hash值都为 401 ，产生冲突（ 哈希算法比较差 ），'bb'的哈希码为 402

hashcode('aa') = 401

hashcode('bb') = 402

hashcode('cc') = 401

（2）添加这3个结点到table，Node数组大小为 4 ，根据key的 hash值 计算数组位置

pos_aa = hashcode('aa') % 4 = 1

pos_bb = hashcode('bb') % 4 = 2

pos_cc = hashcode('cc') % 4 = 1

（3）添加'aa'，添加到位置1

hashData[1] = Node{key='aa', value=100, next=NULL}

（4）添加'bb'，添加到位置2

hashData[2] = Node{key='bb', value=200, next=NULL}

（5）添加'cc'， 位置1已经被'aa'占据 ，挑选一个空闲位置，last_free=3，添加到位置3

hashData[3] = Node{key='cc', value=300, next=NULL}

3个结点添加完毕，Node数组为：

hashData[0] = Node {}

hashData[1] = Node{key=' aa ', value=100, next=NULL}

hashData[2] = Node{key=' bb ', value=200, next=NULL}

hashData[3] = Node{key=' cc ', value=300, next=NULL}

（6）由于'aa'和'cc' 冲突 ，'cc'不在其 主位置 上（ 应该在位置1，实际在位置3 ），需要将'aa'和'cc'串联起来，构成 冲突链

hashData[0] = Node {}

hashData[1] = Node{key='aa', value=100, next=&hashData[3] }

hashData[2] = Node{key='bb', value=200, next=NULL}

hashData[3] = Node{key='cc', value=300, next=NULL}

查找'cc'时，先查找位置1，找到'aa'，再根据'aa'的 next 指针找到'cc'。

table结构图：

Part2 获取key值

根据前面的分析，大概了解key的查询方法，流程如下：

• 先确定key 是否在数组 部分，比如数组部分长度为4，若key为 1~4 会在数组部分查找，其余key都在 哈希 部分查找

• 若在数组部分，直接根据 索引 查找。数组部分的扩容，在rehash部分介绍

• 若在哈希部分，先根据key的 hash值 计算其位置，再通过Node的 next 指针遍历冲突链，找到对应key。

关键点在于 如何计算key的hash值 ，key可以为多种类型，需要针对每种类型计算其哈希值。

（1）字符串

字符串对象本身携带hash值，可以直接使用。

（2）数值

整数值可以直接用作hash值。对于浮点数，考虑到小数部分的不同也会影响hash值，可以将小数累加到整数部分

n = 123.456789

hashcode(n) = (n - (int)n) * 1000000 + n = 456912

（3）指针类型

指针本身就是数值，可以直接用作hash值

hashcode(key) = ( long )ptr

总体来说，应尽量利用数据的 每个字节 计算hash值，以达到hash散列的效果。

Part3 修改key值

要修改key的值，需要先找到key所在的位置，这一点和 “获取key值” 原理相同。若找到对应的key，直接修改其value值。

若 没找到 key，添加到 哈希 部分，流程如下：

当 主位置被占用 ，且有 空闲结点 的时候，需要调整结点的位置，流程如下：

这里逻辑有些复杂，举例讲解：

（1）假定Node数组长度为 4 ，先添加key 'aa'，通过hash值计算其主位置应该为 1

Node[1] = 'aa'

（2）添加key 'bb'，恰巧其主位置 也为1 ，由于'aa'在其 正确 位置上，分配最后一个 空闲结点 给'bb'，且建立 冲突链 ，'aa'指向'bb'

Node[1] = 'aa', next->[3]'bb'

Node[ 3 ] = 'bb'

（3）添加key 'cc'，其主位置为 3 ，但'bb' 已经占用 了位置3，由于'bb'的 实际 主位置应该为 1 ，所以需要将 'bb'移走，归还给'cc'

• 通过冲突链，获取'bb'的 前置 结点'aa'

• 分配空闲位置给'bb'，last_free=2

• 'aa'指向'bb'的新位置

• 'cc'存放在其主位置

Node[1] = 'aa', next->[2]'bb'

Node[ 2 ] = 'bb'

Node[ 3 ] = 'cc'

'bb'从位置3挪动到位置2，'cc'使用位置3，在挪动前后，'aa'始终指向'bb'。

关于table的数据存储、读写key的内部实现介绍到这里，下节介绍其余部分的实现， 欢迎留言 发表您的建议！