黄德森[1]2004年在《两层的Hash架构及其支持动态字典的机制》文中进行了进一步梳理随着计算机网络技术的迅猛发展，以及计算机硬件性能的大幅度提高，新的市场需求应运而生。特别是有关网络方面的需求更是层出不穷，从事宽带接入系统开发的一家公司向我们提出需要一套宽带接入系统中IP地址快速定位的软件，因为他们自己开发的基于二分查找的IP地址定位算法已经无法满足要求。于是我们针对IP地址快速定位问题开始研究更高效的查找算法。无独有偶，另一家公司得知我们在研究高效查找算法，也向我们提出了类似的需求。这些给我们的研究提供了重要的背景和动力。这些需求，抽象起来，实际上就是要求设计一种结构，高效地支持动态ADT字典。动态ADT字典传统的实现方式，主要分两类，一类支持基于元素关键字值比较的结构，另一类支持基于散列的结构。考虑到IP地址绝大多数操作是查找，相对而言，插入和删除操作的频度十分低，第一类实现方式不适用。第二类实现方式以查找效率高见长。我们分别试用了传统的开散列、闭散列、完美散列和可扩展散列等，发现运用单一的传统散列技术还满足不了实用的需求，但它们都有支持快速查找的潜力，值得作深入的研究，有望通过对它们的改进，综合各自的优势，形成一种复合结构，满足实用的需求。在进一步研读有关Hash技术文献的基础上，我们一方面注意到Hash本身的局部化功能，即把字典元素按关键字的Hash值“平均地”划分成一些互不冲突的等价类，使冲突只在规模与全集比相对小得多的同一个等价类中发生；另一方面注意到传统可扩展Hash有可改进达到快速地对同一等价类中的元素进行再散列的潜力。照此设想，把这两方面结合起来，优势互补，将会有所突破。于是，我们对传统的可扩展Hash作了深入的研究，找到了对它进行改进的窍门，然后把改进版本与通常的Hash成功地构成一个两层Hash架构，支持动态ADT字典。实验的结果与我们的定性分析一致，效果显着。本文的创新之处在于：1.针对传统可扩展Hash存在的弊端，在分析了它的逐步扩展机制之后，发现扩展过程从初态到终态不必按部就班，可以一步到位。并且建立起了扩展过程的终态与初态的状态参数之间的直接数学关系式，使传统可扩展Hash的自适应可扩展过程大为缩短，显着地改进了算法的时间效率。2.提出两层的Hash构架，支持动态ADT字典。第一层采用通常的Hash，将字典元素的冲突局部化；第二层采用上述改进的可扩展Hash，对冲突的字典元素根据冲突的状况自适应地作进一步散列。与传统的开散列相比，这种两层的Hash构架所支持的动态ADT字典的平均时间效率提高了2倍。
汪军[2]2006年在《分布式SIP协议栈的研究与实现》文中认为SIP是近年来快速发展的一种应用在通信呼叫控制领域的协议,它起源于Internet领域,对通信网络的架构产生了重大的影响。与传统通信协议不同,SIP协议完全采用文本编码,以方便脚本类语言的操作,其应用的前提是智能化的终端、全IP承载。3GPP在R5版本中提出的IP多媒体子系统将SIP作为唯一的会话控制协议,SIP跨越了IMS网络的接入、控制、业务叁个层次,相应地SIP要具备接入控制、会话控制、业务生成叁个层次的能力。近年来IETF对其作了大量的研究与扩充,使之完全能够适应于网络架构上各层次的需求。SIP与SDP(会话描述协议)一道完成复杂的会话控制,它也可通过消息体来携带即时消息、呈现服务等各类应用层次的信息,此时其更类似于一个传输层协议。本文主要及成果成果在以下几点:1、SIP网络及会话控制能力的深入研究,对比了分级组网与平面组网的优劣,分析了组网会话模型对协议栈架构的重要影响。2、深入研究了SIP分布式系统的负载均衡方案,提出了新的负载均衡体系架构,该架构适用于了SIP同时作为接入及网络侧信令的特点,可以达到理想的负荷分担效果。3、在HASH负载均衡算法的基础上结合对SIP协议进行的私有扩展,实现了分布式SIP处理系统的高级容错特性。4、研究了IMS用户身份标识与鉴权卡号之间的多对多关系,分析了其对分布式SIP处理系统的影响及在不同分布关键字条件下的系统性能。
闫盼[3]2015年在《进化算法中历史计算数据的哈希技术研究》文中研究说明进化算法由于其强大的系统建模能力和空间搜索能力已被广泛应用于许多实际问题的求解中。然而在算法进化的过程中存在着个体适应值重复计算的问题,尤其在解决实际工程中的复杂问题时,适应值的计算会消耗大量时间资源。针对个体适应值的重复计算问题,如果将已计算的数据保存起来,计算适应值前先检查历史计算数据,若存在计算过的数据便可直接使用,这样,就可以通过保存与查询历史计算数据的方式来减少个体适应值的实际计算次数。文中首先针对进化算法中历史计算数据的特点,对哈希表的key值编码,哈希函数与冲突处理进行了研究,提出了基于哈希表的历史计算数据高效存取方法;在此基础上,对离散、连续优化问题中历史计算数据高效利用问题进行了研究。对于处理适应值计算费时问题的另一种有效的方法是适应值估值策略,本文针对进化算法中适应值估值策略常用的邻域查询问题,提出了一种基于哈希桶的邻域查询方法。最后,针对使用哈希桶处理不同问题分别给出了仿真实验数据及结果分析。仿真实验表明,将哈希机制用于历史计算数据的高效利用,能够有效地减少适应值的计算次数,提高算法效率。
周斌[4]2015年在《面向大数据的高效存储容量缩减技术研究》文中研究指明随着信息化的发展,全球数据量呈指数式增长,数据中心存储规模快速迈向了PB级甚至是EB级,其中包含了大量的冗余数据。这些冗余数据占用了大量的存储资源,导致存储系统性能降低,数据存储和管理成本增加等问题。在此背景下,存储容量缩减技术在不改变数据基本属性前提下,通过采用重复数据删除技术和数据压缩技术,有效地缩减数据量的规模,提高存储资源利用率,降低管理成本。存储容量缩减技术已经成为业界研究的热点,显示出重要的学术价值和应用价值。然而,大数据的规模巨大、类型繁多、冗余量庞大以及对数据处理的速度要求较高等特点,导致存储容量缩减技术在面对大数据应用时仍然存在许多需要解决的技术问题。例如如何降低数据分块时间开销,减少冗余数据块发现时间以及提高数据压缩速度和压缩率等方面。针对上述问题,从存储容量缩减技术的数据分块策略、冗余数据块的发现机制以及数据块的高速压缩机制等方面进行深入的研究。具体来说,主要从以下叁个方面提出了创新性理论或方法:1.基于位串内容感知的数据分块策略(Bit-string Content-aware Chunking Strategy,BCCS):围绕影响数据分块性能的各种因素进行分析和讨论,实现了一种新的基于位串的数字签名技术,并在此基础上提出了BCCS。BCCS从数据块每个正文字节中抽取某一特定比特来构成窗口特征数据,并使用位操作替代传统的比较操作。该策略充分利用每一次失败的匹配尝试所带来的特征信息,尽量排除尽可能多的不能匹配位置,从中获取最大跳跃长度,从而加快二进制串的匹配过程,降低确定块边界的CPU资源消耗。实验结果表明,对于可变数据测试集,相对Rabin算法,BCCS的数据块划分速度最多可以提高197%;对于固定数据测试集,相对于FSP算法,BCCS速度仅仅降低10.8%,而其数据压缩率却较FSP的0.977提高到了1.206,可以提高20%。2.基于二级布隆过滤的冗余数据块发现机制(Redundant Chunk Query Mechanism based on Two-staged Bloom Filter,RCQM-TBF):针对数据指纹(FingerPrint,FP)数量巨大,不能完全存储在内存中,导致性能下降的问题,提出了RCQM-TBF。RCQM-TBF中第二级布隆过滤器作为第一级布隆过滤器结果的一个整体表现,其每一个比特位代表进入相同准二级假阳性误判状态的所有FP。对于FP假阳性访问,TBF通过降低二级布隆过滤机制中第一级和第二级过滤的假阳性误判率,快速判断新到达数据块的非存在性;对于FP正常性访问,TBF通过建立FP高速缓存链表和对应的FP预取机制来减少直接的硬盘访问,对新到达的数据块存在性进行快速判断;同时TBF创建了一个具有强全局散列特性的哈希函数族,减小碰撞发生的可能性。实验结果表明,对于非冗余测试数据集,RCQM-TBF的FP查询延迟性能和数据块的存储性能较采用标准布隆过滤算法的ZHU-BLOOM FILTER最多提升了28%;对于冗余测试数据集,RCQM-TBF的存储速度较ZHU-BLOOM FILTER最多可以提高100%到135%;当扩充服务器内存时,理论上RCQM-TBF可管理的存储数据容量最大可以达到64PB。3.基于多矩阵并行匹配的高速数据压缩机制(Parallel Matching LZSS based on Multiple Matrix,PMLZSS-MM):为了加快压缩速度,并提高存储容量利用率,提出了PMLZSS-MM。该机制实现了一种GPU平台下的多矩阵并行匹配工作模式,将需要压缩的数据动态划分多个字典串和预读串,分别将其作为矩阵的纵轴和横轴,分解到GPU中的不同线程块中,形成多个矩阵进行并行匹配;而对于需串行执行的压缩编码生成部分,仍然在CPU上执行。通过合理的调度策略,协调两者共同完成任务。实验结果表明,PMLZSS-MM容量缩减率有所下降。相对于经典CPU平台上的串行LZSS算法,容量缩减率最多下降了1.5%。但PMLZSS-MM显着提高了大数据的压缩速度,当字典窗口设置为4KB,预读数据窗口设置为64B时,相对于CPU平台上的串行LZSS算法,其压缩吞吐率最大提高了18倍;相对于GPU平台上的并行CULZSS算法,其压缩吞吐率最大提高了20.8%。综上所述,通过采用BCCS,有效地减小数据分块过程中的CPU资源消耗,提高发现块边界的速度;采用RCQM-TBF,提高数据指纹查询速度,获取高效的查询速度;引入PMLZSS-MM,进一步补充和优化前两项技术的不足,获取更高的存储容量缩减率。
参考文献：
[1]. 两层的Hash架构及其支持动态字典的机制[D]. 黄德森. 福州大学. 2004
[2]. 分布式SIP协议栈的研究与实现[D]. 汪军. 南京航空航天大学. 2006
[3]. 进化算法中历史计算数据的哈希技术研究[D]. 闫盼. 太原科技大学. 2015
[4]. 面向大数据的高效存储容量缩减技术研究[D]. 周斌. 华中科技大学. 2015
标签：计算机软件及计算机应用论文; 散列算法论文; hash论文; sip论文;