| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 656 人关注过本帖
标题:推荐最实用功能强大的数据结构(有序HASH树)开发包
只看楼主 加入收藏
freeland007
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2009-8-19
收藏
 问题点数:0 回复次数:1 
推荐最实用功能强大的数据结构(有序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秒。
搜索更多相关主题的帖子: 推荐 开发 数据结构 HASH 
2009-10-18 14:53
cosdos
Rank: 9Rank: 9Rank: 9
来 自:ShangHai
等 级:蜘蛛侠
威 望:6
帖 子:2109
专家分:1385
注 册:2007-6-19
收藏
得分:0 
没东西 ?????

—>〉Sun〈<—
2009-10-20 17:38
快速回复:推荐最实用功能强大的数据结构(有序HASH树)开发包
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017552 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved