哈希表

摘要： Cisco IOS(Internetwork Operating System)作为Cisco路由器的专用操作系统,其由于硬件条件限制,在设计时更加注重性能而忽视了系统安全,导致无法有效检测面向返回地址编程(Return-Oriented Programming,ROP)的攻击。针对传统的ROP防护技术在解决Cisco IOS防护上存在的缺陷,提出了一种基于返回地址内存哈希验证的方法,能够对面向Cisco IOS的ROP攻击进行有效检测,并对ROP攻击代码进行捕获。通过分析现有针对ROP攻击的防护机制的优缺点,在紧凑型影子内存防护思想的基础上,将传统的影子内存存储模式改造为基于哈希的内存查找模式,增加了返回地址内存指针的记录作为哈希查找的索引,提高了影子内存查找效率,同时能够抵御由于内存泄露导致的影子内存篡改。在Dynamips虚拟化平台的基础上设计实现了CROPDS系统,对所提方法进行了有效验证。与现有方法对比,所提方法在通用性和性能上均有提升,并能够捕获到攻击执行的shellcode。

摘要： 空间并置(co-location)模式挖掘是指在大量的空间数据中发现一组空间特征的子集,这些特征的实例在地理空间中频繁并置出现.传统的空间并置模式挖掘算法通常采用逐阶递增的挖掘框架,从低阶模式开始生成候选模式并计算其参与度(空间并置模式的频繁性度量指标).虽然这种挖掘框架可以得到正确和完整的结果,但是带来的时间和空间开销非常大.此外传统方法对于空间并置模式的最小频繁性阈值较为敏感,当最小频繁性阈值改变时整个挖掘过程需要重新进行.因此,本文提出一种基于极大团和哈希表的空间并置模式挖掘算法CPM-MCHM(Co-location Pattern Mining based on Maximal Clique and Hash Map)来发现完整并且正确的频繁空间并置模式.CPM-MCHM算法不仅避免逐阶候选-测试框架带来的巨大开销问题,还降低了算法对最小频繁性阈值的敏感.首先,采用基于位运算的分区Bron–Kerbosch算法生成给定空间数据集的所有极大团,并将其存储在哈希表中.然后,提出一种两阶段挖掘框架计算所有模式的参与度并过滤所有频繁空间并置模式.最后,在真实和合成数据集上进行了大量的对比实验.与经典的传统算法和近两年内学者提出的两种算法相比,当实验数据的规模达到20万实例数时,本文提出的CPM-MCHM算法的挖掘时间和空间耗费分别降低了90%和70%以上,当实验数据量进一步加大时CPM-MCHM算法的优势更加明显.

摘要： 针对当前网络防火墙状态检测模型的网络安全置信度低,导致防火墙状态检测时间较长,服务器易受到攻击,检测准确率及防火墙安全性较低的问题,提出了基于信任机制的网络防火墙状态检测模型。分析防火墙安全性能,根据信任机制建立置信度,通过自适应阈值算法,判断网络是否存在攻击现象,并对数据包实施预处理,设置包过滤防火墙规则集,运用哈希表直接查询数据包,构建网络拓扑结构,建立防火墙状态检测模型,完成基于信任机制的网络防火墙状态检测模型。仿真结果表明,所提方法的检测准确率较高,能够缩短防火墙状态检测时间,服务器可以有效避免攻击,提高防火墙自身的安全性。

摘要： 针对基于原始点对特征的三维目标识别算法中存在的内存浪费及过多冗余点导致的配准效率不高问题,提出一种改进的自适应分辨率点云配准算法。通过使用自适应体素网格滤波器对原始点云进行下采样,有效地减少了目标模型哈希表中存在的大量冗余点对,节省了计算机的内存开销并提高了点云配准算法的配准速度。使用迭代最近点方法进一步对聚类结果进行优化处理。实验结果表明:所用算法与传统ICP算法相比,在配准误差相同的情况下配准效率提升显著。

摘要： 针对复杂场景下的三维点云目标识别速度慢,准确率低的问题,提出了一种基于关键点的点对特征三维目标识别算法.通过直接对关键点建立点对特征,避免了周围邻域局部曲面的特征计算,具有空间维度小和计算速度快的特点.使用哈希表存储,加快了特征匹配的时间.利用快速投票方案对模型点云和场景点云进行匹配识别,生成候选位姿,利用贪婪算法对候选位姿进行聚类与筛选,采用ICP算法对物体位姿进行优化,基于配准后的点云重叠情况完成目标识别.对提出的算法在多个数据集以及真实场景下进行了实验,验证了所提出的识别方法具有可行性和有效性,且对噪声的鲁棒性较强,具有一定的实际工程应用价值.

摘要： 概述了命名数据网络(NDN)名称查找所面临的挑战以及实施难点。针对现有的22种名称查找方法,以查找吞吐率、内存开销占比和名称路由表3个因素作为衡量指标,分别采用基于前缀树、哈希表、布隆过滤器3种查找方案进行比对分析。结果表明:使用2种及以上的混合查找方案能够有效提高名称查找效率,为未来NDN的设计提供了新的思路。

摘要： Apriori算法在数据挖掘过程中需要多次扫描数据库,会造成I/O上有较大时间开销和负载,影响算法的运行速度,同时在计算频繁项集的过程中,需要进行大量迭代搜索与计算,算法的时间复杂度和空间复杂度较高。基于此,提出一种基于哈希表与十字链表存储的优化算法HTACL-Apriori。通过理论分析和数据进行实验对比,验证了优化后的HTACL-Apriori算法相对于传统的Apriori算法在时间效率和空间效率方面有明显的提高,达到了预期效果。

摘要： 日志分析对于计算机系统的稳定运行起着至关重要的作用,然而日志通常是非结构化的,不利于自动化分析,如何自动化将日志的模式提炼出来并变成结构化的数据具有重要的实际意义。提出了LDmatch算法,该算法以单词匹配率为基础实现了一种日志模式提炼算法。传统的日志匹配算法在进行相似度计算时使用一对一单词匹配法,而LDmatch算法根据两条日志所包含的单词之间的最长公共子序列计算日志之间的相似度,并以此为基础进行日志分类。LDmatch算法还能实时得到日志模板并更新。除此之外,该算法的模式仓库使用了基于哈希表的数据结构进行存储,该存储结构细化了日志的分类,减少了日志匹配时的比较次数,从而提高了日志模式提炼算法的匹配效率。为了验证算法的优势,将LDmatch算法应用于开源数据集以及国家高性能计算环境实际产生的日志数据集,并且使用多种其他日志模式提炼算法进行对比并得出实验结果,最终证明了该算法在准确度、鲁棒性和效率上具有优势。

摘要： 哈希表以访问效率时间复杂度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.

摘要： 模型数据的读取和存储是所有3D打印的基础,冗余数据的产生容易导致打印效率的下降。针对STL文件存在的顶点数据多次纪录的问题,提出一种基于哈希表的冗余数据优化方法。该方法将多余数据剔除,缩短了数据处理时间,提高了打印效率。通过实验论证,模型数据实现了16.7%的顶点去冗。

摘要： 最大频繁项目集的挖掘和更新是数据挖掘研究的一个重要方面.针对数据库中各个项目的重要性不尽相同且分布不均的情况,本文提出了有效挖掘加权频繁项集的WHIUA(Weighted Hash Incremental Updating Algo rithm)算法,该算法基于哈希表的数据存储结构,处理数据库和最小支持度两者同时发生变化的问题.分析和实验表明,该算法可有效提高最大频繁项目集的挖掘和更新效率.

摘要： 哈希表查找作为一种快速的数据查询算法被广泛应用.为了更好地查找和解决哈希冲突,在构建哈希表时常选用链地址法来解决冲突.由于在查找哈希表时需要遍历链表,大大降低了查找效率.该文在结合链地址法和二分查找的基础上,提出了一种提高哈希表查找效率的改进方法.实验结果表明,该方法降低了冲突时执行查询的查找长度,从而降低了查询所需的时间.

摘要： 基于串联质谱数据进行蛋白质鉴定时，质谱仪导出的原始数据中很关键的母离子信息存在很多错误，这直接影响后续的鉴定性能。本文针对这些问题而开发了pParse软件，使用了C++语言重新实现了pParse的各项功能，使用了哈希表的方法加快数据查找速度，同时用决策树的方法重新整理了多个过滤器，用新的算法流程减少了存储需求，在降低算法的复杂度的同时，也提高了召回率。它可以纠正错误，从而提高串联质谱鉴定率。

摘要： 随着XML的广泛应用,XML上的关键字检索逐渐成为一个研究热点.现有的关键字检索方法主要基于LCA计算和候选点选择两种操作,存在以下问题:首先,现有方法利用Dewey编码来表示结点,LCA的计算过程需要逐段地比较Dewey编码,当XML深度很大时,大量的LCA计算会影响算法的性能.其次,为了确定候选点(即用于进行LCA计算的结点),需要对结点集进行遍历,当结点集很大时,查找过程比较耗时.针对以上问题,首先提出一种基于哈希表的索引结构来记录结点和标签之间的关系。基于这种索引结构,进一步设计了高效的关键字检索算法——Hash-Search算法,避免了LCA计算和确定候选点过程.在理论上提供了算法的正确性证明和复杂度分析,并进行了实验测试,表明Hash-Search算法是一种高效的XML关键字检索算法。

摘要： 介绍了一种应用在静态交通中最短路径规划的改进启发式A-star算法,首先对该算法中的关键步骤进行了描述和分析,然后针对传统采用数组或链表模式实现算法时占用资源过多或效率不高的情况,提出采用哈希表来优化算法,最后以湖北省的路径规划为实例对算法进行了测试和分析,证明引入哈希表对路网数据进行存储和检索,能实现规划数据的快速查找和计算,大幅度提高算法执行效率,减少实现的复杂度.

摘要： 研究了两种常见分词词典机制,提出一种改进的词典机制。在传统的首字哈希表中增加拼音首字母,在首字哈希表中查询次字的拼音首字母,缩小了次字查询范围,同时也较大幅度地提高了次字的整体查询效率。通过实验测试,改进后的机制空间开销增加了不到5%,时间效率却提高了20%以上。

摘要： 基于翻译记忆这一机器翻译技术,本文对比了Trie树、哈希表、后缀数组这三种比较常见的索引方式,并提出了一种基于哈希表和后缀数组的双重策略的翻译算法,并应用于汉日机器翻译系统中,同时提出了一种利用此技术进行机器辅助翻译的方法。初步实验结果表明,该方法拥有较高的效率和较低的内存资源占用。

摘要： 传统的复杂事件处理都是基于时间戳上的有序性,而在实际场景中事件流往往不是有序的.对于事件流乱序问题的解决通常是在它们进入模式匹配之前就将其有序化,但是通常这种算法的效率不高且并没有对乱序时的非事件进行处理.本文采用HASH链表对中间结果进行缓存并通过0CEPM算法来调整乱序事件流以输出最终的复杂事件,然后阐述了如何判断乱序事件流下非事件是未发生还是未到达,最后通过智能交通下左转闯红灯这一案例场景证明了OCEPM算法的有效性.

摘要： 传统的复杂事件处理都是基于时间戳上的有序性,而在实际场景中事件流往往不是有序的.对于事件流乱序问题的解决通常是在它们进入模式匹配之前就将其有序化,但是通常这种算法的效率不高且并没有对乱序时的非事件进行处理.本文采用HASH链表对中间结果进行缓存并通过0CEPM算法来调整乱序事件流以输出最终的复杂事件,然后阐述了如何判断乱序事件流下非事件是未发生还是未到达,最后通过智能交通下左转闯红灯这一案例场景证明了OCEPM算法的有效性.

摘要： 传统的复杂事件处理都是基于时间戳上的有序性,而在实际场景中事件流往往不是有序的.对于事件流乱序问题的解决通常是在它们进入模式匹配之前就将其有序化,但是通常这种算法的效率不高且并没有对乱序时的非事件进行处理.本文采用HASH链表对中间结果进行缓存并通过0CEPM算法来调整乱序事件流以输出最终的复杂事件,然后阐述了如何判断乱序事件流下非事件是未发生还是未到达,最后通过智能交通下左转闯红灯这一案例场景证明了OCEPM算法的有效性.

摘要： 本发明公开了一种哈希表的表项添加、删除、查找方法及哈希表存储装置。本发明的哈希表的表项查找方法通过并行计算待查找表项键值的哈希值，并根据该哈希值到对应位图中进行查找，并将查找的结果进行对比，当第一次出现冲突位为无效时，取出该位图的地址对应的哈希子表中的表项；将其与带查找表项进行对比，如果相匹配，则该表项即为待查找的表项，即查找到待查找的表项。本发明的哈希表表项查找方法以极小的查找时间代价以及较高的表空间利用率实现全部表项存储而无表项遗留，只需访问一次存储器就能够准确的查找到需要的表项，同时也便于硬件与存储器之间接口的实现，能够在表空间大小，查找效率以及硬件实现方面获得比较好的均衡。

摘要： 本发明公开了一种分布式哈希表路由表更新方法及节点，其中，所述方法包括：叠加网中节点检测到叠加网发生调整时，进行路由表更新，并将触发路由表更新原因信息及更新后路由表哈希值通知叠加网的其他节点；其他节点根据触发路由表更新原因信息进行本地路由表更新，并计算本地更新后路由表的哈希值，确定所计算哈希值与所接收到的路由表哈希值不一致时，与发送触发路由表更新原因信息的节点之间进行路由表交换；其他节点以及发送触发路由表更新原因信息的节点对比所交换的路由表间的差异，对叠加网差异处进行探测，在确定需要修正本地路由表时，进行路由表修正。本发明能自动消除节点间路由表不同步的现象，从而避免了错误的路由表扩散，不会导致叠加网路由性能下降。

摘要： 本发明公开了一种基于哈希表和TCAM表的MAC地址硬件学习方法及系统，涉及MAC地址学习领域，本发明在没有MAC地址冲突的时候，使用哈希表来存储学习到的MAC地址，哈希表硬件上用SRAM或者DRAM来实现；存在MAC地址冲突时，使用TCAM表来缓存冲突的MAC地址，TCAM表硬件上采用TCAM存储器来实现，由于TCAM硬件上是并行查找，一次搜索即可定位空闲表项，而且TCAM的表项个数就是实际能缓存的冲突的MAC地址个数。本发明在通用的可编程交换芯片上实现，不需专用硬件电路的支持，学习速率较高，占用的内存资源较少，采用通用的算法，应用灵活，能实现冲突概率完全可控。

摘要： 本发明实施例公开了一种哈希桶查找方法、哈希表存储方法、哈希表查找方法、装置、设备和存储介质，哈希表中存在至少两个哈希桶，哈希桶具有桶链表，桶链表具有结点，哈希桶与结点链接的哈希桶用于存储存在哈希冲突的数据，哈希桶查找方法包括：获取哈希桶的桶链表，所述桶链表中的结点包括处于尾部的尾结点；在所述哈希表中采用至少两种哈希桶查找方法，以所述哈希桶的桶链表的尾结点链接的哈希桶为起点查找空闲的哈希桶。由于采用至少两种哈希桶查找方法查找空闲的哈希桶，一方面提高了查找空闲哈希桶的效率和数据存储的效率，另一方面，避免了单一哈希桶查找方法造成数据聚集的现象，能够合理地存储数据，提高了查找数据的性能。

摘要： 本发明公开了一种哈希表的表项添加、删除、查找方法及哈希表存储装置。本发明的哈希表的表项查找方法通过并行计算待查找表项键值的哈希值，并根据该哈希值到对应位图中进行查找，并将查找的结果进行对比，当第一次出现冲突位为无效时，取出该位图的地址对应的哈希子表中的表项；将其与带查找表项进行对比，如果相匹配，则该表项即为待查找的表项，即查找到待查找的表项。本发明的哈希表表项查找方法以极小的查找时间代价以及较高的表空间利用率实现全部表项存储而无表项遗留，只需访问一次存储器就能够准确的查找到需要的表项，同时也便于硬件与存储器之间接口的实现，能够在表空间大小，查找效率以及硬件实现方面获得比较好的均衡。

摘要： 本发明属于计算机散列数据结构领域，特别涉及一种用于哈希运算的数据结构及基于该结构的哈希表存储、查询方法，为了保证查询效率，采用双端口存储体进行硬件实现，支持同时读取存储体的两个地址的内容，能够在确定的时间内完成键值比较，适合采用流水线的方式实现高效查询；通过更多的哈希运算提供更多的候选位置，降低哈希冲突发生的概率，提升哈希表项的插入存储和更新效率，支持哈希表项容量动态改变，避免空间浪费或因表项插入操作导致性能下降，适用于哈希表项未知且不断变化的应用；采用CRC算法作为哈希函数，哈希计算结果具有较好的唯一性，具体实现时可基于XOR异或操作和并行流水实现结构得到哈希运算结果，有利于硬件设计实现。

摘要： 本发明涉及采用不同方式计算哈希值建立哈希表进行搜索的编码方法，获得图像的采样格式，对图像中的所有像素按照预设规则计算哈希值，不同的采样格式中，至少有两个不同采样格式所使用的预设规则不相同，将具有相同哈希值的像素链接起来建立哈希表，进行基于哈希表的搜索及编码；预设规则选取各分量不同/相同位置的位数；选取各分量不同/相同数目的位数，各分量的数目总和与设定总位数相等；上述规则可以择一或者将多个规则组合使用。本发明针对不同采样格式的图像，采用不同方式计算哈希值，对不同分量采用不同位置和/或不同数目的位数分配，从而提高判断两个像素是否相同或相似的精确度，进一步提高不同采样格式的图像编码效率。

摘要： 本发明公开了一种分布式哈希表路由表更新方法及节点，其中，所述方法包括：叠加网中节点检测到叠加网发生调整时，进行路由表更新，并将触发路由表更新原因信息及更新后路由表哈希值通知叠加网的其他节点；其他节点根据触发路由表更新原因信息进行本地路由表更新，并计算本地更新后路由表的哈希值，确定所计算哈希值与所接收到的路由表哈希值不一致时，与发送触发路由表更新原因信息的节点之间进行路由表交换；其他节点以及发送触发路由表更新原因信息的节点对比所交换的路由表间的差异，对叠加网差异处进行探测，在确定需要修正本地路由表时，进行路由表修正。本发明能自动消除节点间路由表不同步的现象，从而避免了错误的路由表扩散，不会导致叠加网路由性能下降。

摘要： 本发明公开了一种基于哈希表和TCAM表的MAC地址硬件学习方法及系统，涉及MAC地址学习领域，本发明在没有MAC地址冲突的时候，使用哈希表来存储学习到的MAC地址，哈希表硬件上用SRAM或者DRAM来实现；存在MAC地址冲突时，使用TCAM表来缓存冲突的MAC地址，TCAM表硬件上采用TCAM存储器来实现，由于TCAM硬件上是并行查找，一次搜索即可定位空闲表项，而且TCAM的表项个数就是实际能缓存的冲突的MAC地址个数。本发明在通用的可编程交换芯片上实现，不需专用硬件电路的支持，学习速率较高，占用的内存资源较少，采用通用的算法，应用灵活，能实现冲突概率完全可控。

摘要： 本申请提供哈希表的确定方法及装置，其中所述哈希表的确定方法包括：响应于针对目标业务数据表的哈希表创建请求，确定至少一个待匹配哈希算法；分别通过每个待匹配哈希算法计算得到所述目标业务数据表中的业务字段信息，获得所述目标业务数据表根据每个待匹配哈希算法生成的参考哈希表；确定哈希冲突数小于等于预设阈值的参考哈希表为所述目标业务数据表对应的目标哈希表。