本文来自《Lua设计与实现》的阅读笔记，推荐Lua学习者可以购买一本，深入浅出讲解lua的设计和实现原理，很赞，哈哈
Lua中对于表的设计，是基于数组和散列表，和其他语言不同，对于数组的下标是从1开始的，对于散列表而言，只要其键值补位nil，都可以存储在其中。
一、table的基本类型定义
首先看看table的数据定义，参考源码lobject.h
CommonHeader, 参看专栏前面的文章；
flags 这是一个lua的byte类型的数据，用于表示表中提供了哪些元方法，比如是否提供了元方法_index，该数据最开始设置为1，如果进行查找一次，比如_index，如果存在，这该元方法对应的flag bit设置为0，在下一次查找的时候，只需要比较这个bit即可，对应的元方法在ltm.h中
lsizenode，为散列表的大小，必定为2的幂对应的数字；
metatable，该table的元表；
array，该table的数组的指针
node, 该table的散列表的起始位置的指针；
lastfree, 该散列表的最后位置的指针
gclist， gc相关的链表
sizearray， 数组的大小，不一定为2的幂对应的数字
对于node数据，类似于其他语言中的字典设计\hash设计，就是一个键值对集合，其定义为：
需要提一下的是对于key的设计采用的是union，也就是说Lua的散列表的key，可以为nk对应的struct，也可以是TValue类型
二、table相关的操作的实现原理
1、查找算法的实现原理
借用原文的伪代码：
if 输入的key为整数 && key >= 0 && key <= 数组的大小
尝试在数组部分查找
else 在散列表部分查找
计算出该key的散列值，据其查找对应的node所在散列表中的位置，然后遍历其对应的链表，查找是否有该key对应的元素
举例：
local t = {}
t[1] = 0
t[100] = 0
那么1是在数组中查找，100就是在散列表中去查找了（100大于数组的len）
2、新增元素的实现原理
给lua中添加新元素的时候，会有可能触发重新分配table中的数组和散列表，其本质来自于散列表的rehash（由于lua对于下标超过数组的大小的数字，都会存储在散列表部分去，所以数组部分的插值不会触发rehash）
散列表的组织，就是多个mainposition，每个单独的mainposition会对应一个数据链表，当插入一个key的时候，会调用luaHset\luaH_setnum\luaH_setstr，来获得该key对应的TValue指针，如果没有，则调用内部的newkey函数来分配一个新的key：
基本的实现过程看源代码写的比较详细，这儿说一下rehash部分的操作，在ltable.c中：
1) nums中存放的是元素的数量
2）分表遍历数组(numusearray)和散列表(numusehash)，统计更新nums中的数量大小
3) 重新计算数组和hash部分的大小，数组大小的计算规则：逐个遍历nums数组，获得其范围区间内所包含的整数数量大于50%的最大索引，作为rehash后的数组大小，这个索引值来自与computesizes函数：
可能看了会有点迷糊，那我就用大白话说一下吧：
首先nums数组在统计后，每个下标对应的是处于当前2^(i -1) - 2^i中的元素的个数，然后不断的累加计算，求得满足 sum > 2^n/2的最大下标值(这个下标值是nums数组中的)
所以，在不同的rehash阶段，table中的同一个key可能会在数组部分和散列表部分交替出现，也是可能的。
由于rehash会带来较大的性能消耗，所以一般都尽量避免，比如在创建表的时候，就采用预填充的算法
3、取长度算法的原理
如果table中元表没有重载len方法，则调用的是luaH_getn方法，其基本的伪代码为：
if 表中存在数组部分：
初始化i = 0, j = sizearray
while(j - i > 1){
m = (j + i)/2
if(array[m-1] == nil)
j = m
else
i = m
}
return i
else
查找表中散列表长度，算法同数组部分
对于表中只有散列表的时候，其实质就是对键值为正整数的部分进行长度操作，如果既有数组，又有散列表，则优先对数组部分进行长度操作
请发表评论