Lua table 内部实现(上)

栏目: Lua · 发布时间: 1年前

来源: mp.weixin.qq.com

内容简介:这一节介绍Lua唯一的数据结构table充分体现了Lua语言的特点,用最简练的语法表达丰富的信息,但也增加了用户的理解成本。table包含本文展示的代码来自llamavm,并非Lua源码,C++版本的实现比较容易理解。

本文转载自:https://mp.weixin.qq.com/s/ROBotfUvnjehTGlDp-EZ9w,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有。

这一节介绍 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结构图:

Lua table 内部实现(上)

Part2 获取key值

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

Lua table 内部实现(上)

  • 先确定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,添加到 哈希 部分,流程如下:

Lua table 内部实现(上)

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

Lua table 内部实现(上)

这里逻辑有些复杂,举例讲解:

(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的内部实现介绍到这里,下节介绍其余部分的实现, 欢迎留言 发表您的建议!


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

关注码农网公众号

关注我们,获取更多IT资讯^_^


查看所有标签

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

界面设计模式

界面设计模式

[美]泰德维尔(Tidwell,J.) / 蒋芳 / 电子工业出版社 / 2013-9-1 / CNY 119.00

模式意味着重用。 好的模式建立在对人与事物的深刻认知之上。 本书开篇即总结了“与人有关”的各类问题,为读者提供了界面设计总体思路上的指引,帮助读者举一反三。 接下来,本书收集并分析了很多常用的界面设计模式,帮助读者理解在实现级别的各种常用解决方案,将它们灵活地运用到自己的设计中。 同时,随着网络和技术的不断发展,本书在第1 版的基础上,更新了几乎所有的模式示例和说明,并新增......一起来看看 《界面设计模式》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

SHA 加密
SHA 加密

SHA 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换