加载中…
个人资料
水龙一谭
水龙一谭
  • 博客等级:
  • 博客积分:0
  • 博客访问:73,469
  • 关注人气:21
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

在 matlab 中仿拟使用 hash 的几种方法

(2015-03-05 18:33:35)
标签:

it

matlab

分类: 写代码
在 matlab 中仿拟使用 hash 的几种方法
七阶子/2015-3

用 matlab 多年,才意识到 matlab 语言没有 hash 这种数据结构。这也难怪,毕竟
matlab 的本源就是数学计算工具。因此在 matlab 中基础运用中很少需要用到像其他系
统语言相当重要的 hash 数据结构。

hash ,音译哈希,意译散列表。hash 有两个重要的思想,其一是用键名(一般是有意义
的字符串名称)表索引值,即建立键与值的关联对应关系,也因此有些言称之为关联数组
。其二是快速索引,希望能接近用整数下标索引数组的速度,即与数据量无关,有O(1)的
随机索引时间复杂度。

matlab 的基本数据结构是矩阵,即多维数组,但没有类似 hash 的数据结构。但若想利
用 hash 的思路来组织一些算法,这里介绍几种实现方法。

1. 结构的动态域

matlab 的结构 (struce) 支持动态增加域,在对新域赋值时自动扩展,而且可以用变量
表示域名,其语法表示简单直观。常规索引域的语法表示为 struct.field ,如果是变量
域名,则表示为 struct.(fieldvar) ,即在点号后用括号将变量括起来,matlab 就先会
计算出括号的变量,用该变量的值作为结构的域。

如果用键来表示域,就可用结构实现简单的 hash 功能。如:
hash = struct;
hash.key = setval;
getval = hash.key;
其中 key 是一个确定的可用字面字符表示的键。或者用一个变量 keyvar 来表示一个未
确定的键:
hash.(keyvar) = setval;
getval = hash.(keyvar);
然后,也有 rmfield 函数用于删除结构的域。

用这种方法很简单,但要注意两个问题。一是键只能用常规字符串,即不能包含特定字符
,要求是可以作 matlab 标识符的字符串。二是重访速度可能并不高。因为 matlab 保持
了结构内容的域顺序,用 fieldnames 函数返回的域名与添加顺序是一致的。这说明它对
域索引可能是线性查找的,没有随机索引的速率。这并不难理解,因为 matlab 设计
struct 的初衷,只是想要将相关的数据组织在一起,并不期望用户动态地插入大量域。

2. 简单的两行 cell 数组

为解决上述 struct 山寨的 hash 不能使用特殊字符作键名的问题,可以用 cell 来保存
键名与键值。比如两行的 cell 数组,2*n 维度,表示 hash 表中的 n 个元素,第一行
cell 保存键名,第二行 cell 保存键值。

显然这种存储结构,对键的索引也只能是线性查找,只适合元素较小的应用场合下。

3. 具有 hash 值分配的 cell 列表

按 hash 表的思想,可用一个 m*1 维度的 cell 向量来表示。将键通过一个 hash 算法
得到 hash 值(一般是个大整数),对向量长度 m 取模后,即将一个元素映射到一个
cell 中。

虽然 hash 算法在理论上几乎是将不同的键计算为不同的 hash 值,但由于 hash 表的长
度有限,所以必须解决冲突问题。即不同的键有可能映射到相同的单元格 cell 中。所以
这个 m*1 的 cell 列向量,不是简单的内容,而是应该存储多个元素(键值对),可用
上面一节的两行 cell 数组表示。

所以整个 hash 表表示为嵌套的 cell 数组。可想象为 m*1 列向量的每个 cell 内容又
是另一个独立的 2*n 的 cell 数组。每个内嵌 cell 的长度 n 是参差不齐的,而且都应
该很短,否则就需要为 hash 表扩容了,即增大外层 m*1 列向量的长度 m,并将所有元
素重新 hash ,这样才能保证重访索引的高速化。

在 <wbr>matlab <wbr>中仿拟使用 <wbr>hash <wbr>的几种方法


如果真的需要经常在 matlab 中用到 hash 表,还可以将这个 cell 数组封装为 matlab
的类,并且最好也为该类实现重载索引,使之用起来更方便,更像 hash 表。

0

阅读 评论 收藏 禁止转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有