Lua中table的实现

Stella981
• 阅读 1018

本文来自《Lua设计与实现》的阅读笔记,推荐Lua学习者可以购买一本,深入浅出讲解lua的设计和实现原理,很赞,哈哈

Lua中对于表的设计,是基于数组和散列表,和其他语言不同,对于数组的下标是从1开始的,对于散列表而言,只要其键值补位nil,都可以存储在其中。

一、table的基本类型定义

首先看看table的数据定义,参考源码lobject.h

Lua中table的实现

CommonHeader, 参看专栏前面的文章;

flags 这是一个lua的byte类型的数据,用于表示表中提供了哪些元方法,比如是否提供了元方法_index,该数据最开始设置为1,如果进行查找一次,比如_index,如果存在,这该元方法对应的flag bit设置为0,在下一次查找的时候,只需要比较这个bit即可,对应的元方法在ltm.h中

Lua中table的实现

lsizenode,为散列表的大小,必定为2的幂对应的数字;

metatable,该table的元表;

array,该table的数组的指针

node, 该table的散列表的起始位置的指针;

lastfree, 该散列表的最后位置的指针

gclist, gc相关的链表

sizearray, 数组的大小,不一定为2的幂对应的数字

对于node数据,类似于其他语言中的字典设计\hash设计,就是一个键值对集合,其定义为:

Lua中table的实现

需要提一下的是对于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:

Lua中table的实现

基本的实现过程看源代码写的比较详细,这儿说一下rehash部分的操作,在ltable.c中:

Lua中table的实现

  1. nums中存放的是元素的数量

2)分表遍历数组(numusearray)和散列表(numusehash),统计更新nums中的数量大小

  1. 重新计算数组和hash部分的大小,数组大小的计算规则:逐个遍历nums数组,获得其范围区间内所包含的整数数量大于50%的最大索引,作为rehash后的数组大小,这个索引值来自与computesizes函数:

Lua中table的实现

可能看了会有点迷糊,那我就用大白话说一下吧:

首先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

查找表中散列表长度,算法同数组部分

对于表中只有散列表的时候,其实质就是对键值为正整数的部分进行长度操作,如果既有数组,又有散列表,则优先对数组部分进行长度操作

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Wesley13 Wesley13
3年前
lua中的table
1、table是lua中最重要的数据类型。2、table类似于python中的字典。3、table只能通过构造式来创建例1:Lua代码 mytable{a10,b11,c20,ddd30} print(mytable\"a"\) 
Stella981 Stella981
3年前
Bypass ngx_lua_waf SQL注入防御(多姿势)
0x00前言ngx\_lua\_waf是一款基于ngx\_lua的web应用防火墙,使用简单,高性能、轻量级。默认防御规则在wafconf目录中,摘录几条核心的SQL注入防御规则:select.(from|limit)(?:(union(.?)select))(?:from\Winformation_schema\W)这边
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
为什么mysql不推荐使用雪花ID作为主键
作者:毛辰飞背景在mysql中设计表的时候,mysql官方推荐不要使用uuid或者不连续不重复的雪花id(long形且唯一),而是推荐连续自增的主键id,官方的推荐是auto_increment,那么为什么不建议采用uuid,使用uuid究
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这