注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

偶有所得,记录在此

有分享交流才有进步,永远不要固步自封

 
 
 

日志

 
 

Lua Table 内部实现解析  

2012-07-19 10:22:19|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
基本特点
  • 语法上,不像其它语言区分 List 和 Dict,Lua Table 可以直接存储 List 数据 or Dict 格式数据,甚至这两种类型的数据混合出现都是允许的。如下:

    days = {"Sunday", "Monday", "Tuesday", a=1, b=2}

    table 内部数据结构,也是 Array 和 Hash Table 的结合体,如下:
    typedef struct Table {
     ...
     TValue *array;  /* array part */
     Node *node;
     Node *lastfree;  /* any free position is before this position */
     ...
    } Table;

  • table 的 array 部分可以解决 list 类型数据快速访问问题,但 list 类型数据并非一定存储在 array 里面,也可能在 hash table 内。
  • 一个 table 所占用的空间,按功能分可以分为 3 部分:table 结构、array部分 、hash table部分。

如何处理 hash 冲突

按照教科书的讲法,lua 的哈希表以闭散列方式实现。
向 hash table 里面插入一个元素的步骤如下:
  • 在 hash table 里面找到一个空闲的节点(具体怎么找不谈,假定一定可以找到)
  • 计算将要插入的元素的 hash 值,根据该 hash 值确定该元素应该 hash 到的目标节点。这个节点有三种情况:
    1. 若该节点空闲,该元素直接存储在该节点
    2. 若该节点被占用,并且占用该节点的元素按照 hash 算法也确实应该被 hash 到该节点,则把当前元素存储在第一步获取的空闲节点里面,将携带当前元素的节点链表形式链接在冲突节点上。hash 冲突的元素可以通过链表遍历。
    3. 若该节点被占用,但占用该节点的元素按照 hash 算法不应该在当前节点,则将冲突元素的值赋值给第一步获取的空闲节点并链到原本属于它的位置,让出当前节点,将待插入的元素赋值给当前节点。

array 部分扩容策略
array 的大小为 2 的整数幂次,不论扩容还是缩小。
算法很简单:从数组第一个元素开始算,至到最后一个元素,算出满足 >= 50% 使用率的最大 size ,当然这个 size 是 2 的整数次幂,如果是扩容就意味着新申请的空间为原来的2倍。

 
hash 部分扩容策略
计算出除去 array 部分,剩余元素所需要的空间数量,然后申请 2 倍容量的空间,旧元素重新 rehash 到新申请的空间上。
  评论这张
 
阅读(4164)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017