哈希表的应用发表的论文

哈希表（散列表 Hash）是相对于线性表、树形结构的一种数据结构，它能在元素的存储位置和其关键字直接建立某种之间关系，那么在进行查找时，就无需做或者做很少次的比较，就能通过这个关系直接由关键字找到对对应的记录。这就是散列查找法（Hase Search）的思想，它通过对元素的关键字值进行某种运算，直接求出元素的地址。即使用关键字到地址的直接转换方法，而不需要反复比较。因此，散列查找法又叫杂凑法或者散列法。 选择一个好的散列函数可以在一定程度上减少冲突，但在实际应用中，很难完全避免发生冲突，所以选择一个有效的处理冲突的方法是散列表的另一个关键问题。 处理冲突的方法与散列表本身的组织形式有关。按组织形式的不同，通常分为两大类：开放地址法和链地址法。 开放地址法的基本思想是：把记录都存储在散列表数组中，当某一记录关键字key的初始散列地址H0=H(key)发生冲突时，以H0为基础，采取合适方法计算得到另一地址H1，如果H1仍然发生冲突，已H1位基础再求下一个地址H2，若H2仍然冲突，再求得H3，以此类推，直至Hk不发生冲突为止，则Hk为该记录在表中的散列地址。 根据计算方法，可以分为以下三种探测方法： 线性探测法会在出现在处理过程中发生冲突的发生第一个散列地址不同的记录争夺同一个后继散列地址的现象，称为二次聚集或者堆积。即在处理同义词的冲突过程中，又添加了非同义词的冲突。 它的优点是，只要散列表未满，就一定能找到一个不发生冲突的地址 而二次探测法和伪随机数探测法可以避免出现二次聚集现象，但是不保证一定能找到不发生冲突的地址。 链地址法的基本思想是：把具有相同散列地址的记录放在同一个单链表中，称为同义词链表。有m个散列地址就有m个单链表，同时用数组HT[0..m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点的方式插入已HT[i]为头结点的单链表中。

[摘 要]随着计算机处理能力的不断增强,特别是网络技术的迅速发展,不同主机之间的资源共享问题成为研究的热点。对等网络(Peer-to-Peer,简称P2P)作为一种完全分布的计算模型,可以脱离中央服务器实现对等节点间的直接通信,从而充分利用每个网络节点自身的资源,实现整个网络计算资源的充分利用和信息资源的高效共享。在对等网络的众多研究领域中,关于查找算法的研究具有核心地位。本文对现有对等网络查找算法中的以Chord为代表的结构化分布式查找算法,然后在Chord数学模型的基础上,提出了Chord查找算法的改进方法。 [关键词]资源共享 P2P 分布式哈希表 Chord [中图分类号]G[文献标识码]A[文章编号]1007-9416(2010)02-0054-03 1 背景及意义 资源共享是现代信息和通信技术的目标所在,当今互联网世界,用户数目正在以惊人的速度增加,同时随着互联网技术的发展以及信息的迅速膨胀,全球信息已经进入以计算机网络为核心的时代。越来越多的机器获得了网络连接。如果把网络上数量巨大的个人计算机作为一个整体联系起来,就可以提供任何集中式服务器无法比拟的计算资源。其中以信息资源共享为目的对等网络技术成为了研究热点。 自从DHT协议出现以后,结构化P2P的应用得到了快速的发展。目前主流的查询算法是采用分布式哈希表(DHT)技术,这也是目前扩展性最好的P2P路由算法之一,并且衍生出了不同的DHT路由几何结构,如树型结构,超立方体结构、环型结构等等,并且这些不同的几何结构都有各自的路由查询算法。 Chord是典型的分布式结构化网络模型,Chord协议解决键值如何定位问题,新节点怎样加入系统,如何从节点失效中恢复。Chord的核心功能就是提供快速的哈希函数(一般为一致性哈希)进行分布式计算,将节点和资源(键值)映射到一维环形空间上,再进行路由查找。Chord协议具有的特点是:负载均衡;对于一个包含N个节点的网络,查找复杂度为O(logN),适合应用于较大的系统;在有节点加入或者退出时,能进行自动调整;对其查询的键值的结构没有约束。 对等网络中的资源都分散在各个不同的节点上,数据的传输和服务的实现都直接在众节点间进行,在此过程中并不需要中间环节或者服务器的介入,避免了瓶颈。在混合P2P模式中,服务器也仅仅承担查找资源,定位节点或安全检验等环节,主要的数据交换最终还是在各个节点间直接进行,虽然这样大大的减轻了服务器的负担,但是由于资源的位置信息存储在服务器上,一旦服务器失效将会使整个系统瘫痪。而在结构化对等网络中,所有的节点既是服务器又是客户端,每个节点既存储资源又存储路由信息,任何一个节点的失效都不会对系统产生较大的影响。如何对资源进行合理的分配,如何进行资源的快速定位,以及当有节点退出或者加入时如何通知网络中的其他节点是结构化对等网络面临的首要问题。作为典型的分布式结构化网络模型,Chord比较好的解决了上述的问题,保证了负载的均衡,并且查询信息中转的复杂度控制在节点总数的对数级内,比较有效的控制了路由的跳数。本文针对现实世界中,单个节点的性能千差万别,性能好的节点完全有能力多分担网络的负载,以此对Chord模型进行了相应的改进。在继承Chord模型的优点上,提高了Chord系统中的查询效率。 2 基于P2P资源共享系统的关键技术 2.1 Chord中DHT技术思想 DHT的主要思想是:首先,每个对象被表示成一个(K, V)对,K称为关键字,可以是文件名(或文件的其他描述信息)的哈希值,V是实际存储文件的节点的IP地址(或节点的其他描述信息)。所有的对象(即所有的(K, V)对)组成一张大的哈希表,只要输入对象的K值,就可以从这张表中查出所有存储该文件的节点地址。然后,再将上面的大哈希表分割成很多局部小块,按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节点上,使得每个节点负责维护其中的一块。这样,节点查询对象时,只要把查询报文路由到相应的节点即可(该节点维护的哈希表分块中含有要查找的(K,V)对。这里面有个很重要的问题,就是节点要按照一定的规则来分割整体的哈希表,进而也就决定了节点要维护特定的邻居节点,以便路由能顺利进行。Chord协议采用DHT技术,利用一致性哈希函数,来分隔整体的哈希表。 2.2 Chord算法改进 Chord搜索算法,由简单的到可扩展的,可扩展的Chord算法使Chord性能得到提高,它类似于二分法,它的每个节点都维护了少量的路由信息,通过这些路由信息来提高查询的效率。能否用尽可能少的次数来查找到资源的所在节点将影响查询的性能。但Chord这种算法是建立在Chord网络中没个节点的地位都是绝对平等的,而现实世界中,由于计算机的性能千差万别,对于某些性能较差的节点,Chord协议分配给它的负载可能使它无法流畅运行这势必会造成搜索信息到达此节点时的搜索延迟。相反,对于一些性能较好的节点,Chord协议分配给它的负载不能充分发挥其性能。为此本科对现有的Chord搜索算法进行改进,使Chord环中性能较好的节点能够保存更多节点的信息,而又不会使其占用太大的空间,以此来减少搜索信息被中转的路由跳数,提高资源搜索的效率。 节点的权值可以通过节点计算机的一些性能参数来计算,用NodeValue来表示权值,计算公式为: NodeValue=min{PP,OT,NC}*216+(PP+PT+NC)/3 PP,PT,NC∈[0,216) 其中,PP是PC Performance表示计算机性能,OT是Online Time表示节点进入P2P网络的在线时间,NC是Network Connection表示网络连接情况。根据文献的结论,Gnutella中的节点在线的时间越长,那么它的停留时间也越长。根据这个特性,水桶定律设计出来的hash函数能够保证NodeValue越大的节点越能承担负载。 通过NodeValue权值的大小来判断,给予性能较好的节点较多的负载,在合理的范围内(如只需要其多保留一个前驱和一个后继节点上的路由信息)使其为保存更多路由信息,提高搜索消息在其路由表中查找信息的成功率。改进的模型图可以抽象的按下图理解: 图1中,NodeValue大的节点,除保留Chord协议分配的负载外,根据NodeValue的级别,多保留一个(或多个)前驱或后继的finger table。当NodeValue值较大的节点,接收到搜索消息后,除了能路由到本身的finger table 还能不经过后驱节点的转发,直接搜索后驱节点的finger table,提高了查询效率。改进后的Chord协议中节点如何加入网络,路由表如何维护,将在系统设计章节中将近一步说明。 2.3 底层协议优化 2.3.1 UDP协议的缺点及改进 网络协议是为了实现一个特定目的的工作组的互联,一个高质量的工作组(或一个自组织网络中)的网络属性有如下几点: (1)高速数据交换。 (2)可靠的数据传输。 (3)支持广播。 (4)支持大数据块的数据交换。例如初始化系统环境可能需要这样的大数据块。 (5)点对点网络。任意一个节点可以作为数据源和数据目标。 本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 事实上,绝大多数平行计算机软件,都是使用标准的网络协议TCP/IP。使用标准网络协议的弊端有: (6)数据交换速度低。TCP的可靠性是被首先强调的,这也是因为它需要适用于不稳定的Internet环境。但是在一个稳定(或者相对稳定)的网络体系中,它的速率低的弊端就暴露无遗。 (7) TCP不支持广播。UDP不支持广播,但是UDP是不可靠报文协议并且报文大小受限制。 (8) 数据传输之前需要建立逻辑链路。 (9) TCP是基于数据流的协议,但是对一些特定的要求,更适合一个固定块的数据交换,因此这样能把一个确定的、所有数据、必要的操作标志,一次性发送。 因此可以改进标准协议使它能具有高速消息传输、支持大数据块数据传输、接受到消息后作相应反应/操作等能力。本文成为CTP,虽然字母“P”表示“协议”,但它并非这一特指。CTP是理论与工具的综合,可以当成一种“工具”使用。因此它能代替类似MPI、PVM。 大多数用于平行计算的现有工具都以消息作为抽象,这种抽象在CTP中称为命令。命令是一个从某节点到另一节点做指定事情的序列。这种命令需要具有三种属性,发送者、接收者与相应的操作。为满足P2P网络需求CTP协议以UDP/IP模型为参照。因为IP被广泛使用且能满足唯一标识一个节点。CTP/IP模型与UDP/IP模型、OSI模型的关系如图2。 我们可以看出CTP包含了从传输层到应用的几个层次,它的职能从相对底层一直到高层。 2.3.2 Nat穿透 IP地址分为两类,一类是可供内网重复使用的私有IP地址,内网以外的主机无法直接访问这些IP地址。另一类是共网IP地址,能直接被其它主机访问。NAT/NAPT(Network Address Translation/Network Address Port Translator) 允许多台机器使用一个,H地址访问因特网。通常,从为内部网保留的地址块中为NAT网关后面的机器分配一个IP地址。NAT网关是该网络中唯一拥有因特网可访问IP地址的机器。NAT网关透明地重写来自内部网上机器的包,这样对于外部主机来说,它们就像是来自NAT网关本身。NAT网关重写返回的包,以便它们流回到内部网上适当的机器。对于因特网上其它设备而言,只有一台主机和一个IP地址,并且所有的流量看起来都是来自这台机器的[21]。 NAT的这种方式,使日益耗尽的IP资源得到缓解,同时又具有方便性和安全性。因为内部网使用的冲地址都来自于一个保留的子网,所以管理员可以在他们的网络中添加和删除机器而不会与其它组织使用的正地址冲突,也不必从外部实体申请新的正地址。此外,NAT网关通过对因特网隐藏内部正地址和内部机器来担任某种类型的防火墙。仅当向某个外部地址发送过出站包时,NAT才允许来自该地址的流量入站。 NAT网关后面的应用程序可以任意与外部应用程序联系,但外部应用程序却不能同样方便地与NAT,网关后面的应用程序联系。还有,不同NAT网关后面的应用程序之间彼此不能直接联系。 我们来考虑如下几种结构的网络情况(左边是A机,右边是B机):如图3所示。 (1) AB机在同一NAT中 AB机器可以是在完全不受干预的情况下直接进行通信,这是一个透明的网络,当然一定要用AB机器的内部正作为其通信的地址。 (2) A机在外部网络B机在NAT中 NAT创建了一堵单向玻璃的墙。在这种网络结构中只能从出站方向开始通信,意外的入站连接将被拒绝。内部的B机可以看到外面,但外部的应用程序不能看到里面。AB机器要进行文件传输,必须首先由B机发起。 (3) AB机在不同NAT中 AB是完全孤立的两台机器,他们都不能够直接的发现对方和进行文件传输。对于这种结构,当前流行的P2P文件交换软件没有能够很好地解决。还是有办法的,可以称之为UDP隧道技术。考虑这样一个流程:NAT内部的机器创建了一个UDP端口,对外(比如外部服务器)发送了一次数据,那么在NAT网关的端口映射表上就会建立一条数据,即(外部IP,外部Port(内部IP,内部Port)。NAT网关会保留这条映射数据,以后的一段时间内,当外部网络有程序向NAT网关的这个被记录的UDP端口发送数据时,NAT网关会根据端口映射表查找到内部的机器的IP和端口,将数据直接转发到内部的那台机器上。这样一来,NAT对于内部机器和外部机器来说就是透明的,内外的机器可以透过NAT,网关进行直接的数据交换了。 如图4所示,AB机器在传输文件前,各自创建一个UDP端口,向外部网络的服务器发送传输请求,服务器在接收到请求的同时,也获取了A,B机器的对外IP和端口,于是将他们对外的IP和Port返回给A,B机器,这样,A向B的对外IP/Port,即B的NAT网关的特定Port发数据,B就能够直接收到,相反,B也能直接发送数据到A。这样就突破了NAT给文件传输带来的局限。 3 结语 本文主要对结构化和非结构化的P2P网络技术进行了研究,重点对P2P网络的Chord路由算法进行了深入的研究,在对Chord的构造和搜索算法进行深入分析之后,根据现实世界中各节点的处理能力千差万别,提出了一种Chord算法的改进方法,详细的论述改进Chord算法的具体实现方法。 [参考文献] [1]刘晓峰,吴亚娟,钟乐海.Chord路由表结构的改进与优化.计算机工程[J].2007,pp.21,pp.102-104. [2]许斌.JXTA-Java P2P网络编程技术[M].北京:清华大学出版社,2003. [3]杨建雄.JXTA平台下P2P网络安全信任模型的研究[D]. 长沙理工大学硕士论文,2008.pp.2-15. [4]聂荣,张洪欣,吕英华等. P2P网络的研究与进展[J].电信科学.2008.(3). [5]张文,赵子铭.P2P网络技术原理与C++开发案例[M].北京:人民邮电出版社,2008.pp.3-30. [6]Ralf Steinmetz著,王玲芳,陈焱译.P2P系统及其应用[M].北京:机械工业出版社,2008.pp.12-35. [7]刑小良.P2P技术及应用[M].北京:人民邮电出版社,2008.pp.3-20. [8]沈磊.基于超级节点的高性能P2P流媒体技术的研究与实现[D].南京航空航天大学硕士论文,2007.pp.3-25. [9]李振宇,谢高岗.基于DHT的P2P系统的负载均衡算法[J].计算机研究与发 展,2006(9):pp.1579-1585. [10]黄静,黄本雄,莫益军.基于DHT的P2P系统负载均衡的有效算法[J].网络与通信,2007(11):pp.80-82. [作者简介] 李文东:1979.10.25,男,沈阳理工大学学生,职称:讲师,研究方向:计算机应用; 和晓军:女,沈阳理工大学教师,研究生导师. 本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文