文档库 最新最全的文档下载
当前位置:文档库 › 关于对哈希算法的研究与应用_黄云轲

关于对哈希算法的研究与应用_黄云轲

关于对哈希算法的研究与应用_黄云轲
关于对哈希算法的研究与应用_黄云轲

关于对哈希算法的研究与应用

黄云轲,辛小龙,李成龙,李聿民 (西北大学数学系,西安 710069)

摘 要:

要:随着科学技术的不断发展,许多新的算法在各个领域中有了进一步的应用,其中技术较为先进的哈希算法,以其独特的计算方式受到了广泛的应用。本文主要从哈希算法的定义、特点、原理、应用等方面展开了深入的研究,供大家讨论研究。

关键词:

关键词:哈希算法;含义;原理;方式;应用 中图分类号:中图分类号:TP301.6 文献标识码:文献标识码:A 文章编号:文章编号:1007-9599(2012)03-0201-02

The Research and Application of the Hash Algorithm

Huang Yunke,Xin Xiaolong,Li Chenglong,Li Yumin

(Department of Mathematics, Northwest University, Xi'an 710069,China)

Abstract:With the continuous development of science and technology, many new algorithms have further applications in various fields in which technology is more advanced hash algorithm, with its unique method of calculation has been widely used. Mainly from the hash algorithm definition, characteristics, principles and applications, in-depth study for discussion study.

Keywords:Hash algorithm; Meaning; Principle; Way; Application

一、哈希算法的含义 哈希的英文名为Hash,意思为散列,它将任意长度的二进制值对应为固定长度的二进制值,这个值就是我们所要说的哈希值。哈希值的输出空间一般要比输入空间小很多,不一样的输入也会哈希成相同的输出。在哈希一段明文中,如果改变明文中的内容,会导致散列产生不一样的结果,如果要想找到哈希为同一个数值的不同的输入内容,是无法通过各种算法来实现的,因此我们可以利用散列值的这一特点来检验数据的完整性。哈希算法就是将哈希值的输出,它是用来形成某些数据消息或会话内容片段的散列值的计算方法。较为先进合理的哈希算法,可以通过对散列输入数据进行修改时,可以更改结果散列值中的所有位,所以散列对于数据的检测有很好的作用。哈希算法的方式很多,现在普遍在采用的方法有以下几种,分别为:MD2、MD4、MD5 和安全哈希算法(SHA-1)。 哈希表也叫做散列表,它根据已经设定好的哈希算法和处理数据问题的计算方式,将关键码值映射到一个有限的位置空间中,并关键码值的空间位置中的象,作为存储点,这种存放记录的数组形成的表叫做哈希表。这种对应的映射函数叫做哈希函数。在算法中所得到的存放空间就是哈希地址,也叫做散列地址。 二、哈希算法的原理 哈希算法的原理是根据数据帧的散列值服务器数计算出余数,通过这种方法来确定目前数据帧中的内容将会发向哪一个散列值服务器。实际上也可以说就是集合之间所产生的彼此对应的关系,相当于在一个集合内的一个数据帧映射到另一个集合内所对应的那个数据帧的过程。在这个过程中也会涉及到一个哈希算法的分布问题。哈希表的工作原理就是把一个数据帧按照某一种设定好的算法,比如说散列算法,将其转换为数字的形式,将这些数字对数组长度进行余数计算,取其余数,将结果作为该数组的下一个标记,将数值进行存储,并将其存储在这个数字下标下的数组空间内。如果发出有关哈希表的查询命令后,就可以使用散列函数将数据帧转换成其标记下对应的数组,从而从该空间内取得相应的散列值。散列表根据输入数值的变化而不断发生变化。因此,我们可以充分利用哈希算法中的数组定位功能来确定相应的数据位置。由于哈希算法的这一功能,可以快速的完成查找任务,这要同线性数据结构与表格、队列等计算方法相比速度已经有了很大的提升。 三、哈希算法的方式 (一)MD4算法 MD4算法是哈希算法中较为成熟的算法之一,它是由现任麻省理工学院(MIT)电子和计算机科学系Viterbi 讲座教授Ronald L. Rivest 在上个世纪九十年代出创造出来的一种哈希算法方式。MD 是指消息摘要的意思,是Message Digest 的缩写。它一般使用在32位的计算机处理器模块内,通过软件系统来实现其算法功能。MD4算法在计算过程中需要及时填补有关Message Digest 来保证Message Digest 的bit 位长度加上448后能够被512进行整除,之后,通过64位的二进制Message Digest 被填补进来,将信息制定为512bit,并且每个部分都需要通过以上方式进行处理。由于MD4本身存在安全性的问题,当时推出后,就曾被某些人进行了破译,对MD4中的第一步和第三步中存在的问题进行了攻击,例如,曾经Dobbertin 向公众演示,他通过一台计算机在几分钟内就找到了MD4中存在的漏洞,使通过

MD4加密的不同内容,得到了相同的加密结论。但是就整个MD4算法来说并没有完全的被破译,在此之后Ronald L. Rivest 对MD4中存在的漏洞进行了修补与改进。然而,由于MD4本身存在的安全性漏洞,还是被更为先进安全的算法所淘汰。但MD4算法为之后的MD5算法、sha-1算法、RIPEMD 算法等提供了很好的

理论基础。 (二)MD5算法 MD5算法是MD4算法的升级版,也是由Ronald L. Rivest 开发研制出的一种哈希算法方式。它与MD4算法相比安全性有了很大的提升,它在MD4的基础上增加了safety-belts 功能,使整个算法变得更加可靠。MD5的输入方式与MD4相同,还是保持了原理的512bit 的分组形式,它的输出方式是通过四个32bit 的连接形式。MD5在MD4的基础上加入了第四轮的计算模式,每一个步骤都是一一对应的固定值,改进了MD4中在第二轮、第三轮计算中的漏洞,完善了访问输入分组的次序,从而减小其对称性和相同性。通过这些变化,使得MD5与MD4相比变得复杂很多,整个运转速度也要比MD4慢一些,但是从整体安全性、抗冲突和抗分析方面有了很大的提高。 (三)SHA1算法 SHA1算法是由美国国家标准与技术研究院美国国家安全局设计出来的,主要是通过与DSA 算法配合在一起使用。SHA1算法也叫做安全哈希算法,主要应用于Digital Signature Standard

(下转第199页)

直行格——每根箭头的起点位置即是对应颜色方的直行格。每步行动落到这一点,就能直行到箭头所指的格子。

终点前通道 —— 终点前的六格即是对应颜色方的终点通道,这里不会产生“跳跃”。

(二)骰子。飞行棋里有一个骰子,骰子是正方体的,有六个面分别是一个点、二个点、三个点、四个点、五个点和六个点。用来决定玩家走几步,正面是几就走几步,每次掷到6可以出动一个棋子,并且可以再次掷骰子,直至不是六为止。

(三)四方棋子。有四方棋子组成,分别四种颜色,每一方分别有四个棋子。

四、游戏的框架结构设计及流程

(一)游戏的框架结构。游戏的框架结构主要由玩家,鼠标,对战地图和游戏控制组成。玩家通过鼠标控制游戏中对战地图的操作对象——骰子和棋子,骰子和棋子遵循游戏规则,游戏规则决定棋子走的方向和步数,最后棋子所发生的变化映射到对战地图上。

(二)创建对战地图。在创建对战地图时,主要考虑点:幸运轮盘位置、地雷位置、时空隧道位置、暂停位置;关卡在对战地图上的对应的显示图形;玩家棋子骰子在对战地图上的显示图形。

(三)游戏类(Game)。游戏类(Game)功能:1.实现游戏初始化设置;2.展示游戏开始界面以及角色设置;3.控制游戏进度、实现游戏规则。

在游戏正式开始以前必须要清理掉没用的和错误的数据,为后面的正常运行准备一个“干净”的环境,这样程序的正确运行也为调试带来方便,所以首先要进行初始化。设计游戏类的关键:两个玩家轮流掷骰子,如果上轮走到暂停关卡,停掷一次飞行棋游戏类实现流程图如图1所示。

五、游戏的实现

启动游戏后,跳出游戏选择界面,有四个角色可供选择,分别是戴高乐、艾森豪威尔、麦克阿萨、巴顿。分别双方分别选择自己的角色开始对决。

六、总结

通过编写这个程序,我体会最为深刻的一点是系统架构和设计模式的重要性。即使是对于一个并不大的程序,代码的组织都是非常重要的,因为这关系到日后的维护以及扩展。这个游戏之中,可以直接获得一个完整的飞行棋人机对弈算法的源代码级模块。但是对于系统的架构,却完全是自己的事情,几千上万行的代码需要通过合适的方法组织起来,从而使编写代码更加有条理,更加符合标准,这才是最重要的。

在刚开始编写这个程序的时候,我幼稚地认为其中最重要的是博弈树算法。但是头一个月编写程序的时候却发现程序越写越不容易维护,可见是我走错了方向。后来我向老师讨教,他告诉我:我们的先人早已为我们准备好了各种精良可用的现成算法,我们所要做的就是直接“拿来主义”罢了;但是对于代码的组织(也就是软件的架构)才是真正软件工业的核心部分,因为软件事实上是直接和经济挂钩的,因此我们必须在编写代码之前选择一种最为合适的方法来组织这些代码,否则我们将会失去更多的时间和金钱。

于是,我将以前写的代码全部删除,认真地思考了三天的时间。我开始发现其实飞行棋的设计并不是纯数学——正相反,数学只占了很小的一部分。它其实是一种哲学,一种有着数学美感的哲学。

参考文献:

[1][美]罗林斯.[美]莫里斯著,付煜等译.游戏架构与设计[M].红旗出版社.2005.

[2][美]Clayton Walnum著王国春,施妍然译.游戏编程 21天自学通[M].清华大学出版社,2001

[3]姜波.Visual Basic https://www.wendangku.net/doc/b210643891.html,游戏开发实例[M].机械工业出版社,2005

[作者简介]谢云燕(1988-),女,哈尔滨师范大学计算机科学与信息工程学院,本科生,研究方向为计算机教育。

(上接第201页)

DSS里面定义的数字签名算法。SHA1算法长度一般为160bit的Message Digest,SHA1在接收消息摘要的过程中,可以利用Message Digest来检查数据的完整情况。它不会从Message Digest中还原相关的内容,此外两个不同的Message Digest不会产生相同的Message Digest,因此SHA1具有很强的brute-force性能。SHA1的计算方式是基于MD4的算法原理,它的填补和分组模式与MD5是一样的,但是在算法中,SHA1的非线性函数、循环左移运算和加法常数与MD5的运算方式有一定的差异,SHA1的安全性和稳定性比MD5算法更加可靠,且运算速度也有了一定的提高。

四、哈希算法的应用

(一)数字签名方面的应用

哈希算法是现阶段较为先进的加密算法之一,在数字签名方面经常会应用到这一技术。在数字签名过程中,首先要确定出双方认同的哈希算法和签名的方式,签名的一方先要计算出数据文件的哈希值,然后利用哈希值进行非对称算法,得到数字签名。对方在检查签名的过程中,对这条数据信息进行哈希计算,对签字方的哈希值进行比对,比对的方法也是利用非对称算法进行验证。

(二)校对信息方面的应用

在对文件信息校对的过程中使用最多、最为普遍的算法就是哈希算法,其中以MD5算法最为常见。因为MD5算法在信息校对中具有奇偶校验法和循环冗余码校验无法比拟的优势,即具有防止对数据进行篡改的能力,有效的阻止了黑客或其他人员对相关数据文件内容进行恶意的修改和破坏,保证了数据的正确性。

五、结语

总之,哈希算法是目前较为先进的加密算法,它以其单向性、抗冲突性、映射分布均匀性和差分分布均匀性等特点,广泛应用于工业、商业等各个领域之中,但是由于其内部结构还存在很大的发展性,有待于相关技术人员对其进行更深一步的拓展,使其发挥出更好的作用。

参考文献:

[1]王勇平.《哈希算法的研究与发展》.北京.创新出版社,2003(1)

[2]李洪山.《浅谈MD5算法的探究与开发》.电子技术书刊,2004(01)

[3]刘温筠.《关于对SHA1算法的分析与研究》.河北文化出版社,2002(11)

[4]孙清泉,徐卫国,康健.《关于对哈希表的理解与探讨》.现代教育出版社,2008,1

哈希算法散列

计算机算法领域 基本知识 Hash,一般翻译做“散列”,也有直接音译为”哈希“的,就是把任意长度的输入(又叫做预映射,pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 HASH主要用于信息安全领域中加密算法,他把一些不同长度的信息转化成杂乱的128位的编码里,叫做HASH值. 也可以说,hash就是找到一种数据内容和数据存放地址之间的映射关系 基本概念 * 若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function),按这个思想建立的表为散列表。 * 对不同的关键字可能得到同一散列地址,即key1≠key2,而f(key1)=f(key2),这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“象” 作为记录在表中的存储位置,这种表便称为散列表,这一映象过程称为散列造表或散列,所得的存储位置称散列地址。 * 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。 常用的构造散列函数的方法 散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快地定位ǐ 1. 直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b,其中a和b为常数(这种散列函数叫做自身函数) 2. 数字分析法 3. 平方取中法 4. 折叠法 5. 随机数法 6. 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即H(key) = key MOD p, p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义词。 处理冲突的方法 1. 开放寻址法;Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列,可有下列三种取法: 1. di=1,2,3,…, m-1,称线性探测再散列; 2. di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列;

hash算法

Hash,一般翻译做"散列",也有直接音译为"哈希"的,就是把任意长度的输入(又叫做预映射,pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。 数学表述为:h = H(M) ,其中H( )--单向散列函数,M--任意长度明文,h--固定长度散列值。 在信息安全领域中应用的Hash算法,还需要满足其他关键特性: 第一当然是单向性(one-way),从预映射,能够简单迅速的得到散列值,而在计算上不可能构造一个预映射,使其散列结果等于某个特定的散列值,即构造相应的M=H-1(h)不可行。这样,散列值就能在统计上唯一的表征输入值,因此,密码学上的Hash 又被称为"消息摘要(message digest)",就是要求能方便的将"消息"进行"摘要",但在"摘要"中无法得到比"摘要"本身更多的关于"消息"的信息。 第二是抗冲突性(collision-resistant),即在统计上无法产生2个散列值相同的预映射。给定M,计算上无法找到M',满足H(M)=H(M') ,此谓弱抗冲突性;计算上也难以寻找一对任意的M和M',使满足H(M)=H(M') ,此谓强抗冲突性。要求"强抗冲突性"主要是为了防范所谓"生日攻击(birthday attack)",在一个10人的团体中,你能找到和你生日相同的人的概率是2.4%,而在同一团体中,有2人生日相同的概率是11.7%。类似的,当预映射的空间很大的情况下,算法必须有足够的强度来保证不能轻易找到"相同生日"的人。 第三是映射分布均匀性和差分分布均匀性,散列结果中,为0 的bit 和为 1 的bit ,其总数应该大致相等;输入中一个bit 的变化,散列结果中将有一半以上的bit 改变,这又叫做"雪崩效应(avalanche effect)";要实现使散列结果中出现1bit 的变化,则输入中至少有一半以上的bit 必须发生变化。其实质是必须使输入中每一个bit 的信息,尽量均匀的反映到输出的每一个bit 上去;输出中的每一个bit,都是输入中尽可能多bit 的信息一起作用的结果。 Damgard 和Merkle 定义了所谓"压缩函数(compression function)",就是将一个固定长度输入,变换成较短的固定长度的输出,这对密码学实践上Hash 函数的设计产生了很大的影响。Hash函数就是被设计为基于通过特定压缩函数的不断重复"压缩"输入的分组和前一次压缩处理的结果的过程,直到整个消息都被压缩完毕,最后的输出作为整个消息的散列值。尽管还缺乏严格的证明,但绝大多数业界的研究者都同意,如果压缩函数是安全的,那么以上述形式散列任意长度的消息也将是安全的。这就是所谓Damgard/Merkle 结构: 在下图中,任意长度的消息被分拆成符合压缩函数输入要求的分组,最后一个分组可能需要在末尾添上特定的填充字节,这些分组将被顺序处理,除了第一个消息分组将与散列初始化值一起作为压缩函数的输入外,当前分组将和前一个分组的压缩函数输出一起被作为这一次

什么是哈希函数

什么是哈希函数 哈希(Hash)函数在中文中有很多译名,有些人根据Hash的英文原意译为“散列函数”或“杂凑函数”,有些人干脆把它音译为“哈希函数”,还有些人根据Hash函数的功能译为“压缩函数”、“消息摘要函数”、“指纹函数”、“单向散列函数”等等。 1、Hash算法是把任意长度的输入数据经过算法压缩,输出一个尺寸小了很多的固定长度的数据,即哈希值。哈希值也称为输入数据的数字指纹(Digital Fingerprint)或消息摘要(Message Digest)等。Hash函数具备以下的性质: 2、给定输入数据,很容易计算出它的哈希值; 3、反过来,给定哈希值,倒推出输入数据则很难,计算上不可行。这就是哈希函数的单向性,在技术上称为抗原像攻击性; 4、给定哈希值,想要找出能够产生同样的哈希值的两个不同的输入数据,(这种情况称为碰撞,Collision),这很难,计算上不可行,在技术上称为抗碰撞攻击性; 5、哈希值不表达任何关于输入数据的信息。 哈希函数在实际中有多种应用,在信息安全领域中更受到重视。从哈希函数的特性,我们不难想象,我们可以在某些场合下,让哈希值来“代表”信息本身。例如,检验哈希值是否发生改变,借以判断信息本身是否发生了改变。` 怎样构建数字签名 好了,有了Hash函数,我们可以来构建真正实用的数字签名了。 发信者在发信前使用哈希算法求出待发信息的数字摘要,然后用私钥对这个数字摘要,而不是待发信息本身,进行加密而形成一段信息,这段信息称为数字签名。发信时将这个数字签名信息附在待发信息后面,一起发送过去。收信者收到信息后,一方面用发信者的公钥对数字签名解密,得到一个摘要H;另一方面把收到的信息本身用哈希算法求出另一个摘要H’,再把H和H’相比较,看看两者是否相同。根据哈希函数的特性,我们可以让简短的摘要来“代表”信息本身,如果两个摘要H和H’完全符合,证明信息是完整的;如果不符合,就说明信息被人篡改了。 数字签名也可以用在非通信,即离线的场合,同样具有以上功能和特性。 由于摘要一般只有128位或160位比特,比信息本身要短许多倍,USB Key或IC卡中的微处理器对摘要进行加密就变得很容易,数字签名的过程一般在一秒钟内即可完成。

哈希表的设计与实现 课程设计报告

一: 需求分析 (2) 三: 详细设计(含代码分析) (4) 1.程序描述: (4) 2具体步骤 (4) 四调试分析和测试结果 (7) 五,总结 (9) 六.参考文献; (10) 七.致谢 (10) 八.附录 (11)

一: 需求分析 问题描述:设计哈希表实现电话号码查询系统。 基本要求 1、设每个记录有下列数据项:电话号码、用户名、地址 2、从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表; 3、采用再哈希法解决冲突; 4、查找并显示给定电话号码的记录; 5、查找并显示给定用户名的记录。 6、在哈希函数确定的前提下,尝试各种不同类型处理冲突的方法(至少 两种),考察平均查找长度的变化。 二: 概要设计 进入主函数,用户输入1或者2,进入分支选择结构:选1:以链式方法建立哈希表,选2:以再哈希的方法建立哈希表,然后用户输入用户信息,分别以上述确定的方法分别以用户名为检索以及以以电话号码为检索将用户信息添加到哈希表,.当添加一定量的用户信息后,用户接着输入用户名或者电话号码分别以用户名或者电话号码的方式从以用户名或电话号码为检索的哈希表查找用户信息.程序用链表的方式存储信息以及构造哈希表。 具体流程图如下所示:

三: 详细设计(含代码分析) 1.程序描述: 本程序以要求使用哈希表为工具快速快速查询学生信息,学生信息包括电话号码、用户名、地址;用结构体存储 struct node { string phone; //电话号码 string name; //姓名 string address;//地址 node *next; //链接下一个地址的指针 }; 2具体步骤 1. 要求主要用在哈希法解决冲突,并且至少尝试用两种方法解决冲突,定义两个指针数组存储信息node *infor_phone[MAX]; node *infor_name[MAX];前者以电话号码为关键字检索哈希表中的信息,后者以姓名为关键字检索哈希表中的信息 用链式法和再哈希法解决冲突: int hash(string key) //以姓名或者电话号码的前四位运算结果作为哈{ //希码 int result=1,cur=0,i; if(key.size()<=4) i=key.size()-1; else i=4; for(;i>=0;i--) { cur=key[i]-'0'; result=result*9+cur; } result%=(MOD); return result;

一致性哈希算法应用及优化(最简洁明了的教程)

一致性哈希算法的应用及其优化 一.简单哈希算法 哈希(Hash)就是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,使得散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。哈希算法是一种消息摘要算法,虽然哈希算法不是一种加密算法,但由于其单向运算,具有一定的不可逆性使其成为加密算法中的一个重要构成部分。 二.分布式缓存问题 哈希算法除了在数据加密中的运用外,也可以用在常见的数据分布式技术中。哈希计算是通过求模运算来计算哈希值的,然后根据哈希值将数据映射到存储空间中。设有由N 个存储节点组成的存储空间,采用简单哈希计算将一个数据对象object 映射到存储空间上的公式为:Hash(object)% N。 现在假设有一个网站,最近发现随着流量增加,服务器压力越来越大,之前直接读写数据库的方式已经不能满足用户的访问,于是想引入Memcached作为缓存机制。现在一共有三台机器可以作为Memcached服务器,如下图1所示。

图1.三台memcached服务器 可以用简单哈希计算:h = Hash(key) % 3 ,其中Hash是一个从字符串到正整数的哈希映射函数,这样能够保证对相同key的访问会被发送到相同的服务器。现在如果我们将Memcached Server分别编号为0、1、2,那么就可以根据上式和key计算出服务器编号h,然后去访问。 但是,由于这样做只是采用了简单的求模运算,使得简单哈希计算存在很多不足: 1)增删节点时,更新效率低。当系统中存储节点数量发生增加或减少时,映射公式将发生变化为Hash(object)%(N±1),这将使得所有object 的映射位置发生变化,整个系统数据对象的映射位置都需要重新进行计算,系统无法对外界访问进行正常响应,将导致系统处于崩溃状态。 2)平衡性差,未考虑节点性能差异。由于硬件性能的提升,新添加的节点具有更好的承载能力,如何对算法进行改进,使节点性能可以得到较好利用,也是亟待解决的一个问题。 3)单调性不足。衡量数据分布技术的一项重要指标是单调性,单调性是指如果已经有一些内容通过哈希计算分派到了相应的缓冲中,当又有新的缓冲加入到系统中时,哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。 由上述分析可知,简单地采用模运算来计算object 的Hash值的算法显得过于简单,存在节点冲突,且难以满足单调性要求。

哈 希 常 见 算 法 及 原 理

数据结构与算法-基础算法篇-哈希算法 1. 哈希算法 如何防止数据库中的用户信息被脱库? 你会如何存储用户密码这么重要的数据吗?仅仅 MD5 加密一下存储就够了吗? 在实际开发中,我们应该如何用哈希算法解决问题? 1. 什么是哈希算法? 将任意长度的二进制值串映射成固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。 2. 如何设计一个优秀的哈希算法? 单向哈希: 从哈希值不能反向推导出哈希值(所以哈希算法也叫单向哈希算法)。 篡改无效: 对输入敏感,哪怕原始数据只修改一个Bit,最后得到的哈希值也大不相同。 散列冲突: 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小。 执行效率: 哈希算法的执行效率要尽量高效,针对较长的文本,也能快速计算哈

希值。 2. 哈希算法的常见应用有哪些? 7个常见应用:安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。 1. 安全加密 常用于加密的哈希算法: MD5:MD5 Message-Digest Algorithm,MD5消息摘要算法 SHA:Secure Hash Algorithm,安全散列算法 DES:Data Encryption Standard,数据加密标准 AES:Advanced Encryption Standard,高级加密标准 对用于加密的哈希算法,有两点格外重要,第一点是很难根据哈希值反向推导出原始数据,第二点是散列冲突的概率要小。 在实际开发中要权衡破解难度和计算时间来决定究竟使用哪种加密算法。 2. 唯一标识 通过哈希算法计算出数据的唯一标识,从而用于高效检索数据。 3. 数据校验 利用哈希算法对输入数据敏感的特点,可以对数据取哈希值,从而高效校验数据是否被篡改过。 4. 散列函数 1.如何防止数据库中的用户信息被脱库?你会如何存储用户密码这么重要的数据吗?

单向散列函数算法Hash算法

单向散列函数算法(Hash算法): 一种将任意长度的消息压缩到某一固定长度(消息摘要)的函数(过程不可逆),常见的单向散列算法有MD5,SHA.RIPE-MD,HAVAL,N-Hash 由于Hash函数的为不可逆算法,所以软件智能使用Hash函数作为一个加密的中间步骤 MD5算法: 即为消息摘要算法(Message Digest Algorithm),对输入的任意长度的消息进行预算,产生一个128位的消息摘要 简易过程: 1、数据填充..即填出消息使得其长度与448(mod 512)同余,也就是说长度比512要小64位(为什么数据长度本身已经满足却仍然需要填充?直接填充一个整数倍) 填充方法是附一个1在后面,然后用0来填充.. 2、添加长度..在上述结果之后附加64位的消息长度,使得最终消息的长度正好是512的倍数.. 3、初始化变量..用到4个变量来计算消息长度(即4轮运算),设4个变量分别为A,B,C,D(全部为32位寄存器)A=1234567H,B=89abcdefH,C=fedcba98H,D=7654321H 4、数据处理..首先进行分组,以512位为一个单位,以单位来处理消息.. 首先定义4个辅助函数,以3个32为双字作为输入,输出一个32为双字 F(X,Y,Z)=(X&Y)|((~X)&Z) G(X,Y,Z)=(X&Z)|(Y&(~Z)) H(X,Y,Z)=X^Y^Z I(X,Y,Z)=Y^(X|(~Z)) 其中,^是异或操作 这4轮变换是对进入主循环的512为消息分组的16个32位字分别进行如下操作: (重点)将A,B,C,D的副本a,b,c,d中的3个经F,G,H,I运算后的结果与第四个相加,再加上32位字和一个32位字的加法常数(所用的加法常数由这样一张表T[i]定义,期中i为1至64之中的值,T[i]等于4294967296乘以abs(sin(i))所得结果的整数部分)(什么是加法常数),并将所得之值循环左移若干位(若干位是随机的??),最后将所得结果加上a,b,c,d之一(这个之一也是随机的?)(一轮运算中这个之一是有规律的递增的..如下运算式),并回送至A,B,C,D,由此完成一次循环。(这个循环式对4个变量值进行计算还是对数据进行变换??) For i=0 to N/16 do For j=0 to 15 do Set X[i] to M[i*16+j] End AA = A BB=B CC=C DD=D //第一轮,令[ABCD K S I]表示下面的操作: //A=B+((A+F(B,C,D)+X[K]+T[I])<<

哈 希 常 见 算 法 及 原 理

计算与数据结构篇 - 哈希算法 (Hash) 计算与数据结构篇 - 哈希算法 (Hash) 哈希算法的定义和原理非常简单,基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。 构成哈希算法的条件: 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法)对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同; 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小; 哈希算法的执行效率要尽量高效,针对较长的文本,也能快速地计算出哈希值。 哈希算法的应用(上篇) 安全加密 说到哈希算法的应用,最先想到的应该就是安全加密。最常用于加密的哈希算法是 MD5(MD5 Message-Digest Algorithm,MD5 消息摘要算法)和 SHA(Secure Hash Algorithm,安全散列算法)。 除了这两个之外,当然还有很多其他加密算法,比如 DES(Data Encryption Standard,数据加密标准)、AES(Advanced Encryption Standard,高级加密标准)。

前面我讲到的哈希算法四点要求,对用于加密的哈希算法来说,有两点格外重要。第一点是很难根据哈希值反向推导出原始数据,第二点是散列冲突的概率要很小。 不过,即便哈希算法存在散列冲突的情况,但是因为哈希值的范围很大,冲突的概率极低,所以相对来说还是很难破解的。像 MD5,有 2^128 个不同的哈希值,这个数据已经是一个天文数字了,所以散列冲突的概率要小于 1-2^128。 如果我们拿到一个 MD5 哈希值,希望通过毫无规律的穷举的方法,找到跟这个 MD5 值相同的另一个数据,那耗费的时间应该是个天文数字。所以,即便哈希算法存在冲突,但是在有限的时间和资-源下,哈希算法还是被很难破解的。 对于加密知识点的补充,md5这个算法固然安全可靠,但网络上也有针对MD5中出现的彩虹表,最常见的思路是在密码后面添加一组盐码(salt), 比如可以使用md5(1234567.'2019@STARK-%$#-idje-789'),2019@STARK-%$#-idje-789 作为盐码起到了一定的保护和安全的作用。 唯一标识(uuid) 我们可以给每一个图片取一个唯一标识,或者说信息摘要。比如,我们可以从图片的二进制码串开头取 100 个字节,从中间取 100 个字节,从最后再取 100 个字节,然后将这 300 个字节放到一块,通过哈希算法(比如 MD5),得到一个哈希字符串,用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中,这样就可以减少很多工作量。

哈希表的设计与实现-数据结构与算法课程设计报告

合肥学院 计算机科学与技术系 课程设计报告 2009 ~2010 学年第二学期 课程数据结构与算法 课程设计名称哈希表的设计与实现 学生姓名王东东 学号0804012030 专业班级08计本(2) 指导教师王昆仑、李贯虹 2010 年5 月

课程设计目的 “数据结构与算法课程设计”是计算机科学与技术专业学生的集中实践性环节之一, 是学习“数据结构与算法”理论和实验课程后进行的一次全面的综合练习。其目的是要达到 理论与实际应用相结合,提高学生组织数据及编写程序的能力,使学生能够根据问题要求和 数据对象的特性,学会数据组织的方法,把现实世界中的实际问题在计算机内部表示出来并 用软件解决问题,培养良好的程序设计技能。 一、问题分析和任务定义 1、问题分析 要完成如下要求:设计哈希表实现电话号码查询系统。 实现本程序需要解决以下几个问题: (1)如何定义一个包括电话号码、用户名、地址的节点。 (2)如何以电话号码和用户名为关键字建立哈希表。 (3)用什么方法解决冲突。 (4)如何查找并显示给定电话号码的记录。 (5)如何查找并显示给定用户名的记录。 2 任务定义 1、由问题分析知,本设计要求分别以电话号码和用户名为关键字建立哈希表,z在此基 础上实现查找功能。本实验是要我们分析怎么样很好的解决散列问题,从而建立一比较合理 的哈希表。由于长度无法确定,并且如果采用线性探测法散列算法,删除结点会引起“信息 丢失”的问题。所以采用链地址法散列算法。采用链地址法,当出现同义词冲突时,可以使 用链表结构把同义词链接在一起,即同义词的存储地址不是散列表中其他的空地址。 根据问题分析,我们可以定义有3个域的节点,这三个域分别为电话号码char num[30],姓名char name[30],地址char address[30]。这种类型的每个节点对应链表中的每个节点,其中电话号码和姓名可分别作关键字实现哈希表的创建。 二、数据结构的选择和概要设计 1、数据结构的选择 数据结构:散列结构。 散列结构是使用散列函数建立数据结点关键词与存储地址之间的对应关系,并提供多 种当数据结点存储地址发生“冲突”时的处理方法而建立的一种数据结构。 散列结构基本思想,是以所需存储的结点中的关键词作为自变量,通过某种确定的函 数H(称作散列函数或者哈希函数)进行计算,把求出的函数值作为该结点的存储地址,并 将该结点或结点地址的关键字存储在这个地址中。 散列结构法(简称散列法)通过在结点的存储地址和关键字之间建立某种确定的函数 关系H,使得每个结点(或关键字)都有一个唯一的存储地址相对应。 当需要查找某一指定关键词的结点时,可以很方便地根据待查关键字K计算出对应的“映像”H(K),即结点的存储地址。从而一次存取便能得到待查结点,不再需要进行若干次的 比较运算,而可以通过关键词直接计算出该结点的所在位置。

哈希算法介绍

哈希算法介绍 LG GROUP system office room 【LGA16H-LGYY-LGUA8Q8-LGA162】

哈希算法简介

目录 1哈希算法概念 ...................................................... 2哈希函数 .......................................................... 3冲突的解决方法 .................................................... 4哈希算法应用 ......................................................

关键词: 算法、哈希、c语言 摘要: 哈希算法在软件开发和Linux内核中多次被使用,由此可以见哈希算法的实用性和重要性。本文介绍了哈希算法的原理和应用,并给出了简略的代码实现,以便读者理解。

1哈希算法概念 哈希(hash 散列,音译为哈希)算法将任意长度的二进制值映射为固定长度的较小二进制值,这个小的二进制值称为哈希值。 哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的哈希算法都将产生不同的值。要找到散列为同一个值的两个不同的输入,在计算上是不可能的,所以数据的哈希值可以检验数据的完整性。 哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映象到一个有限的地址区间上,并以关键字在地址区间中的项作为记录在表中的存储位置,这种表称为哈希表,所得存储位置称为哈希地址。作为线性数据结构与表格和队列等相比,哈希表无疑是查找速度比较快的一种。 查找一般是对项的摸个部分(及数据成员)进行,这部分称为键(key)。例如,项可以由字符串作为键,附带一些数据成员。 理想的哈希表数据结构只不过是一个包含一些项的具有固定大小的数组。 通常的习惯是让项从0到 TableSize-1之间变化。 将每个键映射到0到TableSize-1 这个范围中的某个 数,并且将其放到适当的单元中,这个映射就称为散列函数 (hash funciton)。 如右图,john被散列到3,phil被散列到4,dave 被散列 到6,mary被散列到7. 这是哈希的基本思想。剩下的问题则是要选择一个函数, 决定当两个键散列到同一个值的时候(称为冲突),应该做 什么。

哈 希 常 见 算 法 及 原 理 ( 2 0 2 0 )

哈希算法乱谈(摘自知乎) 最近【现场实战追-女孩教-学】初步了解了Hash算法的相关知识,一些人的见解让我能够迅速的了解相对不熟悉的知识,故想摘录下来,【QQ】供以后温故而知新。 HASH【⒈】算法是密码学的基础,比较常用的有MD5和SHA,最重要的两【О】条性质,就是不可逆和无冲突。 所谓不【1】可逆,就是当你知道x的HASH值,无法求出x; 所谓无【б】冲突,就是当你知道x,无法求出一个y,使x与y的HA【9】SH值相同。 这两条性【⒌】质在数学上都是不成立的。因为一个函数必然可逆,且【2】由于HASH函数的值域有限,理论上会有无穷多个不同的原始值【6】,它们的hash值都相同。MD5和SHA做到的,是求逆和求冲突在计算上不可能,也就是正向计算很容易,而反向计算即使穷尽人类所有的计算资-源都做不到。 顺便说一下,王小云教授曾经成功制造出MD5的碰撞,即md5(a) = md5(b)。这样的碰撞只能随机生成,并不能根据一个已知的a求出b(即并没有破坏MD5的无冲突特性)。但这已经让他声名大噪了。 HASH算法的另外一个很广泛的用途,就是很多程序员都会使用的在数据库中保存用户密码的算法,通常不会直接保存用户密码(这样DBA就能看到用户密码啦,好危险啊),而是保存密码的HASH值,验

证的时候,用相同的HASH函数计算用户输入的密码得到计算HASH值然后比对数据库中存储的HASH值是否一致,从而完成验证。由于用户的密码的一样的可能性是很高的,防止DBA猜测用户密码,我们还会用一种俗称“撒盐”的过程,就是计算密码的HASH值之前,把密码和另外一个会比较发散的数据拼接,通常我们会用用户创建时间的毫秒部分。这样计算的HASH值不大会都是一样的,会很发散。最后,作为一个老程序员,我会把用户的HASH值保存好,然后把我自己密码的HASH值保存到数据库里面,然后用我自己的密码和其他用户的用户名去登录,然后再改回来解决我看不到用户密码而又要“偷窥”用户的需要。最大的好处是,数据库泄露后,得到用户数据库的黑客看着一大堆HASH值会翻白眼。 哈希算法又称为摘要算法,它可以将任意数据通过一个函数转换成长度固定的数据串(通常用16进制的字符串表示),函数与数据串之间形成一一映射的关系。 举个粒子,我写了一篇小说,摘要是一个string:'关于甲状腺精灵的奇妙冒险',并附上这篇文章的摘要是'2d73d4f15c0db7f5ecb321b6a65e5d6d'。如果有人篡改了我的文章,并发表为'关于JOJO的奇妙冒险',我可以立即发现我的文章被篡改过,因为根据'关于JOJO的奇妙冒险'计算出的摘要不同于原始文章的摘要。 可见,摘要算法就是通过摘要函数f()对任意长度的数据data计算出固定长度的摘要digest,目的是为了发现原始数据是否被人篡

关于对哈希算法的研究与应用

关于对哈希算法的研究与应用 摘要:随着科学技术的不断发展,许多新的算法在各个领域中有了进一步的应用,其中技术较为先进的哈希算法,以其独特的计算方式受到了广泛的应用。本文主要从哈希算法的定义、特点、原理、应用等方面展开了深入的研究,供大家讨论研究。 关键词:哈希算法;含义;原理;方式;应用 the research and application of the hash algorithm huang yunke,xin xiaolong,li chenglong,li yumin (department of mathematics, northwest university, xi’an 710069,china) abstract: with the continuous development of science and technology, many new algorithms have further applications in various fields in which technology is more advanced hash algorithm, with its unique method of calculation has been widely used. mainly from the hash algorithm definition, characteristics, principles and applications, in-depth study for discussion study. keywords: hash algorithm; meaning; principle; way; application 一、哈希算法的含义 哈希的英文名为hash,意思为散列,它将任意长度的二进制值对

哈希算法介绍

哈希算法简介

目录 1哈希算法概念 (2) 2哈希函数 (3) 3冲突的解决方法 (3) 4哈希算法应用 (4)

关键词: 算法、哈希、c语言 摘要: 哈希算法在软件开发和Linux内核中多次被使用,由此可以见哈希算法的实用性和重要性。本文介绍了哈希算法的原理和应用,并给出了简略的代码实现,以便读者理解。

1哈希算法概念 哈希(hash 散列,音译为哈希) 算法将任意长度的二进制值映射为固定长度的较小二进制值,这个小的二进制值称为哈希值。 哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的哈希算法都将产生不同的值。要找到散列为同一个值的两个不同的输入,在计算上是不可能的,所以数据的哈希值可以检验数据的完整性。 哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映象到一个有限的地址区间上,并以关键字在地址区间中的项作为记录在表中的存储位置,这种表称为哈希表,所得存储位置称为哈希地址。作为线性数据结构与表格和队列等相比,哈希表无疑是查找速度比较快的一种。 查找一般是对项的摸个部分(及数据成员)进行,这部分称为键(key )。例如,项可以由字符串作为键,附带一些数据成员。 理想的哈希表数据结构只不过是一个包含一些项的具有固定大小的数组。 通常的习惯是让项从0到 TableSize-1之间变化。 将每个键映射到0到TableSize-1 这个范围中的某个数 ,并且将其放到适当的单元中,这个映射就称为散列函数(hash funciton )。 如右图,john 被散列到3,phil 被散列到4,dave 被散列到6,mary 被散列到7. 这是哈希的基本思想。剩下的问题则是要选择一个函数,决定当两个键散列到同一个值的时候(称为冲突),应该做什么。

哈希表查找成功和不成功的算法

哈希表查找不成功怎么计算? 解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数! 例如:散列函数为hash(x)=x MOD 13,用线性探测,建立了哈希表之后,如何求查找不成功时的平均查找长度!? 地址:0 1 2 3 4 5 6 7 8 9 10 11 12 数据: 39 1228154244 625-- 36- 38 成功次数: 1 3 1 2 2 1 191 1 不成功次数:98 7 65 4 3 2 1 1 2 110 查找成功时的平均查找长度:ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2 查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54 说明: 第n个位置不成功时的比较次数为,第n个位置到第1个没有数据位置的距离。至少要查询多少次才能确认没有这个值。 (1)查询hash(x)=0,至少要查询9次遇到表值为空的时候,才能确认查询失 败。 (2)查询hash(x)=1,至少要查询8次遇到表值为空的时候,才能确认查询失 败。 (3)查询hash(x)=2,至少要查询7次遇到表值为空的时候,才能确认查询失 败。 (4)查询hash(x)=3,至少要查询6次遇到表值为空的时候,才能确认查询失 败。 (5)查询hash(x)=4,至少要查询5次遇到表值为空的时候,才能确认查询失 败。 (6)查询hash(x)=5,至少要查询4次遇到表值为空的时候,才能确认查询失 败。

(7)查询hash(x)=6,至少要查询3次遇到表值为空的时候,才能确认查询失败。 (8)查询hash(x)=7,至少要查询2次遇到表值为空的时候,才能确认查询失败。 (9)查询hash(x)=8,至少要查询1次遇到表值为空的时候,才能确认查询失败。 (10)查询hash(x)=9,至少要查询1次遇到表值为空的时候,才能确认查询失败。 (11)查询hash(x)=10,至少要查询2次遇到表值为空的时候,才能确认查询失败。 (12)查询hash(x)=11,至少要查询1次遇到表值为空的时候,才能确认查询失败。 (13)查询hash(x)=12,至少要查询10次遇到表值为空(循环查询顺序表)的时候,才能确认查询失败。 下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。 Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为:H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。 (1) 请画出所构造的散列表。 (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 Ans: (1).首先明确一个概念装载因子,装载因子是指所有关键子填充哈希表后饱和的程度,它等于关键字总数/哈希表的长度。根据题意,我们可以确定哈希表的长度为 L = 7/0.7 = 10;因此此题需要构建的哈希表是下标为0~9的一维数组。根据散列函数可以得到如下散列函数值表。 H(Key) = (keyx3) MOD 7, 例如key=7时, H(7) = (7x3)%7 = 21%7=0,其他关键字同理。

字符串哈希算法

经典字符串Hash函数 工作中经常需要用大hash这个强有力的工具,hash表最核心的部分则在于怎么设计一个好的hash函数,以使数据更均匀地分布在若干个桶上。下面来介绍一下我现在用到的一个hash函数,我们来看代码: unsigned chostcachehash::get_host_key(const string& host) { int result = 1; unsigned i = 0; for (i = 0; i > 24); h = h ^ g; } } return h; } openssl中出现的字符串hash函数 unsigned long lh_strhash(char *str) { int i,l; unsigned long ret=0; unsigned short *s;

SHA-1(安全哈希算法实现)

SHA-1(安全哈希算法实现) 如题,不知道sha-1的自己百度吧。 1 #include 2 #include //定义vector数组 3 #include //记录消息 4usingnamespace std; 5 6constint NUM = 8; //一个字由32比特(或者8个16进制数) 7constint BIT = 512; //消息认证码要以512比特一组 8 9//字常量 10string H0 = "67452301"; 11string H1 = "EFCDAB89"; 12string H2 = "98BADCFE"; 13string H3 = "10325476"; 14string H4 = "C3D2E1F0"; 15 16//定义SHA1(安全哈希算法)类 17class SHA1 18 { 19public: 20//将一个字符串形式的字转化为vector数组 21 vector hex_into_dec(string word); 22 23//将vector转化为string字符串形式 24string num_into_message(vector A); 25 26//两个字X和Y的逻辑"和" 27 vector word_AND(vector A,vector B); 28 29//两个字X和Y的逻辑"或" 30 vector word_OR(vector A,vector B); 31 32//两个字X和Y的逻辑"异或" 33 vector word_XOR(vector A,vector B); 34 35//两个字X和Y的逻辑"补" 36 vector word_COMPLEMENT(vector A); 37 38//两个字X和Y的摸2^32整数加 39 vector word_ADD(vector A,vector B); 40

几种字符串哈希HASH算法的性能比较

几种字符串哈希HASH算法的性能比较 2011年01月26日星期三 19:40 这不就是要找hash table的hash function吗? 1 概述 链表查找的时间效率为O(N),二分法为log2N,B+ Tree为log2N,但Hash链表查找的时间效率为O(1)。 设计高效算法往往需要使用Hash链表,常数级的查找速度是任何别的算法无法比拟的,Hash 链表的构造和冲突的不同实现方法对效率当然有一定的影响,然而Hash函数是Hash链表最核心的部分,本文尝试分析一些经典软件中使用到的字符串 Hash函数在执行效率、离散性、空间利用率等方面的性能问题。 2 经典字符串Hash函数介绍 作者阅读过大量经典软件原代码,下面分别介绍几个经典软件中出现的字符串Hash函数。 2.1 PHP中出现的字符串Hash函数 static unsigned long hashpjw(char *arKey, unsigned int nKeyLength) { unsigned long h = 0, g; char *arEnd=arKey+nKeyLength; while (arKey < arEnd) { h = (h << 4) + *arKey++; if ((g = (h & 0xF0000000))) { h = h ^ (g >> 24); h = h ^ g; } } return h; } 2.2 OpenSSL中出现的字符串Hash函数 unsigned long lh_strhash(char *str) { int i,l; unsigned long ret=0; unsigned short *s; if (str == NULL) return(0); l=(strlen(str)+1)/2; s=(unsigned short *)str; for (i=0; i ret^=(s[i]<<(i&0x0f)); return(ret);

数据结构课程设计--哈希表实验报告

福建工程学院 课程设计 课程:算法与数据结构 题目:哈希表 专业:网络工程 班级:xxxxxx班 座号:xxxxxxxxxxxx 姓名:xxxxxxx 2011年12 月31 日 实验题目:哈希表 一、要解决的问题 针对同班同学信息设计一个通讯录,学生信息有姓名,学号,电话号码等。以学生姓名为关键字设计哈希表,并完成相应的建表和查表程序。 基本要求:姓名以汉语拼音形式,待填入哈希表的人名约30个,自行设计哈希函数,用线性探测再散列法或链地址法处理冲突;在查找的过程中给出比较的次数。完成按姓名查询的操作。 运行的环境:Microsoft Visual C++ 6.0 二、算法基本思想描述 设计一个哈希表(哈希表内的元素为自定义的结构体)用来存放待填入的30个人名,人名为中国姓名的汉语拼音形式,用除留余数法构造哈希函数,用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。 三、设计 1、数据结构的设计和说明 (1)结构体的定义 typedef struct //记录 { NA name; NA xuehao; NA tel; }Record;

{ Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable; 哈希表元素的定义,包含数据元素存储基址、数据元素个数、当前容量。 2、关键算法的设计 (1)姓名的折叠处理 long fold(NA s) //人名的折叠处理 { char *p; long sum=0; NA ss; strcpy(ss,s); //复制字符串,不改变原字符串的大小写 strupr(ss); //将字符串ss转换为大写形式 p=ss; while(*p!='\0') sum+=*p++; printf("\nsum====================%d",sum); return sum; } (2)建立哈希表 1、用除留余数法构建哈希函数 2、用线性探测再散列法处理冲突 int Hash1(NA str) //哈希函数 { long n; int m; n=fold(str); //先将用户名进行折叠处理 m=n%HASHSIZE; //折叠处理后的数,用除留余数法构造哈希函数 return m; //并返回模值 }Status collision(int p,int c) //冲突处理函数,采用二次探测再散列法解决冲突{ int i,q; i=c/2+1; while(i=0) return q; else i=c/2+1; } else{ q=(p-i*i)%HASHSIZE; c++;

相关文档