Hash函数（精选4篇）
Hash函数 篇1
摘要：Hash函数也称散列函数,它是一种单向密码体制,可以将任意长度的输入信息经过变换后得到固定长度的输出。在数据完整性认证、数字签名等领域有广泛的应用,论文介绍了Hash函数的基本概念、特性及一般结构,对常用的Hash函数进行了对比分析,并对Hash函数的应用领域详细进行了研究,对以后的研究工作有一定的作用。
关键词：杂凑函数,加密解密,数字签名,消息认证
Ha sh函数也称杂凑函数或散列函数,通常用来构造数据的短“指纹”。即对任意长度的输入消息M,经过N次变换后,得到固定长度的输出。Ha sh函数是一种单向密码体制,它是一个从明文到密文的不可逆映射,只有加密过程,不能解密。Ha sh函数的这种单向性特征和输出数据的长度固定的特性使得它可以生成消息或其它数据块的“指纹”,在消息完整性认证、数字签名等领域有着广泛的应用[1]。
1 HASH函数概念及安全性要求
1.1 Ha sh函数概念[2]
一个Ha sh函数是满足以下要求的四元组(X,Y,K,H):
1)X代表所有消息的集合;
2)Y是所有消息指纹的集合;
3)K代表所有密钥的有限集;
4)H代表加密Ha sh函数;
1.2 HASH函数的安全性要求[3]
1)有数据压缩功能:能将任意长度的输入数据转换成一个固定长度的输出;
2)具有单向性:由H(M)计算消息指纹很容易,反之则不能,即对给定的一个散列值,不可能找出一条消息M'的散列值正好相等。
3)抗碰撞性:所谓碰撞性是指两个不同的消息M和M',如果它们的散列值相同,即H(M)=H(M'),则发生碰撞。如果M≠M',则有H(M)≠H(M'),即使M和M'差别非常小,甚至只有一个比特的差别,它们的散列值也会有很大的不同(强抗碰撞性);给定消息M和其散列值H(M),要找到另一个与M不同的消息M',使得H(M)=H(M')是不可能的(弱抗碰撞性)。
2 HASH函数的一般结构
安全Ha sh函数一般结构如下图所示,这是一种迭代结构Ha sh函数,对于输入的报文M,首先将其分为N个固定长度的分组,如果最后一个数据块不满足输入分组的长度要求,可以进行填充[4]。
3 安全HASH函数比较
安全Ha sh算法(SHA)由美国国家标准技术研究所NIST开发,作为联邦信息处理标准于1993年发表,1995年修订为SHA-1。SHA-1基于MD4算法,并且在设计方面很大程度上是模仿MD4的。后来还新增了SHA-256、SHA-384和SHA-512三个散列算法标准,它们的消息摘要长度分别为256、384和512,以便与AES的使用相匹配,现在最新的是SHA-3,以下是各种SHA的比较[5]:
4 HASH函数的应用
4.1 消息认证
消息认证的目的主要有两个:一个是验证信息的来源真实性,即信息来源认证;另一个是验证信息的完整性,即验证信息在公共信道传送或存储过程是否被篡改、重放或延迟等。可以用作认证的函数有消息加密函数、消息认证码(MAC)和散列函数三种,而散列函数是一个不需要密钥的公开函数,它将任意长度的输入消息映射成一个固定长度的输出值,度以此值作为认证标识[6]。
Ha sh函数可以将任意长度的输入消息M经过若干次变换,成为固定长度的输出,得到文档的散列值输出,即“消息指纹”可与放在安全地方的原有“指纹”进行比对,如果消息被修改,那么这个两个指纹就不会相等,从而表明此消息被篡改过。这就是保证了数据的完整性,实现消息认证。
4.2 数字签名
数字签名是一种给以电子形式存储的消息签名方法。并以某种形式将签名“绑”到所签文件上,与传统的手写签名具有同等的效果,并能通过一个公开的验证算法对它进行确认。
由于公钥密码学和对称密码学在加密和解密速度上的区别,在数字签名中往往先使用杂凑函数对消息M实施“压缩”运算,接着对消息M的杂凑值实施签名,这样既起到了保密作用,又提高了加密速度。对于在数字签名中使用的杂凑函数,要求它们具有更强的安全性能[7]。一个使用杂凑函数H(M)的数字签名方案中的合法用户Alice不能找到一对不同的消息(M,M')满足H(M)=H(M'),如果Alice能找到这样的消息,那她就可以签署消息M',后来却宣布她签名的消息是M'而不是M。如果找到这样的消息对在计算上是不可行的,那么我们就称它是抗碰撞(Collision Resistant)的或是碰撞自由(Collision Free)的。
4.3 其他应用
杂凑函数在现代密码学中具有非常广泛的用途,比如用于安全存储口令方面。基于Ha sh函数生成口令的散列值,比如在操作系统中保存用户的ID和他的口令散列值,而不是口令本身,这有助于提高系统的安全性。当用户进入系统时要求输入口令,这时系统重新计算用户输入口令的散列值并与系统中保存的数值相比较,当等时进入系统,否则将被系统拒绝[8]。
Ha sh函数在入侵检测和病毒扫描方面也有很好的应用,比如可以为系统中每个文件进行哈希函数运算得到安全的Ha sh值,如果某个文件被非法修改就可以及时发现。
5 结论
单向散列函数可选的方案比较多,一般有SHA、MD5和基于分组密码的构造,而其他方案实在没有得到足够的重视和研究,目前比较流行的还是SHA,它的散列值比其他的要长,比各种分组密码构造更快[9],并且由NSA研制,虽然山东大的王小云团队已在破解SHA-1上有很大的突破,但要投入实用还有很长的路要走,并且随着SHA-384、SHA-512及SHA-3的出现,我们坚信SHA在密码学上的应用还是有很大的前途。
参考文献
[1]Stinson D R.密码学原理与实践[M].冯登国,译.3版.北京:电子工业出版社,2009:130-180.
[2]Wenbo Mao.现代密码学理论与实践[M].王继林,伍前红,译.北京:电子工业出版社,2006:305-330.
[3]William Stallings.密码编码学与网络安全——原理与实践[M].孟庆树,王丽娜,傅建明,译.4版.北京:电子工业出版社,2006:229-249.
[4]Bruce Schneier.应用密码学协议、算法与C语言源程序[M].吴世忠,祝世雄,张文政.2版.北京:机械工业出版社,2010:307-329.
[5]Forouzan B A.Cryptography and Network Security[M].北京:清华大学出版社,2009:200-280.
[6]胡向东,魏琴芳,胡蓉.应用密码学[M].2版.北京:电子工业出版社,2011:166-200.
[7]Forouzan B A.Cryptography and Network Security[M].Bei-jing:Tsinghua university press,2009:363-385.
[8]William Stallings.Cryptography and Network Security[M].Beijing:Electronic industry press,2011:327-393.
[9]张月,李海青.浅析加密技术在保密通信中的应用[J].电脑知识与技术,2015(21):230-235.
Hash函数 篇2
关键词：认证协议,Hash链,Verilog HDL
0 引言
无线射频识别(Radio Frequency Identification, RFID)是一种无接触的数据采集和自动识别技术,由标签技术和识别装置技术组成,利用它可以在远距离、恶劣环境下对集群目标和移动目标进行快速信息采集和自动识别。
本文提出了一个基于Hash函数的RFID改进认证协议,然后采用Verilog HDL硬件编程语言,对标签和读写器之间的无线传输信道中的信号流进行仿真,此仿真对一个FPGA目标设备的硬件实现而言,可以得到一个快速的实现原型。
1 基于Hash函数的RFID改进认证协议
近年来,已经提出了许多RFID认证方案,这些方案所采用的安全机制主要有物理机制和密码机制。由于物理机制需要额外的物理设备或增加了RFID系统的成本,所以在最新的RFID安全方案中,多数采用密码机制。但是,标签资源有限,使得现有的许多成熟的安全认证协议不适合RFID系统。由于Hash函数具有快速、低耗的特点,所以基于Hash函数的RFID认证协议的设计近年来备受关注。本文中H、G表示来表示两个不同的抗碰撞的安全杂凑函数。
1.1 Hash链(Hash-Chain)[1]协议的介绍
在Hash链协议中,若采用两个不同杂凑函数的读写器向Tag发起认证时,Tag 总是给予不同的应答;另外,Hash链协议具有完美的前向安全性(由于G是单向函数,因此攻击者能够获得标签输出at,j,但是不能从at,j中获得st,j),其协议流程认证过程如图 1 所示。
在RFID系统运行之前,Tag和DB首先要共享一个初始秘密值 st,1,那么Tag和Reader之间第j次H认证过程如下:
(1)Reader向Tag发送Query认证请求。
(2)Tag使用当前的秘密值st,j计算at,j=G(st,j),并更新其秘密值为st,j+1=H(st,j)。Tag将at,j发送给Reader。
(3)Reader将at,j转发给DB。
(4)后端数据库系统针对所有的 Tag 数据项查找并计算是否存在某个 IDt(1≤t≤n)以及是否存在某个j(1≤j≤m,其中m为系统预设置的最大链长度) 使得at,j=G( Hj-1(st,1))成立。如果有,则认证通过,并将IDt发送给Tag;否则,认证失败。
从上述协议执行过程中可看出,第一,Hash链协议是一个单向认证协议,即只对Tag身份进行认证;第二,此时Tag是一个具有自主更新ID的主动式Tag;第三,只要攻击者截获某个at,j,它就可以进行重传攻击,伪装Tag通过认证;第四,当Tag发起认证时,后端数据库都要对每一个Tag进行j次杂凑运算,后端数据库计算载荷也很大。
1.2 基于Hash函数的RFID认证协议的设计
针对Hash-Chain协议是一个单向认证协议及其搜索效率低的问题,本文提出基于Hash函数的RFID改进认证协议。在改进协议中,后端数据库中增加了一个访问计数器k,为了提高其搜索数据的效率,这对于多个标签的RFID系统具有十分重要的意义。
(1)协议的初始条件和相关说明
在改进的认证协议中,DB(后端数据库)是授权的唯一可以追踪标签的实体,存储标签唯一的标识符IDi、访问计数器k及所有标签的初始化标识符si,k(1≤i≤n),组成序列对(IDi,k,si,k)和Hash函数G和H,还有一个随机数发生器;R(读写器)是没有密码保护功能的不可信装置;Ti(1≤i≤n,n为数据库中标签的最大数)是可读写的标签。每个Ti在出厂时存储一个随机设置的初始化标识符si,1,它是采用EEPROM存储,写标识信息并写入两个Hash函数G和H(标准化以后可以固化到标签ROM)。
(2) 协议认证过程
在RFID系统运行之前, DB和Ti共享一个标签出厂时随机设置的si,1R第k次访问标签的认证过程如图2所示。
Step 1:R产生一个随机数NR,并向T发送NR和Query认证请求;此时可能会发生三种情况:①没有标签响应;②一个标签响应;③多个标签同时响应。当发生多个标签冲突的时候,会执行一次冲突仲裁(collision arbitration)过程,如二进制搜索算法,执行完此算法后会从中选取一个T与R进行信息交互。
Step 2:T计算ri,k=G(si,k)⊕NR后,然后更新标识符为si,k+1=H(si,k)和访问计数器为k=k+1, 并将ri,k和k发送给R。
Step 3:R将ri,k和k转发给DB。
Step 4:DB通过检索计数器k找到与之相同的序列对,对每个序列的si,1计算rj,k=G(Hk-1(si,1)),检查rj,k与ri,k是否相等。若相等,则说明标签通过认证,更新k=k+1,si,k+1=Hk-1(si,1),并将(NR,H(IDj⊕NR))发给R;若不相等,则发送认证失败的消息给R,不进行更新。
Step 5:若T通过认证,R将(R,H(IDj⊕NR))转发给T。
Step 6:T收到消息5后,验证H(IDj⊕NR)=H(ID⊕NR)是否相同,若相同,则R通过认证。
(3)安全性分析
针对RFID协议面临的主要攻击[2,3],对改进协议进行安全性分析如下。
①重传攻击:
读写器向标签发送 Query和NR之后,攻击者获取标签的响应:ri,k=G(si,k⊕NR),k;在以后的认证过程中,攻击者响应ri,k=G(si,k⊕NR),k,从而对后端数据库发起重传攻击;
通过前一次对“标签”(实为攻击者)的认证和该协议中标签每次更新si,k+1=H(si,k),ri,k=G(si,k⊕NR),攻击者无法伪造ri,k=G(si,k⊕NR),因为读写器每次产生的随机数都是不同的,所以该协议对重传攻击具有安全性。
②假冒攻击:
攻击者伪装成合法的阅读器通过前向信道R→T向标签发送Query和NR;攻击者获取标签的响应:ri,k=G(si,k⊕NR),k,在下一次认证过程中,当真正合法的阅读器发送Query和N′R的时候,攻击者响应刚才所得的信息ri,k=G(si,k⊕NR),k。
但是由于阅读器在每一次认证会话过程中都会产生一个新的伪随机数,即NR≠N′R,所以攻击者就无法假冒合法标签进行假冒攻击。所以该协议对假冒攻击具有安全性。
③前向安全性:
由于G是单向函数,攻击者能够获得标签输出ri,k,但是不能从ri,k中获得si,k。因此改进的协议具有良好的前向安全性。
④追踪:
由于标签在每次询问后ri,k都将更新,并且同一标签在不同认证过程中,标签回应得ri,k的值也不相同,攻击者也无法确定此次通信的标签与下次通信的标签是否为同一标签,从而无法对标签进行有效跟踪。
⑤窃听:
即使攻击者可以窃听到读写器与标签之间通信的消息数据,由于重要的数据都使用了单向函数G或者H进行处理,所以攻击者无法获得任何有用信息,即协议能够较好地防御攻击者的窃听。
改进的协议和以上的安全性分析的前提是密钥ID绝对保密,不管在任何时候都要注意对密钥的严格保护。改进的协议属于静态ID的RFID认证协议,近年来同类的研究有Sarmar[4],Weis[5],Rhee[6]等文献。
2 协议仿真
在Actel Libero IDE version 8.5环境中,采用Verilog HDL语言[7]对无线传输信道中的信号流进行仿真,利用测试文件testbench对标签进行激励。仿真中采用的Hash函数采用CRC16循环校验码[8]来实现的。
2.1 消息的帧格式和规则
图3是提出新协议的消息交换过程。
在仿真中,伪随机数NR设定为8bit,标签的ID即密钥设定为16 bit, 帧头和帧尾都定义为十六进制的0xaa,即二进制为10101010,如图4所示。
2.2 模块设计
本文的仿真由接收模块、发送模块、状态机和存储器ROM组成,另外,还有CRC及LFSR(线性移位寄存器)。如图5所示标志了模块间的连接及数据信号的流向。
2.3 通用异步收发器
UART(Universal Asynchronous Receiver Transmitter)是各种设备之间进行相互通信的关键模块,通常采用数字信号进行通信。文中,规定每个消息的帧格式为64 bit(如图4所示),但发送端每次只发送8 bit,为此每发送一次8 bit信号需要进行一次并——串转换,每个消息共需要进行8次转换;在接收端需要处理64 bit的信号时,必须要把8 bit串行信号转换为一组8位的并行信号,待到8组并行信号全部转换完毕后输出64 bit数据,所以该仿真需要UART进行并——串和串——并转换。
UART是由发送模块、接收模块、顶层模块组成,下面分别介绍各个模块。
(1)发送模块
发送模块是把并行数据转换成串行数据并行,然后串行输出,如图6-7所示。
(2)接收模块
接收模块是把接收到的串行数据转换成并行数据后输出,收到的数据串后判断其是否有错,如图8-9所示。
(3)顶层模块
顶层模块是把发送模块和接收模块的对应端口连接在一起,并给UART设定输入输出引脚,如图10-11所示。
2.4 仿真
仿真中,data代表伪随机数NR为8 bit,在某一刻,使能信号able_en为1时,此时系统产生的伪随机数有效;标签标识符ID(密钥),存储在存储器中,为16 bit,设定为0x1010,u_din表示每个消息的输入,为64 bit;data_out表示每个消息的输出,为64 bit;data_change表示攻击测试信号通道,为64 bit, control_e为1时,表示通信过程中报错;control_a为1时,表示标签成功验证读写器,此时本次认证结束。
(1)协议的合法认证过程
在协议的合法验证中,查看state、u_din以及data_out的值的变化,验证过程如图12-17所示。
通过分析协议的合法验证,标签收到消息1:aa01ff00000000aa,然后将收到的消息与存储器中的消息对比后,得知符合其帧格式,表明该读写器不是假冒的读写器;当state为101时,标签收到消息3:aa03ff6f939800aa,然后通过存储器中的NR和ID计算CRC值,经验证该值与接收到的消息3的值相等,表明攻击者对消息3没有进行篡改。
(2)模拟攻击的认证过程
图18是模拟假冒读写器向标签发起询问请求的行为。此模拟攻击认证过程中的验证过程1与合法认证中的验证过程1相同,如图11所示,不在此赘述。
图18的验证过程表明,当state为010时,标签收到的消息1为bb01ff00000000bb,验证其帧头和帧尾不符合规定的消息1的帧格式,此过程模拟了读写器的假冒攻击。对于重传和跟踪攻击,由于仿真中每次NR在变化,所以攻击者无法通过此类方法对系统进行攻击。另外,由于Hash函数的单向性,攻击者不可能篡改消息3的内容。
3 结束语
本文通过分析现有的Hash链协议的安全隐患和其效率上的不足,提出了基于Hash函数的RFID改进认证协议;针对RFID认证协议的常见攻击类型,改进的协议可以抵抗假冒攻击、重传攻击等常见攻击;采用Verilog HDL硬件编程语言,对标签和读写器之间的信号流进行了仿真,此仿真对于FPGA目标设备的硬件实现,可以得到一个快速的原型。
参考文献
[1]Ohkubo M,Suzuki K,Kinoshita S.Hash-chain based for ward-se-cure privacy protection scheme for low-cost RFID[C]//Proceedingsof the 2004 Symposium on Cryptography and Information Security(SCIS 2004),Sendai,2004:719-724.
[2]丁振华,李锦涛,冯波.基于Hash函数的RFID安全认证协议研究[J].计算机研究与发展,2009,46(4):583-592.
[3]李振汕.RFID系统安全问题研究[J].网络安全技术与应用,2011(4):61-63.
[4]Ohkubo M,Suzuki K,Kinoshita S.Cryptographic approach to“Pri-vacy-Friendly”tags[EB/OL].[2007-10-07].http://www.rfidprivacy.us//2003//papers//ohkubo.pdf.
[5]周永彬,冯登国.RFID安全协议的设计与分析[J].计算机学报,2006,29(4):581-589.
[6]Rhee K,Kwak J,Kim S,et al.Challenge-response based RFID au-thentication protocol for distributed database environment[C]//Proc of the 2nd Int Conf on Security in Pervasive Computing.Ber-lin:Springer,2005:70-84.
[7]王伟.Verilog HDL程序设计与应用[M].北京:北京人民出版社,2005.
Hash函数 篇3
无线射频识别(Radio Frequency Identification,RFID)技术是一种自动识别技术,作为物联网的关键技术之一,应用领域已涉及日常生活的方方面面。而RFID系统中阅读器与标签之间的无线信道决定了RFID系统安全性差,易受到攻击。主要攻击手段有欺骗攻击、插入攻击、重放攻击、假冒攻击、跟踪以及拒绝服务攻击。因此,RFID的安全机制问题越来越重要。
目前,实现RFID安全机制所采用的主要方法分物理方法和采用安全认证机制的方法。安全认证机制通过消息传递来实现标签与读写器合法身份的确认。随着密码学的发展,已经提出多种RFID安全协议,具有代表性的是Hash-Lock、随机化Hash-Lock和Hash链协议,但这些协议也存在安全性问题。本文从RFID系统的安全机制入手,研究分析一种改进RFID安全认证协议。
2 改进的安全认证协议
本文提出的改进协议同样基于Hash函数,并引入读写器-标签双向认证的机制以及标签ID动态刷新机制。下文中所用的符号“‖”为字符串连接符号,符号“笒”为字符串异或符号,H(x)表示对x取哈希运算的值。
在改进协议中,后台服务器和标签共享一个密钥。一个RFID系统中密钥可以有多个,如每64个标签公用一个密钥,密钥可当作标签ID的索引号。一个RFID系统也可以只有一个密钥。本文改进协议中密钥K的数量的选取在一定程度上取决于RFID系统后台服务器的存储能力以及标签总的数量。如果标签数量众多并且服务器有足够的存储空间,那么可以选取多个密钥,每个密钥对应一定数量的标签以减少服务器搜寻标签ID的时间。如果系统中只有少量的标签,那么可以只有一个密钥。标签和读写器之间的通信数据采用Hash函数加密,标签和读写器之间的信息均动态更新。流程如图1所示。
改进协议流程如下:
1)标签进入读写器有效读取范围,读写器向标签发送查询命令Query和随机数R;
2)标签接收到查询命令后计算H(R‖Kj)发送回读写器;
3)读写器逐个对所有的Ki计算H(R‖Ki)并与接收到的H(R‖Kj)进行比较,若存在某个Ki与Kj的哈希值相同,则标签认证通过,并向标签发送读取指令Read以及H(Kj);
4)标签将接收到的H(Kj)与自身存储的H(Kj)’值进行对比,若一致,则读写器认证通过,标签计算H(R‖Kj‖IDi)返回给读写器;
5)读写器接收到H(R‖Kj‖IDi)后,向后台服务器发送H(R‖Kj‖IDi)、R、Kj。服务器根据接收到的Ki查询对应ID的存储区域,然后对该区域内的所有IDi计算H(R‖Kj‖IDi)并与接收到的值进行比较,若存在相同的值,则计算H(IDi茌R)并用H(IDi茌R)代替原来的IDi,同时原来的IDi存储为IDi’,并向读写器发送新的IDi。若不存在相同的值,则对该区域内所有的IDi’计算H(IDi’茌R)并与接收到的值进行比较,若存在与接收到的值相同的IDi’,则数据库保持IDi和IDi’不变,同时向读写器发送IDi;
6)读写器接收到IDi后向标签发送确认指令ACK,标签接收到ACK指令后用计算H(IDi茌R)并用H(IDi茌R)代替原来的IDi,至此读写器读取流程完成。
3 改进协议的安全性证明
为了规范证明改进协议的安全性,下面将采用经典的安全协议证明分析方法———BAN逻辑对改进协议进行形式化分析和证明。
假设D代表后台系统,R代表阅读器,T代表标签,S代表阅读器产生的随机数,K代表标签密钥,ID代表标签标识符,则协议开始的假设为:
改进协议的理想化模型:
其中由于读写器和后台系统之间是安全信道传输数据,所以相互信任,用后台系统D代替读写器T,又因为M1是以明文形式传输的,所以可以将上述模型简化为:
M2:D茳H(S,K)
M3:T茳H(K)
M4:D茳H(S,K,ID)
协议的安全目标:(1)D|≡T|~#(K)
下面证明改进协议能达到以上安全目标。
可得:D|≡T|~H(S,K)
由于D|~S,所以由D茳H(S,K)可以推出:D茳S,D茳K。再由规则
推出:D|≡T|~(S,K),得:D|≡T|~K(2)
综合(1)(2)可得:D|≡T|~#(K),达到安全目标(1)。
由M3:T茳H(K)和规则可知:T|≡D|~K,即达到安全目标(2)。
同目标(1)证明过程,由M4:D茳H(S,K,ID)、D|≡#(S)、安全目标(1):D|≡T|~#(K)、规则
和新鲜性规则可知:D|≡T|~#(ID),即达到安全目标(3)。
上述证明分析可知,本文改进协议能实现预期的安全目标D|≡T|~#(K)、T|≡D|~K和D|≡T|~ID,即能实现读写器与标签双向认证和读写器安全读取标签ID,且由于读写器读取标签数据时具有新鲜性,所以能有效防止标签位置跟踪。
4 改进协议的性能分析
在实际标签芯片制造中,一个电子标签可用于安全和隐私保护的门电路数量限制在5000个以内,而设计一个hash函数模块大约需要1700个门电路,因此在标签中嵌入hash函数模块是可行的。对比各个协议,假设读写器完成一次读取过程,RFID系统中标签的个数为N,改进协议中密钥的个数为M(M
通过对比不难发现本文协议不仅能够有效抵御各种攻击,安全性高,而且可以根据读写器和后台运算能力来选择恰当的密钥个数M,来提高系统的运算效率,协议中标签不需要内置随机数生成器,有效降低了标签的成本。
5 结束语
Hash函数 篇4
1 整数的Ha s h函数
常用的方法有三种:直接取余法、乘积取整法、平方取中法。下面我们对这三种方法分别进行讨论。以下假定我们的关键字是k, Hash表的容量是M, Hash函数为h (k) 。
1.1 直接取余法
我们用关键字k除以M, 取余数作为在Hash表中的位置。函数表达式可以写成:
例如, 表容量M=12, 关键值k=100, 那么h (k) =4。该方法的好处是实现容易且速度快, 是很常用的一种方法。但是如果选择的不好而偏偏标本又很特殊, 那么数据在Hash中很容易扎堆而影响效率。
对于M的选择, 在经验上, 我们一般选择不太接近2n的一个素数;如果关键字的值域较小, 我们一般在此值域1.1～1.6倍范围内选择。例如k的值域为[0, 600], 那么M=701即为一个不错的选择。竞赛的时候可以写一个素数生成器或干脆自己写一个“比较像素数”的数。
我用4000个数插入一个容量为701的Hash表, 得到的结果表1。
可见对于随机数据, 取余法的最大单元容量达到了期望容量的将近3倍。经测试, 在我的机器 (Pentium III 866MHz, 128MB RAM) 上, 该函数的运行时间大约是39ns, 即大约35个时钟周期。
1.2 乘积取整法
我们用关键字k乘以一个在 (0, 1) 中的实数A (最好是无理数) , 得到一个 (0, k) 之间的实数;取出其小数部分, 乘以M, 再取整数部分, 即得k在Hash表中的位置。函数表达式可以写成:
其中kAmod1表示kA的小数部分, 即kA-[kA]。例如, 表容量M=12, 种子A251 (A251是一个实际效果很好的选择) , 关键值k=100, 那么h (k) =9。
同样用4000个数插入一个容量为701的Hash表 (A5 1) , 得到的结果见表2。2
从公式中可以看出, 这个方法受M的影响是很小的, 在M的值比较不适合直接取余法的时候这个方法的表现很好。但是从上面的测试来看, 其表现并不是非常理想, 且由于浮点运算较多, 运行速度较慢。经反复优化, 在我的机器上仍需892ns才能完成一次计算, 即810个时钟周期, 是直接取余法的23倍。
1.3 平方取中法
我们把关键字k平方, 然后取中间的[log2M]位作为Hash函数值返回。由于k的每一位都会对其平方中间的若干位产生影响, 因此这个方法的效果也是不错的。但是对于比较小的k值效果并不是很理想, 实现起来也比较繁琐。为了充分利用Hash表的空间, M最好取2的整数次幂。例如, 表容量M=24=16, 关键值k=100, 那么h (k) =8。
用4000个数插入一个容量为512的Hash表 (注意这里没有用701, 是为了利用Hash表的空间) , 得到的结果见表3。
效果比我们想象的要差, 尤其是对于连续数据。但由于只有乘法和位运算, 该函数的速度是最快的。在我的机器上, 一次运算只需要23ns, 即19个时钟周期, 比直接取余法还要快一些。
比较一下这三种方法, 见表4。
从这表4中我们很容易看出, 直接取余法的性价比是最高的, 因此也是我们竞赛中用得最多的一种方法。
对于实数的Hash函数, 我们可以直接利用乘积取整法;而对于标本为其他类型数据的Hash函数, 我们可以先将其转换为整数, 然后再将其插入Hash表。下面我们来研究把其他类型数据转换成整数的方法。
2 字符串的Ha s h函数
字符串本身就可以看成一个256进制 (ANSI字符串为128进制) 的大整数, 因此我们可以利用直接取余法, 在线性时间内直接算出Hash函数值。为了保证效果, M仍然不能选择太接近2n的数;尤其是当我们把字符串看成一个2p进制数的时候, 选择M=2p-1会使得该字符串的任意一个排列的Hash函数值都相同。 (想想看, 为什么?)
常用的字符串Hash函数还有ELFHash, APHash等等, 都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数, 这些函数几乎不可能找到碰撞 (MD5前一段时间才刚刚被破解) 。
我们从Mark Twain的一篇小说中分别随机抽取了1000个不同的单词和1000个不同的句子, 作为短字符串和长字符串的测试数据, 然后用不同的Hash函数把它们变成整数, 再用直接取余法插入一个容量为1237的Hash表, 遇到冲突则用新字符串覆盖旧字符串。通过观察最后“剩下”的字符串的个数, 我们可以粗略地得出不同的Hash函数实际效果。 (见表5)
把1000个随机数用直接取余法插入容量为1237的Hash表, 其覆盖单元数也只达到了694, 可见后面的几种方法已经达到了极限, 随机性相当优秀。然而我们却很难选择, 因为不存在完美的、既简单又实用的解决方案。我一般选择JS Hash或SDBM Hash作为字符串的Hash函数。这两个函数的代码如下:
JSHash的运算比较复杂, 如果对效果要求不是特别高的话SDBMHash是一个很好的选择。
3 结论
本文对几个常用的Hash函数进行了总结性的介绍和分析, 并将其延伸到应用更加广泛的“与自然数建立一一对应”的过程。Hash是一种相当有效的数据结构, 充分体现了“空间换时间”的思想。在如今竞赛中内存限制越来越松的情况下, 要做到充分利用内存空间来换取宝贵的时间, Hash能够给我们很大帮助。我们应当根据题目的特点, 选择适合题目的数据结构来优化算法。对于组合与自然数的一一对应关系, 我还没有想到好的方法, 欢迎大家讨论。
参考文献
[1]Thomas H Cormen, Charles E Leiserson, Ronald L Riverst, Clifford Stein.Introduction to Algorithms.Second Edition.The MIT Press, 2001.
[2]刘汝佳, 黄亮.算法艺术与信息学竞赛[M].北京:清华大学出版社, 2004.