推荐最实用功能强大的数据结构(有序HASH树)开发包
1 概述 本文讲述普遍应用在程序开发中快速HASH树数据结构的技术特点、功能描述、应用领域以及性能参数和其他类库的对比。
目前实时处理系统对内存数据结构的普遍有以下要求:
1、功能要求
功能要强大且完备,满足业务功能的需求。
2、性能要求
要能满足实时处理系统对处理速度的需求,同时能长期运行且性能保持稳定
3、系统容量大
要能保持超大规模数据,且在海量数据情况下还能保持优异的性能。
快速HASH树是目前速度最快功能最强大的数据结构,可以满足电信以及其他行业软件开发对数据结构的要求。
2 版权说明
1、 本开发包免费,用户可用于学习、测试、商业用途,本软件没有功能上的限制和使用期限限制,可自由复制、
传播。
2、作者联系方式
e-mail:freeland007@
QQ: 723273055
3 单级HASH树介绍
Hash树数据结构是根据键值插入到树中形成节点,节点保存用户数据,一般情况保存一个结构体或对象的指针,树中的各个
节点再插入后即排序,形成有序的节点多叉树结构。
可以通过以下方式访问树节点以及用户数据
1、可以通过外部提供的值在HASH树中快速定位到唯一树中的节点。
2、可以通过外部提供的值在HASH树中快速定位到符合条件的匹配规则节点。
匹配规则表达式字符串由字符和2种通配符组成,例如以下形式的规则表达式:
1)0755%、138%5678、%5678、%1234%
2)?234567890、12345678??、?23???789?
3)0755%56??、????1234%
通配符为%和?。
通配符%:包含零个或更多个字节的任意字符串。
通配符?:任意单字节字符。
3、 可以通过外部提供的匹配模式字符串在HASH树中定位到符合条件的节点。
说明:本搜索方式和方式2是完全相反的方式,一般情况下可能会有多个节点的键值符合匹配模式,对于符合条件的节
点可以可以指定排序方式顺序访问。
4、 可以在HASH树中定位指定键值长度的节点。
例如:
1)定位键值长度为10字节的所有节点
2)定位键值长度为大于5小于10个字节的所有节点
5、 可以在HASH树中定位键值在某个区域的节点。
例如:
1)返回大于“1234000000”的节点
2)返回小于“1235000000”的节点
3)返回大于“1234000000”并且小于“1235000000” 的节点
6、 用整体遍历的方式访问HASH树中的节点,再遍历时可以指定排序方式,可以按主键的升序或降序顺序遍历
7、 根据指定排序(升、降)方式获取头(尾)节点
8、 根据指定排序(升、降)方式删除头(尾)节点,同时获取头(尾)节点的用户数据(指针)
除了以上的访问HASH树节点方式外,还有以下功能:
1、对于返回多个节点的情况可以指定排序方式(升序、降序)的方式访问节点
例如:上面的方式3、4、5、6
2、对于返回多个节点的情况可以指定访问的最大节点数量
3、 可以再查询HASH树的回调函数中对节点数据经行再处理。
4、根据节点可以获取该节点的用户数据(指针)以及该节点的键值。
4 多级HASH树介绍
如果HASH树中的节点保存的数据是指向另外一个HASH树的指针,如此递归形成一棵多级HASH树,最后一棵HASH树保存用户
数据,一般为结构体或对象的指针。
用户通过插入多个键值插入到多级树的各个HASH树中,也可以通过多个键值删除多级树中指定的节点。多级HASH树采用以
下方式遍历用户数据节点。
从顶层HASH树开始向底层树遍历,对每层次的HASH树可以指定访问树节点的访问方式(参考单级树的访问方式),一致到
最底层数的叶子节点。
开发包访问多级树的API和访问单级树是统一的。
5 运行效率高
1、根据主键精确访问(插入、删除、查询、模式匹配)节点的速度快。
1)在有 1000万节点的HASH树中插入或插入一个节点需要1~2个微秒,相当于50~100万次/秒插入或删除节点操作。
2)在有 1000万节点的HASH树中查找一个节点需要0.3~0.6个微秒,相当于130~300万次/秒查找操作。
2、在按指定排序的情况下获取(删除)头(尾)节点的速度快。
在有 1000万节点的HASH树中删除入一个头(尾)节点需要2~3个微秒,相当于30~50万次/秒删除头(尾)节点操作。
3、对HASH其它操作的指标参考性能指标部分
4、支持超大容量节点
在HASH树有庞大数量节点的情况下,仍然保持高效运行。根据主键精确访问(插入、删除、查询、模式匹配)节点的
耗时与HASH树中节点数量无关,只与键值的长度有关。
5、在频繁插入、删除节点的情况下,系统仍然保持运行稳定,不会出现性能抖动的情况。
6 功能强大
单(多)级HASH树功能强大,可以满足目前应用程序开发中对数据结构功能上的需求,是对目前C、C++标准库强有力的补充
或部分替代功能。
以下是HASH树和MFC中CMAP类的功能比较。
序号 比较功能 快速HASH树 CMAP(MFC)
1 精确查询节点 支持 支持
2 精确删除节点 支持 支持
3 根据匹配模式匹配节点 支持 不支持
4 根据字符串匹配规则表达式节点 支持 不支持
5 查询指定键值长度的节点 支持 不支持
6 查询指定键值范围的节点 支持 不支持
7 支持键值有序(升、降)遍历 支持 不支持
8 支持头(尾)节点操作 支持 不支持
9 根据节点位置获取键值 支持 不支持
10 根据节点位置获取用户指针数据 支持 不支持
11 根据节点位置删除树节点 支持 不支持
12 支持多级(树、MAP)方式 支持 不支持
13 多级(树、表)的功能 支持 N/A
14 其它功能 支持 不支持
具体功能可参考第7章SDK中API函数的功能介绍。
7 快速HASH树SDK介绍
快速HASH树以动态库的形式提供给开发人员,下面介绍常用的API。
1、HANDLE HTreeCreate(LPHTREEDESC pTreeDesc);
功能:生成单(多)级HASH树
2、void HTreeDrop(HANDLE hTree);
功能:删除单(多)级HASH树。
3、int HTreeGetCount(HANDLE hTree);
功能:获取HASH树中节点的数量。
4、int HTreeAddKey(HANDLE hTree, char* sMultiKey[], HANDLE hValue);
功能:根据键值插入一个节点到单(多)级HASH树中。
5、HANDLE HTreeRemoveKey(HANDLE hTree, char* sMultiKey[]);
功能:根据键值在单(多)级HASH树中精确删除相应的节点。
6、HANDLE HTreeGetKeyValue(HANDLE hTree, char* sMultiKey[]);
功能:根据键值在单(多)级HASH树中精确查找相应的一个节点。
7、HANDLE HTreeGetMatchValue(HANDLE hTree, char* sMultiKey[]);
功能:根据外部提供的字符串在单(多)级HASH树中匹配出最精确的规则表达式。
8、HANDLE HTreeGetHead(HANDLE hTree, bool bAsc[]);
功能:在指定树的各级主键排序的情况下,获取头结点的值
9、HANDLE HTreeGetTail(HANDLE hTree, bool bAsc[]);
功能:在指定树的各级主键排序的情况下,获取尾结点的值
10、bool HTreeGetHeadPosition(HANDLE hTree, bool bAsc[], HANDLE hNodeSet[]);
功能:在指定树的各级主键排序的情况下,获取各级树在指定排序情况下头结点,并把各级头结点保存到节点数组中。
11、bool HTreeGetTailPosition(HANDLE hTree, bool bAsc[], HANDLE hNodeSet[]);
功能:在指定树的各级主键排序的情况下,获取各级树在指定排序情况下尾结点,并把各级尾结点保存到节点数组中。
12、HANDLE HTreeRemoveHead(HANDLE hTree, bool bAsc[]);
功能:在指定树的各级主键排序的情况下,删除头节点,并返回头节点句柄值。
13、HANDLE HTreeRemoveTail(HANDLE hTree, bool bAsc[]);
功能:在指定树的各级主键排序的情况下,删除尾节点,并返回尾节点句柄值。
14、 HANDLE HTreeRemoveAt(HANDLE hTree, HANDLE hNodeSet[]);
功能:根据各级树种的节点,删除指定叶子节点
15、void HTreeGetNodeKey(HANDLE hTree, HANDLE hNode, char* sKey);
功能:根据节点获取节点对应的键值
16、HANDLE HTreeGetNodeValue(HANDLE hTree, HANDLE hNode)
功能:根据节点获取节点对应的句柄值
17、void HTreeRemoveAll(HANDLE hTree);
功能:一次清除HASH树中的所有节点
18、 int HTreeSelect(LPSELECTCOND pSelectCond);
功能:此函数用来根据指定的条件访问单(多)级HASH树中的节点,此函数功能强大,可以指定访问各级子树的访问方
式,对于满足访问条件的节点可以由用户编写的回调函数处理。
19、void HTreeGetCurrentPosition(LPSELECTCOND pSelectCond, HANDLE hNodeSet[]);
功能:此函数在执行HTreeSelect中的回调函数中使用,用来获取当前各级子树节点,并保存在节点数组中。
20、HANDLE HTreeGetCurrentValue(LPSELECTCOND pSelectCond);
功能:此函数在执行HTreeSelect中的回调函数中使用,用来获取当前节点的句柄值。
其它功能函数:略
8 HASH树行业应用
快速单(多)级HASH树已经广泛应用到可应用于多个行业软件开发领域,特别适合于超大规模信息的实时处理的情况。
8.1 电信实时处理系统
1、电话(手机)号码路由
2、电话号码区号匹配
3、手机号码归属地查询
4、手机短信违禁词过滤
5、电话(手机)号码黑白名单查询过滤
6、号码路由
7、订购关系处理
8、实时鉴权系统
9、实时计费系统
8.2 互联网应用
1、高效数据库缓存服务器
2、产品编码查询
3、身份查询
4、网络游戏服务器
5、域名系统
6、路由查询
7、邮件系统
8.3 实时处理系统
1、实时监控系统
2、数据采集系统
3、跟踪系统
8.4 内存数据库系统
内存数据库的其中之一的核心数据结构式内存数据库表,而索引时其中最重要部分,内存数据库的索引可选择HASH树可
作为内存数据库的索引数据结构。
9 运行环境
1、windows 2000、windows 2003、windows XP
2、linux
3、unix(solarix、HP-UX、AIX等)
10 性能指标
10.1 测试环境
1、 操作系统:windows xp professional
2、 内存:1G /DDR2
3、 CPU:AMD LE1100/1.9GHz
10.2 单级HASH树的性能指标
测试条件:
1、单级HASH树
2、树中有100万节点,节点的键值从123456780000000000到123456780000999999
测试项目:
1、插入节点
插入100万节点到HASH树中,节点的键值从123456780000000000到123456780000999999,耗时2.140秒。
2、根据键值精确删除节点
从HASH树中根据键值删除100万节点,节点的键值从123456780000000000到123456780000999999,耗时2.172秒。
3、根据键值精确查询节点
根据键值从HASH树中精确查询100万节点,节点的键值从123456780000000000到123456780000999999,耗时0.610秒。
4、整体遍历
遍历HASH树中的100万节点,节点的键值从123456780000000000到123456780000999999,耗时0.062秒。
5、删除头(尾)节点
用删除头(尾)节点的方式删除HASH树中的100万节点,节点的键值从123456780000000000到123456780000999999,耗
时2.600秒。
6、清除HASH树中所有节点
一次清除HASH树中的所有100万节点,节点的键值从123456780000000000到123456780000999999,耗时0.100秒。