基于暴雪的哈希算法,实现可扩展的哈希表

你条草 发布于 2012/04/11 16:52
阅读 1K+
收藏 2

前提:基于暴雪的哈希算法,http://www.oschina.net/code/snippet_99767_1217

这里参考了RyanLee的代码,想基于这个源码,实现可扩展的哈希表。

查看源代码后,发现能够将哈希表上的所有空间都填满,经过测试当hash表的长度为1024*1024,所有hash值的查找平均耗时是2毫秒,最长查找耗时是16毫秒,空间,效率上都能满足我的要求。

 

但存在一个较大的问题,该哈希表结构,不支持动态扩展。

后来想到个扩展该哈希表结构的方式。

 

假设哈希表的数据结构如下,

 

struct Hash_Table

{

       Hash_length; //哈希表的总长度

       Hash_count; //哈希表空余项的计数

       Check_code; //当前哈希表的数据检验码

       Hash_Table* nextTable;    //链接下一个哈希表

}

 

若插入新的hash值时,当 Hash_count < Hash_Length 时,通过一系列运算,得到新的Check_code,此Check_code能够检验当前已经存在于Hash_Table的所有hash值,之后按照RyanLee的代码,进行Hash_Table表的数据插入。

 

一旦当前Hash_Table表,已经填满,即 Hash_count == Hash_Length 。此时通过新建一Hash_Table,Hash_Table之间的连接可通过链表实现。再根据上述方式插入新增的hash值。

 

在进行数据查找的时候,获取对应的Hash值,之后通过每个Hash_Table所对应的动态数据检验码Check_code,来进行校验,确定Hash值所在的Hash_Table,再按照RyanLee的代码,查找对应的数据内容。

 

 

问题:

是否存在类似的算法,基于一个集合内的所有动态数值,产生一个校验码,该校验码能够确定一个外部数值,是否存在于该集合。

当集合内的某个数据进行删除之后,更新校验码,该校验码能够排除已经删除的数据。

 

 

 

 

 

加载中
0
中山野鬼
中山野鬼
能做。但是计算量不保证。类似香农定义一样,你的数值想描述全体数据集合的特性,那么你在更新这个数值时,仍然需要对全体集合进行遍历处理。是否采用在于数据库的数据是查询的多还是修改的多。对于满库,确认是否存在是有利的,因为库的内容不做变动。对于运行态的库,在不停的插入和删除,你就不能完了。老实点,该查的时候,就遍历把。
0
你条草
你条草

受教啦!因为这个hash表的信息,其实是存储于文件上的,目前考虑到的只能是通过合并hash表的方式啦,遍历难免啦。

程度比较低,看过其他扩展hash的方式,因为能以确保空间利用率的问题……所以想在这个相对紧凑的利用空间的形式上扩展!

0
中山野鬼
中山野鬼

引用来自“你条草”的答案

受教啦!因为这个hash表的信息,其实是存储于文件上的,目前考虑到的只能是通过合并hash表的方式啦,遍历难免啦。

程度比较低,看过其他扩展hash的方式,因为能以确保空间利用率的问题……所以想在这个相对紧凑的利用空间的形式上扩展!

你得搞清楚,用HASH的目标是什么。不同任务目标,虽然可能核心HASH映射算法完全一样,但是展开的整体就完全不一样。没有哪个算法就是好的。关键看任务。我搞明白,客户才是老大,就是因为我一直做算法优化,后来发现,优化不代表快(给予正确下)有的目标就是要慢。哈。
0
你条草
你条草
其实我是实现一个基于中文分词记录的搜索,hash也是最近才接触的!原来是算法大牛,失敬啦!
0
中山野鬼
中山野鬼

引用来自“你条草”的答案

其实我是实现一个基于中文分词记录的搜索,hash也是最近才接触的!原来是算法大牛,失敬啦!
分词只是语法分析,但是还有语义分析。是两个工作。千万别混一块去了。而且他们不是单射的。双射更不谈。也就是,语法分析完毕后,两个元素,他们的距离远近和语义分析后的远近没有联系。可能同样落入语义某个元素对应的语法元素差异很远。奇异也是这样产生的。完全消除奇异是不现实的。但通过增加词汇的前后关联,则可以提高语义的准确性。
0
你条草
你条草

引用来自“中山野鬼”的答案

引用来自“你条草”的答案

其实我是实现一个基于中文分词记录的搜索,hash也是最近才接触的!原来是算法大牛,失敬啦!
分词只是语法分析,但是还有语义分析。是两个工作。千万别混一块去了。而且他们不是单射的。双射更不谈。也就是,语法分析完毕后,两个元素,他们的距离远近和语义分析后的远近没有联系。可能同样落入语义某个元素对应的语法元素差异很远。奇异也是这样产生的。完全消除奇异是不现实的。但通过增加词汇的前后关联,则可以提高语义的准确性。
分词,是用人家的源码来实现……我那个不需要太强的语义,基本上基于原始词语来进行搜索就ok……大牛果然专业,奈何公司就我一个做这个项目…… 
0
中山野鬼
中山野鬼

引用来自“你条草”的答案

引用来自“中山野鬼”的答案

引用来自“你条草”的答案

其实我是实现一个基于中文分词记录的搜索,hash也是最近才接触的!原来是算法大牛,失敬啦!
分词只是语法分析,但是还有语义分析。是两个工作。千万别混一块去了。而且他们不是单射的。双射更不谈。也就是,语法分析完毕后,两个元素,他们的距离远近和语义分析后的远近没有联系。可能同样落入语义某个元素对应的语法元素差异很远。奇异也是这样产生的。完全消除奇异是不现实的。但通过增加词汇的前后关联,则可以提高语义的准确性。
分词,是用人家的源码来实现……我那个不需要太强的语义,基本上基于原始词语来进行搜索就ok……大牛果然专业,奈何公司就我一个做这个项目…… 
谈不上专业。那你的事情简单点了。搞点类似遗传收缩算法的,自适应学习折腾语义应该可以糊弄过去了。
返回顶部
顶部