基于Trie树的哈希表

计算机应用 ›› 2010, Vol. 30 ›› Issue (8): 2193-2196.

基于Trie树的哈希表

史长琼¹,唐铭²,张大方¹,周恺卿¹

1.
2. 长沙理工大学

收稿日期:2010-02-07 修回日期:2010-03-13 发布日期:2010-07-30 出版日期:2010-08-01
通讯作者: 唐铭
基金资助:
湖南省自然科学基金

Hash table based on Trie-tree

Received:2010-02-07 Revised:2010-03-13 Online:2010-07-30 Published:2010-08-01
Supported by:
the Natural Science Foundation of Hunan Province

摘要/Abstract

摘要： 受到AC算法与链式哈希的启发，提出了一种基于Trie树的哈希表。该算法通过增加一个后继状态计数器，能够为后续的查找等运算提供更加简单和快速的信息。分析与实验表明该算法具有较高的效率、较强的稳定性，且降低了能耗。

关键词: AC算法, Trie树, 分离位的串匹配, 链式哈希表, 分段哈希表

Abstract: A Hash table based on Trie-tree was proposed, based on idea the Aho-Corasick (AC) algorithm and the chain-hash. This algorithm, by adding a counter of the subsequent state, could supply simpler and faster information for the follow-up search operations and so on. The analysis and the experiment indicate that this algorithm is of higher efficiency,stronger stability and less energy consumption.

Key words: Aho-Corasick （AC） algorithm, Trie-tree, bitsplit string-matching, chain-hash table, segment hash table

史长琼唐铭张大方周恺卿. 基于Trie树的哈希表[J]. 计算机应用, 2010, 30(8): 2193-2196.

[1]	杜柳青, 许贺作, 余永维, 张建恒. 基于改进SURF算法的柔性装夹机器人快速工件匹配方法[J]. 计算机应用, 2018, 38(7): 2050-2055.
[2]	刘青卫宏儒潘伟. Zodiac算法的碰撞攻击[J]. 计算机应用, 2014, 34(1): 73-77.
[3]	刘丽霞张志强. 基于Trie树的相似字符串查找算法[J]. 计算机应用, 2013, 33(08): 2375-2378.
[4]	张墨华李戈. 基于中间点划分无冲突哈希的高速包处理[J]. 计算机应用, 2012, 32(04): 999-1002.
[5]	吴庆双付仲良. 一种鲁棒的序列图像自动拼接方法[J]. 计算机应用, 2012, 32(02): 499-503.
[6]	张朝伟周焰吴思励林洪涛. 基于SIFT特征匹配的监控图像自动拼接[J]. 计算机应用, 2008, 28(1): 191-194.
[7]	蔡晓妍戴冠中杨黎斌. 改进的多模式字符串匹配算法[J]. 计算机应用, 2007, 27(6): 1415-1417.