摘要：针对高速网络环境下连接记录管理的性能需求,提出了一种改进的高效哈希表PRH-MTF(伪随机哈希-移至最前).首先在定义输入关键字即连接标识符的基础上,通过选择适当的运算符,设计了高效鲁棒的哈希函数PRH.为有效解决哈希冲突,根据网络数据流局部性特点,应用MTF启发法,改进了传统的链式冲突解决方法.以分组火车模型作为数据包到达模式,分析了PRH-MTF哈希表的算法复杂度,推导出了平均查找长度.最后通过实际高速网络数据流和模拟攻击的方式,对PRH-MTF哈希表进行了实验评估.实验结果表明,PRH-MTF哈希表在查找性能和抗攻击能力等方面均优于传统的简单排序哈希表.

摘要：为了滤除STL面片数据中的冗余顶点 ,提出了基于哈希表的快速算法 ,使用链地址法处理冲突 ,根据顶点坐标设计高效哈希函数 ,直接滤除冗余顶点 ,从而提高运行效率 ,节省存储空间 .经测试验证 ,该算法效率远远高于三轴分块排序算法 .本算法已经成功应用于华塑CAE系统 。

摘要：基于网络处理器的防火墙中大量的内存访问会影响对高速网络流的处理速度。哈希表是防火墙中重要的数据结构,用拉链法解决冲突时一次查表的平均内存访问次数与相应拉链的长度成正比。把一条拉链划分成两条可以缩短链的长度,减少总的内存访问次数,从而提高系统性能。介绍了用两条链处理哈希表冲突问题的方法,分析了它对性能的影响,并以网络处理器IXP2400为例给出了具体设计和实现。

摘要：随着现代企业应用开发的规模越来越大,系统的性能与可伸缩性对系统的成败起着越来越重要的作用。在整个分层的企业级应用架构中,数据库层的访问速度通常会成为整个系统的瓶颈。采用Cache技术将已访问的数据缓存在应用层,从而减少数据库访问的负载量,可以使系统的性能与可伸缩性得到根本性的提高。在吸取了前人Cache开发经验的基础上,我们设计了DartCache,它是一套基于哈希表的分布式Cache系统。经实验证明,DartCache使系统的性能与可伸缩性都得到了根本性的提高。

摘要：分布式并行计算是提高计算机性能常用的方法,但针对不同需求,并行程序的设计并没有统一的模型与方法,使得并行程序的编写完全依靠开发人员的经验。Google公司提出的分布式并行编程模型MapReduce能够完成特定类型的并行程序的开发与运行。使用哈希表对MapReduce分布式并行编程模型进行优化,减少中间结果中的碎片,并省略Combiner中间函数的调用,减少传输负载,提升运行效率,同时兼顾了Map函数与Reduce函数接口的属性,保持了MapReduce模型的并行性特点。

摘要：哈希表是数据结构中的重要概念之一。由于它在记录查找时一次存取便能得到所查记录,所以在经常要进行的大容量数据库表的查询时,显示出相当高的效率。首先介绍了哈希表的有关知识,然后介绍了电信公用电话客户流失分析中为实现合并表所采用的哈希表冲突解决方法,接着介绍了合并表的处理流程,最后简介了应用中的关键算法。

摘要：在互联网码号资源公钥证书体系(Resource Public Key Infrastructure,RPKI)中,依赖方(Relying Party,RP)负责从资料库同步并验证资源证书和签名对象(ROAs,Manifests,Ghostbusters),而后将有效的ROA处理成用于指导BGP路由的IP地址块和AS号的真实授权关系.在当前的实现方式中,验证证书模块主要通过数据库查询递归查找待验证证书的父证书从而构建完整的证书链并由OpenSSL完成最终验证.由于RPKI体系中证书量较大,导致基于数据库查询的方法效率不足.结合RPKI运行机制中将计算代价由BGP路由器(用户)迁移到RP服务器(服务器)的特点和"空间换时间"的思想,可以将证书信息读取到内存中从而减少I/O的时间消耗.本文基于上述思想基础,结合哈希表中条目查询的时间复杂度最优为O(1)的特点,设计并实现了基于哈希表的RPKI证书验证优化方法.实验结果表明,在设计的3种实验场景中,平均时间加速比分别为99.03%、98.45%和97.48%,有效的减少了时间的消耗.

摘要：哈希表在网络报文处理,尤其是带状态的报文处理中发挥着重要作用.伴随着网络流量的快速增长,传统软件哈希表难以满足网络性能需求,而查找是影响哈希表性能的关键之一,如何提升哈希表的查找速率也一直是一个难点问题.经研究表明,现有的网络流量呈现Pareto分布特征,即存在少数的大流量数据——大象流.基于当前数据中心广泛采用的软硬协同计算模式,提出了一种基于DPDK+FPGA的大规模软硬协同哈希表架构.根据现有网络流量特征,将流量分成大象流与背景流.同时也将哈希表分成硬件表与软件表.在FPGA中构造小规模硬件表,卸载所有报文的哈希计算,以及大象流的哈希查找.在软件中基于DPDK构建大规模软件表,利用FPGA卸载哈希计算,加速背景流的查找.软件拥有所有流信息,利用采样法识别大象流并将大象流的键值对信息(key-value)更新到FPGA的硬件表中,以加速软件中大规模软件表的查找速率.采用Xilinx U200加速卡和通用服务器作为硬件平台,实现了软硬协同的大规模哈希表,并利用测试仪构造了符合当前网络特征的流量数据,以DPDK精确转发为例,验证了软硬协同哈希表的性能.结果表明,在大象流哈希查找完全卸载的情况下,其性能相较DPDK原有的精确转发提升了64%–75%;在大象流未卸载的情况下,其性能提升了5%–48%.

摘要：哈希表以访问效率时间复杂度O(1)著称,作为一类可提供大规模数据高效访问的算法和数据结构为各类大数据应用所采用,例如,适用于各类新兴高性能(HPC)领域、数据库领域的工作负载和场景.随着高性能协处理器GPU硬件性能的日益提升,面向高性能GPU环境的哈希表并行优化已逐渐吸引了大量研究工作.当前的各类GPU哈希表优化方法和解决方案集中于利用GPU的大规模线程环境和高内存带宽来提升哈希表的事务高并发性处理和键值对数据快速访问.然而,由于现有GPU哈希表结构的研究工作普遍忽略了GPU资源有效管理,并没有以如何充分利用GPU线程资源和显存资源.同时,由于GPU显存空间的大小限制,用于存储哈希表结构数据的空间有限,无法应对更大规模的哈希表结构.因此,面向GPU环境下的哈希表方法的可扩展性和性能仍存在着技术挑战.本文提出并设计了一种面向GPU环境的可处理大规模并发事务的哈希表技术,命名为Starfish. Starfish提出了新的基于异步GPU流的“交换层”(swap layer)技术,用以支持GPU显存外的动态哈希表,同时也保障了GPU哈希表的索引方法性能.为了解决GPU大规模线程的访问带来的哈希冲突开销, Starfish设计了一类紧凑型数据结构,并研究了一种可分页显存的分配方法,不仅为GPU哈希表技术提供了静态哈希方法的高性能,而且也支持动态哈希的高可扩展性.性能评估实验表明, Starfish显著优于其他GPU哈希表技术,包括cudpp-Hash, SlabHash.

摘要：通过对DXF文件结构和哈希查找算法的详细剖析,在UNIX平台下运用C语言设计了基于哈希表的DXF文件信息读取方法,并将其运用到冲压成形专用非线性有限元仿真软件包SHEET-FORM ING中,解决了其与CAD软件之间缺乏数据流联系的"孤岛"现象,从而提高其有限元模型的建模效率。