下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 一个实用的针对URL的哈希函数

一个实用的针对URL的哈希函数.pdf

一个实用的针对URL的哈希函数

爱动漫呢
2011-03-12 0人阅读 举报 0 0 暂无简介

简介:本文档为《一个实用的针对URL的哈希函数pdf》,可适用于高等教育领域

  收稿日期: 基金项目:国家"九七三"项目(G)资助北大"九八五"项目资助 作者简介:肖明忠,男,年生,博士生研究生,主要研究方向为计算机网络与分布式系统代亚非,女,年生,教授,博士生导师,主要研究方向为网络存储、语义Web等一个实用的针对URL的哈希函数肖明忠,闵博楠,王佳聪,代亚非(北京大学计算机系网络实验室,北京)Email:mzxiaonetpkueducn摘 要:在Web信息处理的研究中,不少情况下需要对很大的URL序列进行散列(hashing)操作本文提出了一个针对URL数据集合的均匀哈希函数,它是ELFhash函数的变型通过对天网搜索引擎采集的亿多个URL集合的抽样实验表明:它能有效使得URL集在哈希表中均匀散布并通过与MD和SHA的对比,认为它是实用的最后,指出了进一步的研究方向关键词:URL哈希函数ELFhash均匀分布MDSHA中图分类号:TP     文献标识码:A      文章编号:()PracticalHashingFunctionforURLsSetXIAOMingzhong,MINBonan,WANGJiachong,DAIYafei(DepartmentofComputerScienceTechnology,PekingUniversity,Beijing,China)Abstract:URLhashingisfoundmanyapplicationsinWebresearchWeproposeahashingfunctionforlargescaleURLssetandfindithasbetteruniformityandstabilitythantheothertwo(HfIpandhf)throughthreeexperimentsofthelargescaleItisavariationofthewellknownfunction(ELFhash)andisrecommendedusedintheapplicationsofneedingtohashURLsMoreover,ithaslowtimecostandalmostperformancecomparedwithMDandSHAsothatwethinkitismorepracticalthantheotherFinally,somefutureworksaregivenKeywords:URLhashingfunctionELFhashevendistributionMDSHA 引 言哈希(hashing,散列)方式组织和查找信息的研究始于年前,其基础性和在许多领域的可应用性是其不断被人们研究的源泉,而对它的研究不断能有新意的基本原因在于其优化性能在很大程度上取决于输入键的结构本文研究的键值是形如“http:öönetcspkueducnö⋯”这样的url字符串我们前期的工作表明:在许多文献中推荐的对字符串散列效果很好的ELFhash函数对URL的散列效果并不好,同时推荐了两种已经应用于天网搜索引擎许久的对URL散列效果较好的哈希函数HfIp和hf我们对ELFhash函数进行了改进,并通过实验证实其散布均匀性优于HfIp和hf以及通过与MD和SHA的对比,认为它是实用的本文首先给出哈希函数散布均匀性(公平性)定义及其评估测度,然后描述用于实验的数据集和三个散列函数以及实验的方法在介绍了实验设计的细节后,我们给出实验的结果并作了分析讨论最后是对本文工作的一个总结以及指出进一步的研究方向 哈希函数散布均匀性及测度设有长为M的哈希表T,每个表位置称为槽,哈希函数h就是将N个键值映射到T中,按照开散列方法(又称拉链法)处理冲突,当M<N时,理想情况下,h将把N个键值均匀散布到M个槽中,使得每个槽中恰拥有NöM个键值我们称这个h对M个槽拥有的公平性,也称h具有均匀性,记为fairness(h)=我们设计哈希函数时,总是希望键值能均匀分布,避免聚集现象,而实际的哈希函数要做到这一点是非常困难的,通常只能是<fairness(h)<fairness(h)越接近表示键值越被均匀散布,越接近表示键值聚集现象严重,散布越不均匀如何评测哈希函数的散布均匀特性,存在许多可选的方法,,,,我们选择RJainetal提出的测度方法并结合我们的工作背景作了适应性修改,表述如下:假定xi是哈希函数h分配给第i(≤i≤M)个槽的键值数,记为随机变量x,∑Mi=xi=N,则h的均匀性定义为:fairness(h)=(E(x))E(x)=(∑Mi=xi)M(∑Mi=xi)()易证<fairness(h)≤fairness(h)越接近,表明h越公平(或越具有均匀散布特性)若fairness(h)=,意味着对的槽来说是公平的,对的槽是不公平的,即均匀分布在的槽中这个测度公式被认为是方差公式的变形,它抓住了全局,能反映与理想分布情况(fairness(h)=)的整体偏离程度,,,所以我们选择它作为评价公平性(均匀性) 第卷第期  年月小型微型计算机系统MINIMICROSYSTEMSVolNo  Mar  的指标 实验设计我们前期工作发现在许多文献中推荐的对字符串散列效果很好的ELFhash函数对URL的散列效果并不好,同时推荐了两种已经应用于天网搜索引擎许久的对URL散列效果较好的哈希函数HfIp和hf在此基础上我们进一步发现稍加修改ELFhash函数便可以获得良好的均匀散布特性下面首先给出修改后的ELFhash函数(ELFhashxl)和HfIp以及hf三个函数的描述,再介绍我们的实验方法 待评估的散列函数 ELFhashxlELFhash源于UNIXSystemV,号称“实际生活散列函数中的典型魔术”,也是我们在信息查询研究工作中的首选,ELFhash被认为具有均匀散布特性我们前期工作已经证明针对URL集其糟糕的性能,在此仅给出修改后的ELFhashxl函数unsignedlongELFhashxl(charurl,unsignedlongsize){öösize是哈希表大小unsignedlongh=,gwhile(url){h=(h<<)urlif(g=hxFL)h^=g>>ööxF后跟个而不是个h=~g}returnhsize}第二、三个是由阎宏飞和谢正茂采用折叠方法设计的,一直用在我们的天网搜索引擎中,它们分别称为HfIp和hf HfIpunsignedintHfIp(charurl,intsize){unsignedintn=charb=(char)nfor(inti=i<strlen(url)i) bi^=urlireturnnsize} hfinthf(charurl,intsize){intresult=charptr=urlintcfor(inti=c=ptri) result=ciif(result<) result=resultreturnresultsize} 实验方法我们以天网搜索引擎年月搜集的个url序列为源数据,不放回随机抽取个长为万的URL数据片断,对M=、M=、M=分别比较三个哈希函数对它们的散布均匀性测度再就质数型表规模M=、M=和M=进行性能比较最后比较不同数据规模下,三个算法均匀性的变化趋势 实验结果 偶数型表规模如图所示,在M=时,对个数据集来说,ELFhashxl和hf的统计均匀性均高于HfIp,但是随着M的加大,hf的均匀性明显不如ELFhashxl和HfIp,ELFhashxl较HfIp又有稍好一些的统计均匀性图 三个哈希函数散布均匀性对比,M依次加大且均为偶数(横轴为个测试数据集,每组性能数据依次为ELFhashxl、HfIp和hf)  所以,我们初步可以认为在小哈希表尺寸的应用中(如文献提到的并行收集网页问题)可以优先考虑选择ELFhashxl和hf之一对于大规模的表尺寸来说(如文献提到的大规模url集的哈希查找问题),宜优先考虑选择ELFhashxl和HfIp之一 质数型表规模我们又对质数型表规模,重复了上述实验(见下页图),发现使用质数型表长能充分发挥哈希函数的均匀散布特性比如图之最左子图表明三个函数的均匀性都在以上,而图之最左子图中HfIp的性能低于此值综合对比图和图我们不难发现:图展示的所有性能对应地均大于等于图所以,建议使用哈希函数时,优先考虑使用质数型表长 不同数据规模如上节述,质数型表规模能较好的展现哈希函数的均匀性,所以我们选择,M=和M=分别考察三个函数在数据规模为万、万、万、万和万下的变化趋势如图所示,发现在小表长情况下(图左),ELFhashxl和期       肖明忠等:一个实用的针对URL的哈希函数  HfIp对大小不同的url集具有良好的均匀散布稳定特性(较hf曲线平稳)在大表长的情况下(图右),hf的性能随着数据规模的加大不如另二者,ELFhashxl稍好于HfIp 实验结果在总结这些实验结果之前,我们将证明哈希查找代价问题与哈希均匀性问题同一图 三个哈希函数散布均匀性对比,M依次加大且均为质数(横轴为个测试数据集,每组性能数据依次为ELFhashxl、HfIp和hf)  哈希查找代价问题:设有N个url字符串待处理,将这些字符串用散列函数h散列到M个槽中,对i(≤i≤M)号槽,散列到其中的url个数为xi我们假设查询每个url的概率是相等的,则对N个url各作一次查询的时间算术平均值,便可当作h的查询性能图 基于数据集的测试(横轴数据集大小,纵轴均匀性)测度按照通常散列表项的链表结构,对i号槽中第k个元素作查询,需要访问存储k次,所以,对散列在i号槽中的所有字符串都作一次查询,则需要访问存储xi(xi)次考虑所有的槽,我们可用下面的平均存储访问次数来表示散列函数h的查找代价,越小越好A(h)=N∑Mi=xi(xi)=∑Mi=xiN,其中∑Mi=xi=N()定理哈希查找代价问题与哈希均匀性问题同一,即是fairness(h)ΖA(h)证明fairness(h)=(E(x))E(x)=(∑Mi=xi)M(∑Mi=xi)=NM(∑Mi=xi)~o(ö∑Mi=xi),A(h)=N∑Mi=xi(xi)=∑Mi=xiN~o(∑Mi=xi)所以,两个哈希函数h和h,若有fairness(h)<fairness(h),则A(h)>A(h)反之亦然证毕故综合前述个实验的分析和上述定理,同时考虑平稳性和均匀性,不管是什么样的表规模和数据规模,我们认为针对url集合的哈希处理,ELFhashxl都是值得优先考虑的 讨 论通过对图、和的综合比较分析初步发现:随着M的增加,各哈希函数的均匀性呈下降趋势,我们将讨论这一问题然后将ELFhashxl哈希函数与时间复杂度较高的MD和SHA作了均匀性对比,更进一步展示ELFhashxl的实用性 实际理想均匀性测度公式()作了这样的假定:h把N个键值均匀散布到M个槽中,使得每个槽中恰拥有NöM个键值,则最优均匀性fairness(h)=然而,通常N关于M的模并非为,所以我们实际上能获得的最优均匀性(NM个槽有NöM个键值,MNM个槽有NöM个键值),按照公式()计算的话,实际理想均匀性:PF(N,M)= (N◊M)(NöM)(MN◊M)(NöM)M(N◊M)(NöM)(MN◊M)(NöM)()对图实验参数来说:PF(,)=PF(,)=PF(,)=但是图的各函数性能仍距实际理想较远,这驱使我们去考虑这样的问题:是否存在这样的哈希函数,其性能非常接近各个实际理想通过下节的讨论,我们发现:在许多文献中广泛         小 型 微 型 计 算 机 系 统       年推荐使用的SHA和MD哈希函数,也不具备这一特征 ELFhashxl与SHA、MD的性能对比由于SHA和MD较高的计算复杂性,所以在我们前述的性能对比中,并没有给出它们的性能情况,但是出于审查其与实际理想偏离的程度考虑,我们将比较MD,SHA和ELFhashxl这三个函数的性能图 ELFhashxl、MD和SHA性能对比(横轴为个测试数据集)图中可以发现这三个函数性能接近,离各个实际理想都相去较远,以及MD和SHA的计算复杂性,使得我们认为ELFhashxl是所知的函数中,针对URL集是最优的、最实用的当然,在对安全性要求高的场合下,宜选择SHA 结束语及未来的工作表示和查找信息是大多数计算机应用程序的核心,而哈希组织信息并提供高效的查找效率使之更是具有重要的研究地位与应用价值对它的研究不断能有新意的基本原因在于其优化性能在很大程度上取决于输入键的结构本文针对url字符串键值,在前期工作的基础上,提出了一个ELFhash函数的变型,并通过大量的实验表明它的散布均匀性总的说来优于文献中推荐使用的HfIp和hf函数在针对url集的哈希处理中,应优先考虑使用但是,我们也发现其性能较实际理想有一些差距,是否存在或设计出这样的哈希函数,使得其性能非常接近各个实际理想我们通过实验发现计算时间复杂性较高的MD和SHA算法也不具备这一特征在对ELFhash函数的变形处理中,我们也发现对其各个算法常数的修改,针对url集也可以获得较原算法ELFhash好得多的均匀性,其原因也将是我们下一步工作的重点References:LiXiaoming,FengWangsenTwoeffectivefunctionsonhashingURLJJournalofSoftware,,():CliffordA,ShafferDataStructureandAlgorithmAnalysisMPrenticeHall,北大天网http:ööepkueducnPekingUniversityTianwangSearchEngineEBöOLhttp:ööepkueducnCharlesJBashe,etalIBM’sEarlyComputersMAddisonWesley,Reading,Mass,JainR,ChiuD,HaweWAquantitativemeasureoffairnessanddiscriminationforresourceallocationinsharedcomputersystemsRDECResearchReportTR,SeptemberBhargavaR,GoelA,meyersonAUsingapproximatemajorizationtocharacterizeprotocolfairnessCIn:ProcSIGMETRICSöPerformance’,TriantafillouP,XiruhakiC,KoubarakisMTowardshighperformancePeertoPeercontentandresourcesharingsystemsCIn:ProcofCIDR,WorldWideWebConsortiumSiteEBöOLhttp:ööwwwworgöAddressingöURLöOverviewhtmlSchneierBAppliedcryptography:protocols,algorithms,andsouredcodeinc(secondeditionMJohnWileySons,附中文参考文献:李晓明,凤旺森两种对URL的散列效果很好的函数J软件学报,,():张 铭,刘晓丹(译)数据结构与算法分析M北京:电子工业出版社,年期       肖明忠等:一个实用的针对URL的哈希函数  

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/4

一个实用的针对URL的哈希函数

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利