V ol.15, No.2
?2004 Journal of Software 软 件 学 报 1000-9825/2004/15(02)0179 两种对URL 的散列效果很好的函数
?
李晓明+, 凤旺森
(北京大学 计算机科学技术系,北京 100871)
Two Effective Functions on Hashing URL
LI Xiao-Ming +, FENG Wang-Sen
(Department of Computer Science and Technology, Peking University, Beijing 100871, China)
+ Corresponding author: Phn: +86-10-62756589, Fax: +86-10-62765813, E-mail: lxm@https://www.doczj.com/doc/af4368436.html,, https://www.doczj.com/doc/af4368436.html,
Received 2003-03-05; Accepted 2003-06-18
Li XM , Feng WS . Two effective functions on hashing URL . Journal of Software , 2004,15(2):179~184. https://www.doczj.com/doc/af4368436.html,/1000-9825/15/179.htm
Abstract : Hashing large collection of URLs is an inevitable problem in many Web research activities. Through a large scale experiment, three hash functions are compared in this paper. Two metrics were developed for the comparison, which are related to web structure analysis and Web crawling, respectively. The finding is that the well-known function for hashing sequence of symbols, ELFhash, is not very good in this regard, and the other two functions are better and thus recommended. Key words :
hashing; ELFhash; URL; even distribution; Web mining; load balance
摘 要: 在Web 信息处理的研究中,不少情况下需要对很大的URL 序列进行散列操作.针对两种典型的应用场合,即Web 结构分析中的信息查询和并行搜索引擎中的负载平衡,基于一个含有2 000多万个URL 的序列,进行了大规模的实验评测.说明在许多文献中推荐的对字符串散列效果很好的ELFhash 函数对URL 的散列效果并不好,同时推荐了两种对URL 散列效果很好的函数.
关键词: 散列;ELFhash;URL;均匀分布;Web 挖掘;负载平衡 中图法分类号: TP314 文献标识码: A
散列(hashing)是信息存储和查询所用的一项基本技术,许多教科书中都有介绍[1].这项技术虽然发明于50年前,其间也有过不少非常系统、完整的研究工作[2],但直到近几年仍然有新的工作进展[3~5].散列技术的基础性及其在许多领域的可应用性是其不断被人们研究的源泉,而对它进行的研究能不断有新意的基本原因在于,其优化性能在很大程度上取决于输入键的结构.本文研究散列的键是用于访问网页的url,即形如“https://www.doczj.com/doc/af4368436.html,/…”之类的字符串[6].
考虑如下两种应用情形:
? Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1999032706 (国家重点基础研
究发展规划(973))
作者简介: 李晓明(1957－),男,湖北荆州人,教授,博士生导师,主要研究领域为计算机系统,网络计算;凤旺森(1980－),男,硕士
生,主要研究领域为算法设计,复杂性理论.
180
Journal of Software 软件学报 2004,15(2)
(1) 假设我们已经有了全国网页的集合,记作P ={p 1,p 2,p 3,…}.对应地,所有URL 的集合,记作URL ={url 1,url 2,url 3,…}.作为研究Web 结构的一个方面,我们关心的是,给定两个网页p i 和p j ,从p i 到p j 的最少链接数是多少.为此,我们可以首先从网页中抽取出基本结构信息,将每一个网页表达为
,...},...,,:{,2,1,j i i i i i url url url url p =,
即我们将每篇网页看成是一个有向图的节点,这样表达的p i 就给出了节点的标识和它的“外向”相邻关系.注意,并不是所有的url i ,j 都属于上述URL 集合(可能有死链,还可能有我们在此不关心的链,例如指向国外的).此时,得到从p i 到p j 的最少链接数的方法之一就是从p i 开始做先宽搜索.在搜索过程中,为了不重复劳动,要记住已经查过的节点(记作集合visited-nodes);凡是遇到一个节点,就要用它和visited-nodes 中的元素对比,若在其中,则放弃,否则,将它放入visited-nodes,继续沿其含有的url 向下搜索.显然,将visited-nodes 组织成一个散列表是最自然的.散列的对象(键)是url.
(2) 在并行搜索引擎的工作过程中,若干台计算机并行地从Web 上抓取网页[7].并行系统维护一个全局的visited-pages,每台计算机维护一个局部的unvisited-pages.每当从一个刚抓来的网页中提取出一个url 时,首先和visited-pages 的元素对比(这里可能也用散列,与前述情况类似,在此不赘述),看是否存在;如果不存在,则将它散列到某台计算机上,让它来负责该url 对应网页的抓取.
我们注意到,这两种应用的要求是有区别的.前者追求的是查询效率,后者追求的是负载平衡;前者的散列槽数可能很大(对于千万量级的节点数,槽数可以大到百万量级),后者的散列槽数相比要小得多(并行系统中计算机台数).同时,前者追求的是某种“平均”效果,后者要考虑“最大值”的情况.这样的认识是后面进行实验设计和分析的基础.
首先,我们针对上述两种应用需求给出相应的散列函数质量的评估测度.随后,描述参与实验的数据源和几个散列函数;特别地,其中包括在许多文献中推荐的对字符串散列效果很好的ELFhash 函数(一种散列URL 的自然选择)和阎宏飞、谢正茂设计的用于我们的天网搜索引擎的散列函数,以及我们在“Web 信息博物馆”中使用的另一种函数.在介绍了实验设计的细节之后,我们给出执行的结果.最后是对结果的几点分析和讨论.
1 实验的设计和执行
1.1 评估测度
为了比较不同的散列函数,需要有与应用背景相关的评估测度.对于上述第1种应用,我们关心的是对散列后url 的平均查询时间.对于第2种应用,我们关心最大的槽中元素的个数.为此,有下面两种对应的测度定义.
信息查询性能测度.设有N 个url 字符串待处理,将这些字符串用散列函数F 散列到M 个槽中,对i (1≤i ≤M )号槽,散列到其中的url 个数为N i .我们假设查询每个url 的概率是相等的,则对N 个url 各作一次查询的时间算术平均值,便可当作F 的查询性能测度.按照通常散列表项的链表结构,对i 号槽中第k 个元素作查询,需要访问存储k 次,所以,对散列在i 号槽中的所有字符串都作一次查询,则需要访问存储
2
)
1(+i i N N 次.考虑所有的槽,我们可以用下面的平均存储访问次数来表示散列函数F 的查询性能测度,越小越好.
∑∑==+=+=
M i i M
i i i N N N N N
A 12
121212)1(1, 其中. ∑==M
i i N N 1根据上述条件和凹函数(x 2)的基本性质易知,当所有M
N
N i =时A 取最小值,当只有1个,其他都为0时取最大值.两个极值分别为
N N i =i N 21/+M N 和2
1
+N . 负载平衡性能测度.设有N 个url 所指网页待抓取,将这些url 字符串用散列函数F 散列到M 台机器中,对i (1≤i ≤M )号机器,散列到其中的url 字符串个数为N i ,则M 台机器并行完成N 个网页抓取的时间取决于任务最多
李晓明 等:两种对URL 的散列效果很好的函数
181
的机器的完成时间,即与max(N i )成比例.做一定的规格化,我们用)max(i N N M
B =来作为F 的负载平衡性能测
度,这个量也可以解释成抓取一个网页所要消耗的平均机器时间,越小越好.同样,我们不难看出它的极值分别
为1和M ,发生在M
N
N i =)max(和N N i =)max(.我们注意到,B 值的物理意义是散列结果和最佳期望值的倍数差距,即M N B ?
N i =)max(. 1.2 待评估的散列函数 我们考虑3个函数,第1个取自文献[8],源于UNIX System V,号称“实际生活散列函数中的典型魔术”,也是我们在信息查询研究工作中的首选,但发现不理想,从而导致了本文的研究工作.
int ELFhash(char* url, int size) {
unsigned int h =
0;
while (*url)
{
h =
(h<<4) + *url++;
unsigned int g= h & 0xF0000000; if (g)
h^=
g>>24; h&=~g; }
return h%size;
}
第2个是由阎宏飞和谢正茂采用折叠方法设计的,一直用在天网搜索引擎中,感觉负载平衡效果比较好,但没有系统评估过.
unsigned int HfIp(char* url, int size) {
unsigned int n =
0; char* b =
(char*)&n;
for (int i=0; i url[i]; return n%size; } 第3个是谢正茂为了在多个数据库中分布网页设计的,也是出于负载平衡的目的,主要的一个考虑因素是实现简单. int _hf(char* url, int size) { int result = 0; char* ptr = url; int c; for (int i=1; c=*ptr++; i++) result += c*3*i; if (result<0) result = ?result; 182 Journal of Software 软件学报 2004,15(2) return result%size; } 1.3 实验方案和数据结果 我们以天网搜索引擎搜集的2 000万个url 序列为源数据?,用上述3种散列函数分别针对两种应用的需求实验,考察在不同的N 和M 情况下测度A 和B 的情况. 对信息查询应用,我们分别取槽数M =20,80,100,200(单位:万),以50万为间隔,以N =50万,100万,…,2000万个url 为输入执行散列函数,得到测度A.共执行4次,每次执行得到3×40个数据. 对负载平衡应用,我们分别取槽数M =8,10,12,40,同样也是以50万为间隔,以N =50万,100万,…,2000万个url 为输入执行散列函数,得到测度B.也是共执行4次,每次执行得到3×40个数据. 图1和图2是这些数据的图示.如图1所示为信息查询的性能,如图2所示为负载平衡的性能,其中标有A 的图与测度A 相关,标有B 的图与测度B 相关. A(1): M =200000 A(2): M =800000 Record number (unit: 10 000) I n f o r m a t i o n r e t r i e v a l p e r f o r m a n c e n u m b e r * ELFhash ? Hflp + hf * ELFhash ? Hflp + hf Record number (unit: 10 000) I n f o r m a t i o n r e t r i e v a l p e r f o r m a n c e n u m b e r * ELFhash ? Hflp + hf A(4): M =2000000 Record number (unit: 10 000) * ELFhash ? Hflp + hf I n f o r m a t i o n r e t r i e v a l p e r f o r m a n c e n u m b e r I n f o r m a t i o n r e t r i e v a l p e r f o r m a n c e n u m b e r Record number (unit: 10 000) A(3): M =1000000 Fig.1 Performance comparison for information retrieval 图1 检索性能比较 ? 可以免费提供给有兴趣做类似研究工作的同行,燕穹产品号:YQ-URLLIST-2002-03. 李晓明 等:两种对URL 的散列效果很好的函数 183 L o a d b a l a n c e p e r f o r m a n c e n u m b e r * ELFhash ? Hflp + hf * ELFhash ? Hflp + hf B(2): M =100000 Record number (unit: 10 000) B(1): M =80000 L o a d b a l a n c e p e r f o r m a n c e n u m b e r Record number (unit: 10 000) * ELFhash ? Hflp + hf * ELFhash ? Hflp + hf L o a d b a l a n c e p e r f o r m a n c e n u m b e r B(4): M =400000 Record number (unit: 10 000) B(3): M =120000 L o a d b a l a n c e p e r f o r m a n c e n u m b e r Record number (unit: 10 000) Fig.2 Performance comparison for load balance 图2 负载平衡性能比较 2 实验的结论与分析 我们分信息查询(对应于A)和负载平衡(对应于B)两种情况加以讨论. 观察图1中A(1),A(2),…,A(4)的形态,我们有: ? HfIp 散列函数具有绝对的优势,在所有情况下都是最好的. ? hf 的性能在M 较小的情况下与HfIp 相当,比ELFhash 要好;但随着M 的增大,hf 的相对性能逐步下降,最后比ELFhash 要差. ? 特别地,我们注意到HfIp 和最优值相当接近.例如,在M =20万的情形下,我们有下面的对比(其中最优A 值可由前面的测度表达式定义计算出): N 500 000 1 000 000 1 500 000 2 000 000 2 500 000 3 000 000 … 20 000 000 A (opt) 1.75 2.75 4.25 5.5 6.75 8.00 … 50.50 HfIp 1.89 3.23 4.54 5.85 7.01 8.31 … 51.75 这些数据显示HfIp 不仅很接近最优,而且相当稳定. 184 Journal of Software 软件学报 2004,15(2) 观察图2中B(1),B(2),…,B(4)的形态,我们有: ? HfIp 散列函数在负载平衡方面表现也不错.它的B 测度基本上都在1.1以下,接近B 的最优值(即1.0,与图的横轴重合).它最大的优点是稳定,对不同的M 表现很一致. ? hf 在M =8,10,40时表现最好(比HfIp 要好),但在M =12时最差(比ELFhash 要差).这种不稳定性的原因不清楚. ? ELFhash 的表现较差,B 值在1~5之间大范围波动. 由于hf 在负载平衡实验中的异常表现,我们在2 000万个url 序列中随机选取40万个url 作为样本,单独作一个比较实验,证明hf 的不稳定性.对负载平衡应用,我们分别取槽数M =11,12,14,16,18,以1万为间隔,以N =1万,2万,…,40万个url 为输入执行散列函数hf,得到测度B.共执行5次,每次执行得到40个数据.图3是这些数据的图示,可以很清楚地看到hf 性能的波动. ? M =11* M =12+ M =14□ M =16 M =18 L o a d b a l a n c e p e r f o r m a n c e n u m b e r Record number (unit: 10 000) Fig.3 Instability of algorithm hf in load balance application 图3 hf 算法在负载平衡应用中的不稳定性 作为本项研究的结论,我们有:对于URL 的散列,(1) 无论出于信息查询还是负载平衡的需求,HfIp 都是很可靠的,可以首选使用;(2) Hf 在有些情况下对负载平衡很好,但它对槽数的敏感性是一个值得注意的缺陷,有时可能效果很不好,需要小心;(3) 不推荐使用ELFhash. 致谢 许多人在这项工作中给予了帮助:阎宏飞和谢正茂提供了他们的散列函数,孙磊收集并整理了用于实验的数据,肖明忠对论文的初稿提出了一些有益的建议,张立昂老师一直关心这项工作的进行.在此,我们对他们表示衷心的感谢. References : [1] Cormen TH, Leiserson CE. Introduction to Algorithms. 2nd ed., Cambridge: MIT Press, 2001. 221~252. [2] Knuth DE. Sorting and Searching, Volume 3 of the Art of Computer Programming. New York: Addison-Wesley, 1973. 506~549. [3] McKenzie BJ, Harries R, Bell T. Selecting a hashing algorithm. Software Practice and Experience, 1990,20(2):208~210. [4] Tong MCF. General hashing [Ph.D. Thesis]. Computer Science Department, University of Auckland, 1996. [5] Peter K. Pearson, fast hashing of variable length text strings. Communications of the ACM, 1990,33(6):676~678. [6] Berners-Lee T. Universal resource locator. 2003. https://www.doczj.com/doc/af4368436.html,/Addressing/URL/Overview.html [7] Yan HF, Wang JY, Li XM, Guo L. Architectural design and evaluation of an efficient Web-crawling system. Journal of System and Software, 2002,60(3):185~193. [8] Shaffer CA. Zhang M, Liu XD, Trans. Data Structure and Algorithm Analysis. Beijing: Publishing House of Electronics Industry, 1998. 211~213 (in Chinese). 附中文参考文献: [8] Shaffer CA,著.张铭,刘晓丹,译.数据结构与算法分析.北京:电子工业出版社,1998.211~213. 课程实验报告 课程名称：数据结构 实验项目名称：散列表 专业班级： 姓名：XXX 学号： 完成时间：2015 年06 月13 日 背景 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。在理想情况下，查找、插入、删除操作的时间均为O(1)，是一种高效的动态集合结构。 例1：计算机程序设计语言的编译程序需要维护一个符号表，其中元素的关键值为任意字符串，与语言中的标识符对应。该符号表常采用散列表。 例2：为了节约空间，常常需要把文本文件采用压缩编码方式存储。LZW是对文本文件进行压缩和解压缩的方法之一，该方法采用了散列。 问题描述 我们希望在浩瀚的图书中，去发现一本书是否存在。我们不知道书的编号，只知道它的书名。（其实这已经不错了...）。通过书名，来查询它是否存在。 为了简化问题，我们假设每本书的书名都是一组小写字母组成，长度不超过100字符。 基本要求 （1）根据输入建立图书名称表，采用散列表实现该表，散列函数选用BKDE 字符串哈希。 （2）数据的输入输出格式： 输入分为两部分 第一部分，第一行是行数n，n <= 5000。余下n行，每行一个字符串。表示已存 在的图书记录。 第二部分，第一行是行数m，m <= 1000。余下m行，每行一个字符串。表示要查 询的图书记录。 输出： 输出为m行，如果被查的记录存在，则输出"YES",如果不存在则输出"NO"。 测试数据 输入： 4 a ans and hellocpp 实验报告 姓名：学号： 1．实验题目 针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。 基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 2．需求分析 本演示程序用VC编写，完成哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 输出形式：地址，关键字，收索长度，H（key），拼音 3.概要设计 typedef struct NAME typedef struct hterm void InitNameList() void CreateHashList() void FindList() void Display() int main() 4．详细设计 #include #define HASH_LEN 50 #define M 47 #define NAME_NO 8 typedef struct NAME { char *py; //名字的拼音 int k; //拼音所对应的整数}NAME; NAME NameList[HASH_LEN]; typedef struct hterm //哈希表{ char *py; //名字的拼音 int k; //拼音所对应的整数int si; //查找长度 }HASH; HASH HashList[HASH_LEN]; void InitNameList() { NameList[0].py="houxinming"; NameList[1].py="abc"; NameList[2].py="defdgf"; NameList[3].py="zhangrji"; NameList[4].py="jiaxin"; NameList[5].py="xiaokai"; NameList[6].py="liupeng"; NameList[7].py="shenyonghai"; 什么是哈希函数 哈希（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卡中的微处理器对摘要进行加密就变得很容易，数字签名的过程一般在一秒钟内即可完成。 计算机算法领域 基本知识 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)称二次探测再散列; 福建工程学院 课程设计 课程：算法与数据结构 题目：哈希表 专业：网络工程 班级：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 单向散列函数算法（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])<< 最小完美哈希函数 哈希函数h是一个能够将n个键值x j的集合映射到一个整数集合的函数h(x i)，其值域范围是0≤h(x j)≤m-l，允许重复。哈希是一个具有查找表功能并且提供平均情况下快速访问的标准方法。例如，当数 据包含n个整数键值。某常用哈希函数采用h(x)=x mod m，其中m 是一个较小的值，且满足m>n/a。a是装载因子，表示记录数和可用地址数的比例关系。m一般选择一个素数，因此如果要求提供一个对1000个整数键值进行哈希的函数，一个程序员可能会建议写出如下函数形式：，h(x)=x mod 1399。并且提供一个装载因子为。a=0.7的表，该表声明能够存放1399个地址。 a越小，两个不同键值在相同哈希值相互冲突的可能性就越小，然而冲突总是不可避免。第1次考虑这个问题时，事实可能让人吃惊，最好的例子莫过于著名的生日悖论(birthday paradox)。假定一年有365天，那么要组合多少个人，才能使得出现生日相同的人这一概率超过0.5呢？换句话说，给定一个365个哈希槽(hashslot)。随机选择多少个键值才能够使得出现冲突的概率超过0.5?当首次面对这样一个问题时，一般的反应肯定是认为需要很多人才行。事实上，答案是只需区区23人。找到一个能够满足现实大小要求且无冲突的哈希函数的几率小到几乎可以忽略25。例如，一个1000个键值和1399个随机选择的槽，完全没有冲突的概率为 2.35×10-217（概率的计算诱导公式将在下一节中给出，以公式4.1代入m=1399和n=1000得到），如何才能最好地处理这些不可避免冲突？这一话题将在本节中以大段篇幅展开，这里我们正是要找到其中万里挑一的能够避免所有冲突的哈 希函数。 25可以试图在一群人中做这样一个有趣的实验，笔者曾在讲述哈希表的课上和同学们做 过多次这样的实验。有一项很重要的事情往往被我们忽略，即参加者必须事先在纸上写下他们的生日（或者其他任意日子）。然后才能开始核对的工作，这样才能消除神奇的负反馈。在我们的实验中，除非这样做了，否则也许必须找到366个同学才能遇到第1次碰撞，也许这乜存在心理学悖论吧。 题5.1 a.分离链接法：将散列到同一个值的所有元素保留到一个链表中。 1)首先插入4371，h(4371)=4371(mod 10)=1，故插入1位置。 2)插入1323，h(1323)=1323(mod 10)=3，故插入3位置。 3)插入6173，h(6173)=6173(mod 10)=3，故插入3位置，此时发生冲突（与1323 插入同一位置），故添加一个链表并保存到此链表中。 4)插入4199，h(4199)=4199(mod 10)=9，故插入9位置。 5)插入4344，h(4344)=4344(mod 10)=4，故插入4位置。 6)插入9679，h(9679)=9679(mod 10)=9，故插入9位置，此时发生冲突（与4199 插入同一位置），故添加一个链表并保存到此链表中。 7)插入1989，h(1989)=1989(mod 10)=9，故插入9位置，此时发生冲突（与4199， 9679插入同一位置），故添加一个链表并保存到此链表中。 b.线性探测：hi(x)=(hash(x)+f(i))mod TableSize，其中f(i)=i，i为发 生冲突的次数，f(0)=0。相当于逐个探测散列表，最后将值散列 到最接近的一个空单元中（可以理解为，若发生冲突，则插入到下一个空单元中）。 1)首先插入4371，h0(4371)=(4371(mod 10)+f(0))mod 10=1，故插入1位置。 2)插入1323，h0(1323)=(1323(mod 10)+f(0))mod 10=3，故插入3位置。 3)插入6173，h0(6173)=(6173(mod 10)+f(0))mod 10=3，故插入3位置，此时发 生冲突（与1323插入同一位置）。 发生第一次冲突，计算h1(6173)=(6173(mod 10)+f(1))mod 10=4，故插入4位置。 4)插入4199，h0(4199)=(4199(mod 10)+f(0))mod 10=9，故插入9位置。 5)插入4344，h0(4344)=(4344(mod 10)+f(0))mod 10=4，故插入4位置，此时发 生冲突（与6173。插入同一位置）。 发生第一次冲突计算h1(4344)=(4344(mod 10)+f(1))mod 10=5，故插入5位置。 6)插入9679，h0(9679)=(9679(mod 10)+f(0))mod 10=9，故插入9位置，此时发 生冲突（与4199插入同一位置）。 发生第一次冲突计算h1(9679)=(9679(mod 10)+f(1))mod 10=0，故插入0位置。 7)插入1989，h0(1989)=(1989(mod 10)+f(0))mod 10=9，故插入9位置，此时发 南昌航空大学实验报告 课程名称：数据结构实验名称：实验九查找 班级：学生姓名：学号： 指导教师评定：签名: 题目：编程实现哈希表的造表和查找算法。 要求：用除留余数法构造哈希函数，用二次探测再散列解决冲突。 一、需求分析 1.用户可以根据自己的需求输入一个顺序表（哈希表） 2.通过用除留余数法构造哈希函数，并用开放地址的二次探测再散列解决冲突。 3.在经过排序后显示该哈希表。 4.程序执行的命令包括： （1）创建哈希表（2）输出哈希表（3）二次探测再散列解决冲突 二、概要设计 ⒈为实现上述算法，需要顺序表的抽象数据类型： ADT Hash { 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P: Creathash(&h) 操作结果：构造一个具有n个数据元素的哈希查找表h。 destroyhash(&h) 初始条件：哈希查找表h存在。 操作结果：销毁哈希查找表h。 displayhash（h） 初始条件：哈希查找表h存在。 操作结果：显示哈希查找表h。 hash(h，&k) 初始条件：哈希查找表h存在。 操作结果：通过除留余数法得到地址用k返回。 hash2 (i，&k) 初始条件：哈希查找表h存在存在，i是除留余数法得到的地址。 操作结果：返回二次探测再散列解决冲突得到的地址k。 search (h，key) 初始条件：哈希查找表h存在。 操作结果：查找表h中的key，若查找成功，返回其地址，否则返回 -1 insert (&h，key) 初始条件：哈希查找表h存在。 操作结果：若表h中没有key，则在h中插入key。 search1(h, key,&p) 初始条件：哈希查找表h存在。 操作结果：在表h中查找key，若没有，则返回p的插入的地址，否 则返回-1。 }ADT Hash 2. 本程序有三个模块： ⑴主程序模块 main(){ 初始化； { 接受命令； 显示结果； ｝ ｝ ⑵创建hash表的模块：主要建立一个哈希表； ⑶解决冲突模块：利用开放地址的二次探测再散列解决冲突； (4)输出哈希表模块：显示已创建哈希表。 三、详细设计 ⒈元素类型，结点类型 typedef struct { int key; }keytype; typedef struct { keytype elem[100]; int length; /*当前的长度*/ int size; /*哈希表的总长*/ }hashtable; /*全局变量*/ int a=0,b=0; /*哈希函数*/ 2.对抽象数据类型中的部分基本操作的伪码算法如下： /*哈希函数*/ int hash(hashtable *h,int k) { return k%h->size; } SHA-1（安全哈希算法实现） 如题，不知道sha-1的自己百度吧。 1 #include 实验课程名称：电子商务安全管理实验项目名称1:DES 、RSA 和Hash 算法的实现实验成绩 试验者 王秀梅专业班级1105441 组别同组者无实验的目的 (1) 掌握常用加密处理软件的使用方法。 (2) 理解DES 、RSA 和Hash 算法的原理。 (3) 了解MD5算法的破解方法。实验环境 (1) 装有Windows XP/2003操作系统的PC 机1台。 (2) MixedCS 、RSATool 、DAMN_HashCalc 、MD5Crack 工具软件各1套。实验步骤1、请参考实验指导PPT 。并在最后写实验心得体会。2、将实验电子版提交FTP——1105441电子商务安全管理——第一次实验报告，文件名为“学号（1105441）+姓名+实验一”。 实验过程记录 (1) 对称加密算法DES 的实现 步骤1：双击运行MixedCS.exe 程序，打开的程序主界面步骤2：单击“浏览文件”按钮，选择要进行DES 加密的源文件，选择完成后在“输出文件”文本框中会自动出现默认的加密后的文件名。步骤3：选中“DES 加密”单选按钮，在“DES 密钥”文本框中输入5个字符 (区分大小、管路敷设技术通过管线敷设技术，不仅可以解决吊顶层配置不规范问题，而且可保障各类管路习题到位。在管路敷设过程中，要加强看护关于管路高中资料试卷连接管口处理高中资料试卷弯扁度固定盒位置保护层防腐跨接地线弯曲半径标高等，要求技术交底。管线敷设技术中包含线槽、管架等多项方式，为解决高中语文电气课件中管壁薄、接口不严等问题，合理利用管线敷设技术。线缆敷设原则：在分线盒处，当不同电压回路交叉时，应采用金属隔板进行隔开处理；同一线槽内，强电回路须同时切断习题电源，线缆敷设完毕，要进行检查和检测处理。、电气课件中调试对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行高中资料试卷调整试验；通电检查所有设备高中资料试卷相互作用与相互关系，根据生产工艺高中资料试卷要求，对电气设备进行空载与带负荷下高中资料试卷调控试验；对设备进行调整使其在正常工况下与过度工作下都可以正常工作；对于继电保护进行整核对定值，审核与校对图纸，编写复杂设备与装置高中资料试卷调试方案，编写重要设备高中资料试卷试验方案以及系统启动方案；对整套启动过程中高中资料试卷电气设备进行调试工作并且进行过关运行高中资料试卷技术指导。对于调试过程中高中资料试卷技术问题，作为调试人员，需要在事前掌握图纸资料、设备制造厂家出具高中资料试卷试验报告与相关技术资料，并且了解现场设备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况，然后根据规范与规程规定，制定设备调试高中资料试卷方案。 、电气设备调试高中资料试卷技术电力保护装置调试技术，电力保护高中资料试卷配置技术是指机组在进行继电保护高中资料试卷总体配置时，需要在最大限度内来确保机组高中资料试卷安全，并且尽可能地缩小故障高中资料试卷破坏范围，或者对某些异常高中资料试卷工况进行自动处理，尤其要避免错误高中资料试卷保护装置动作，并且拒绝动作，来避免不必要高中资料试卷突然停机。因此，电力高中资料试卷保护装置调试技术，要求电力保护装置做到准确灵活。对于差动保护装置高中资料试卷调试技术是指发电机一变压器组在发生内部故障时，需要进行外部电源高中资料试卷切除从而采用高中资料试卷主要保护装置。 密码学 （第十三讲） HASH函数 张焕国 武汉大学计算机学院 目录 密码学的基本概念 1、密码学 2、古典 、古典密码 3、数据加密标准（ ） DES） 、数据加密标准（DES 4、高级 ） AES） 数据加密标准（AES 高级数据加密标准（ 5、中国商用密码（ ） SMS4） 、中国商用密码（SMS4 6、分组密码的应用技术 7、序列密码 8、习题课：复习对称密码 、公开密钥密码（11） 9、公开密钥密码（ 目录 公开密钥密码（22） 10 10、 11、数字签名（1） 12、数字签名（2） 13、 、HASH函数 13 14 14、 15、 15 PKI技术 16 16、 、PKI 17、习题课：复习公钥密码 18、总复习 一、HASH 函数函数的概念的概念 1、Hash Hash的作用的作用 ?Hash Hash码也称报文摘要码也称报文摘要。。 ?它具有极强的错误检测能力错误检测能力。。 ?用Hash Hash码作码作MAC ，可用于认证认证。。 ?用Hash Hash码辅助码辅助数字签名数字签名。。 ?Hash Hash函数可用于函数可用于保密保密。。 一、HASH 函数的概念 2、Hash Hash函数的定义函数的定义 ①Hash Hash函数将任意长的数据函数将任意长的数据M 变换为定长的码h ， 记为记为：：h=HASH(M)h=HASH(M)或或h=H(M)h=H(M)。。 ②实用性：对于给定的数据对于给定的数据M M ，计算，计算h=HASH(M)h=HASH(M)是是 高效的。 ③安全性安全性：： ? 单向性：对给定的对给定的Hash Hash值值h ，找到满足H(x)H(x)＝＝h 的x 在 计算上是不可行的计算上是不可行的。。 否则否则，，设传送数据为设传送数据为C=C=＜＜M ，H(M||K )＞,K 是密钥。攻击者可以截获攻击者可以截获C,C,求出求出Hash 函数的逆函数的逆，，从而得出 M||S ＝H -1(C)，然后从M 和M ||Ｋ即可即可得出得出Ｋ。 数据结构实验报告四一一哈希表查找名字(字符串) 实验题目：哈希表查找名字(字符串) 实验目标： 输入一组名字(至少50个)，将其保存并利用哈希表查找。输出哈希查找冲突次数，哈希表负载因子、查找命中率。 数据结构： 哈希表和数组(二维)。二维数组用于静态顺序存储名字(字符串)，哈希表采用开放定址法， 用于存储名字(字符串)对应的关键字并实现对名字(字符串)的查找。 需要的操作有： 1.关键字求取(主函数中两次出现，未单独编为函数) 关键字key=abs (字符串首位ASCII码值-第二位ASCII码值+第([n]+i )位ASCII码值撮后一 位ASCII码值-倒数第二位ASCII码值)*字符串长度(abs为求整数绝对值的函数)。 2.处理关键字的哈希函数(Hash) 利用平方取中法求关键值key在哈希表中的位置。公式add=(key*key)%1000/LENGTH(add 为key在哈希表中的地址)。 int Hash(i nt key) { return((key*key)/1000%LENGTH); } 3.处理哈希表中冲突的函数(Collision 利用线性探测再散列处理冲突，利用全局变量count统计冲突次数。 int Collision(int key,int Hashtable[]) { int i; for(i=1;i<=LENGTH;i++) { if(Hashtable[(Hash(key)+i)%LENGTH]==-1) return((Hash(key)+i)%LENGTH); coun t++; } } 4.哈希表初始化(InitHash) void InitHash(int Hashtable[]) { int i; for(i=0;i 安全哈希函数 一、哈希函数定义 Hash，一般翻译做“散列”，也有直接音译为”哈希”的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 二、性质 基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。但反过来不同的原始输入不一定能得到相同的散列值，即发生了碰撞。哈希函数的定义域无限，而值域有限，因此理论上来讲每个哈希函数都可以找到碰撞。 一个“优良”的hash函数f 应当满足以下三个条件： 任意y，找x，使得f(x)=y，非常困难。此为哈希函数的单向性，或抗原像性（preimage resistant）。 给定x1，找x2，使得f(x1)=f(x2)，非常困难。弱抗碰撞性，或抗第二原像性（second preimage resistant）。 找x1，x2，使得f(x1)=f(x2)，非常困难。强抗碰撞性（Collision Resistant）。 三、分类 哈希函数有字符串哈希函数，一般用于数据存储；安全哈希函数 安全哈希函数的分类： 根据安全水平： 弱抗碰撞哈希函数和强抗碰撞哈希函数，后者是包含前者的。 在保护口令的应用中，只需弱抗碰撞性就够了，但在数字签名中，必须有强抗碰撞性。 根据是否使用密钥： 带密钥的哈希函数：消息的散列值由只有通信双方知道的秘密密钥K来控制，此时散列值称作MAC(Message Authentication Code) 不带密钥的哈希函数：消息的散列值的产生无需使用密钥，此时散列值称作MDC(Message Detection Code 四、哈希函数的用途 数字签名 哈希函数可以提高签名的速度，减少运算，又可以不泄露签名所对应的消息，还可以将消息的签名与加密变换分开处理。 校验 可以校验数据是否被篡改。传输消息之前对消息进行哈希变换，接收者也进行相同的哈希变换，若两个哈希值相同，可以认为消息在传输过程中没有被篡改。 快速访问 散列表的寻址时间复杂度为O(1)，在数据存储中运用较多，这里不作详述。 安全访问认证 MD5广泛用于操作系统的登陆认证上，如在Unix系统中用户的密码是以MD5（或其它类似的算法）经Hash运算后存储在文件系统中。当用户登录的时候，系统把用户输入的密码进行MD5 Hash运算，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这可以避免用户的密码被具有系统管理员权限的用户知道。 伪随机数生成 哈尔滨工程大学 实验报告 实验名称：Hash 算法MD5 班级： 学号： 姓名： 实验时间：2014年6月 成绩： 指导教师： 实验室名称： 哈尔滨工程大学实验室与资产管理处制 一、实验名称 Hash算法ＭＤ５ 二、实验目的 通过实际编程了解MD5 算法的加密和解密过程，加深对Hash 算法的认识。 三、实验环境（实验所使用的器件、仪器设备名称及规格） 运行Windows 或Linux 操作系统的PC 机，具有gcc(Linux)、VC（Windows）等C 语言编译环境。 四、任务及其要求 （1）利用自己所编的MD5 程序对一个文件进行处理，计算它的Hash 值，提交程 序代程和运算结果。 （2）微软的系统软件都有MD5 验证，尝试查找软件的MD5 值。同时，在Windows 操作系统中，通过开始→运行→sigverif 命令，利用数字签名查找验证非Windows 的系 统软件。__ 五、实验设计（包括原理图、真值表、分析及简化过程、卡诺图、源代码等） 在MD5 算法中，首先需要对信息进行填充，使其字节长度与448 模512 同余，即信息的字节长度扩展至n*512+448，n 为一个正整数。填充的方法如下：在信息的后面填充第一位为1，其余各位均为0，直到满足上面的条件时才停止用0 对信息填充。然后，再在这个结果后面附加一个以64 位二进制表示的填充前信息长度。经过这两步的处理，现在的信息字节长度为n*512+448= (n+1)*512，即长度恰好是512 的整数倍，这样做的目的是为满足后面处理中后面处理中对信息长度的要求。n 个分组中第q 个分组表示为Yq。MD5 中有A、B、C、D，4 个32 位被称作链接变量的整数参数，它们的初始值分别为： A=01234567B=89abcdef,C=fedcba98，D= 当设置好这个4 个链接变量后，就开始进入算法的4 轮循环运算。循环的次数是信息中512 位信息分组数目。首先将上面4 个链接变量复制到另外4 个变量中A 1.消息认证是为了对付哪些类型的攻击？ 答：伪装（假冒）篡改内容修改顺序修改时间（包括重放） 2.消息认证或数字签名方法有哪两层功能？ 答：任何消息认证或数字签名机制基本分两步： 产生认证符(是一个用来认证消息的值)的函数; 将该函数作为原语使接收方可以验证消息真实性的认证协议。 3.产生消息认证有哪些方法？ 答：用于消息认证的最常见的密码技术是消息认证码和安全散列函数 MAC是一种需要使用秘密钥的算法，以可变长度的消息和秘密钥作为输入，产生一个认证码。拥有秘密钥的接受方产生一个认证码来验证消息的完整性。 哈西函数将可变长度的消息映射为固定长度的哈西值，或叫消息摘要。对于消息认证来说，安全散列函数还必须以某种方式和秘密钥捆绑起来。 4.对称加密和错误控制码一起用于消息认证时，这两个函数必须以何种顺序执行？ 答：先错误控制码后对称加密。 5.什么是消息认证码？ 答：消息认证码，是用来保证数据完整性的一种工具，可以防止数据未经授权被篡改，用数学语言描述，是一个让双方共享的密钥k和消 (m),这个函数值就是一个息m作为输入函数，如果将函数记为mac k 认证标记。 6.消息认证码和散列函数之间的区别是什么？ 答：消息认证码（MAC）依赖公开函数，密钥控制下对消息处理，生成定长认证标识，并加以认证。 散列函数：将任意长度的消息换为定长的消息摘要，并加以认证。 7.为提供消息认证，应以何种方式保证散列值的安全？ 答：a.用对称密码对消息及附加在其后的散列码加密。 b.用对称密码仅对散列加密。 c.用公钥密码和发送方的密钥仅对散列加密。 d.若寄希望保证保密性有希望有数字签名，则先用发送方的密钥对散列码加密 e.该方法使用散列函数但不使用加密函数来进行消息认证。 f.如果对整个消息和散列码加密，则(e)中的方法可提供保密性。 8.为了攻击MAC算法必须要恢复密钥吗？ 答：不需要。 散列函数 又称hash函数，Hash函数(也称杂凑函数或杂凑算法)就是把任意长的输入消息串变化成固定长的输出串的一种函数。这个输出串称为该消息的杂凑值。一般用于产生消息摘要，密钥加密等. 一个安全的杂凑函数应该至少满足以下几个条件: ①输入长度是任意的; ②输出长度是固定的,根据目前的计算技术应至少取128bits长,以便抵抗生日攻击; ③对每一个给定的输入,计算输出即杂凑值是很容易的 ④给定杂凑函数的描述,找到两个不同的输入消息杂凑到同一个值是计算上不可行的,或给定杂凑函数的描述和一个随机选择的消息,找到另一个与该消息不同的消息使得它们杂凑到同一个值是计算上不可行的。 Hash函数主要用于完整性校验和提高数字签名的有效性,目前已有很多方案。这些算法都是伪随机函数,任何杂凑值都是等可能的。输出并不以可辨别的方式依赖于输入;在任何输入串中单个比特的变化,将会导致输出比特串中大约一半的比特发生变化。 常见散列函数(Hash函数) ·MD5（Message Digest Algorithm 5）：是RSA数据安全公司开发的一种单向散列算法，MD5被广泛使用，可以用来把不同长度的数据块进行暗码运算成一个12 8位的数值； ·SHA（Secure Hash Algorithm）这是一种较新的散列算法，可以对任意长度的数据运算生成一个160位的数值； ·MAC（Message Authentication Code）：消息认证代码，是一种使用密钥的单向函数，可以用它们在系统上或用户之间认证文件或消息。HMAC（用于消息认证的密钥散列法）就是这种函数的一个例子。 ·CRC（Cyclic Redundancy Check）：循环冗余校验码，CRC校验由于实现简单，检错能力强，被广泛使用在各种数据校验应用中。占用系统资源少，用软硬件均能实现，是进行数据传输差错检测地一种很好的手段（CRC 并不是严格意义上的散列算法，但它的作用与散列算法大致相同，所以归于此类）。 讨论几种散列函数。在以下的讨论中，我们假设处理的是值为整型的关键码，否则我们总可以建立一种关键码与正整数之间的一一对应关系，从而把该关键码的检索转化为对与其对应的正整数的检索；同时，进一步假定散列函数的值落在0到M－1之间。散列函数的选取原则是：运算尽可能简单；函数的值域必须在散列表的范围内；尽可能使得结点均匀分布，也就是尽量让不同的关键码具有不同的散列函数值。需要考虑各种因素：关键码长度、散列表大小、关键码分布情况、记录的检索频率等等。下面我们介绍几种常用的散列函数。 1、除余法 福建工程学院课程设计 课程：算法与数据结构 题目：哈希表 专业：网络工程 班级：xxxxxx班 座号：xxxxxxxxxxxx 姓名：xxxxxxx 2011年12 月31 日 实验题目：哈希表 一、要解决的问题 针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。 基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。 运行的环境：Microsoft Visual C++ 6.0 二、算法基本思想描述 设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。 三、设计 1、数据结构的设计和说明 （1）结构体的定义 typedef struct //记录 { NA name; NA xuehao; NA tel; }Record; 录入信息结构体的定义，包含姓名，学号，电话号码。 typedef struct //哈希表 { Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable; 哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。 2、关键算法的设计 （1）姓名的折叠处理数据结构实验 散列表实验报告
哈希表实验报告完整版
什么是哈希函数
哈希算法散列
数据结构课程设计--哈希表实验报告
单向散列函数算法Hash算法
最小完美哈希函数(深入搜索引擎)
习题题5-1Hash函数答案说明
哈希查找_数据结构实验报告
SHA-1(安全哈希算法实现)
【免费下载】hash算法实验
HASH函数
哈希表实验报告(20200623044247)
安全哈希函数简介
Hash算法MD5 实验报告
密码学作业ch11
散列函数
数据结构课程设计--哈希表实验报告
相关主题
文本预览