2022年2022年哈希算法散列 .pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《2022年2022年哈希算法散列 .pdf》由会员分享,可在线阅读,更多相关《2022年2022年哈希算法散列 .pdf(4页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、计算机算法领域基本知识Hash,一般翻译做 “ 散列 ” ,也有直接音译为” 哈希 “ 的,就是把任意长度的输入(又叫做预映射,pre-image) ,通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是, 散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出, 而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要 的函数。HASH 主要用于信息安全领域中加密算法,他把一些不同长度的信息转化成杂乱的128位的编码里 ,叫做 HASH 值 . 也可以说, hash 就是找到一种数据内容和数据存放地址之间的映
2、射关系基本概念* 若结构中存在关键字和K 相等的记录,则必定在f(K) 的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f 为散列函数 (Hash function) ,按这个思想建立的表为 散列表 。* 对不同的关键字可能得到同一散列地址,即key1key2 ,而 f(key1)=f(key2) ,这种现象称冲突。 具有相同函数值的关键字对该散列函数来说称做同义词。综上所述, 根据散列函数 H(key) 和处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“ 象 ” 作为记录在表中的存储位置,这种表便称为散列表,这一映象过程称为散列造表或
3、散列,所得的存储位置称散列地址。* 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的, 则称此类散列函数为均匀散列函数(Uniform Hash function) ,这就是使关键字经过散列函数得到一个“ 随机的地址 ” ,从而减少冲突。常用的构造散列函数的方法散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数, 数据元素将被更快地定位1. 直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b ,其中 a 和 b 为常数(这种散列函数叫做自身函数)2. 数字分析法3. 平方取中法4
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=12, (-1)2, 22,(- 2)2,
5、 (3)2, , (k)2,(k=m/2)称二次探测再散列; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 4 页 - - - - - - - - - 3. di=伪随机数序列,称伪随机探测再散列。= 2. 再散列法: Hi=RHi(key), i=1,2,k RHi均是不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“ 聚集 ” ,但增加了计算时间。3. 链地址法 (拉链法 ) 4. 建立一个公共溢出区查找的性能分析散
6、列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到,另一些关键码在散列函数得到的地址上产生了冲突,需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中,产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以,对散列表查找效率的量度,依然用平均查找长度来衡量。查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:1. 散列函数是否均匀;2. 处理冲突的方法;3. 散列表的装填因子。散列表的装填因子定义为:= 填入表中的元
7、素个数/ 散列表的长度 是散列表装满程度的标志因子。由于表长是定值,与“ 填入表中的元素个数” 成正比,所以, 越大,填入表中的元素较多,产生冲突的可能性就越大;越小,填入表中的元素较少,产生冲突的可能性就越小。实际上, 散列表的平均查找长度是装填因子的函数, 只是不同处理冲突的方法有不同的函数。了解了 hash 基本定义,就不能不提到一些著名的hash 算法, MD5和 SHA-1 可以说是目前应用最广泛的Hash 算法,而它们都是以MD4为基础设计的。那么他们都是什么意思呢 ? 这里简单说一下:(1) MD4MD4(RFC 1320)是MIT 的Ronald L. Rivest 在 199
8、0 年设计的,MD 是Message Digest 的缩写。 它适用在 32位字长的处理器上用高速软件实现-它是基于32 位操作数的位操作来实现的。(2) MD5 MD5(RFC 1321)是 Rivest 于1991年对 MD4 的改进版本。它对输入仍以512位分组,其输出是 4个32位字的级联,与MD4 相同。 MD5 比 MD4 来得复杂,并且速度较之要慢一点,但更安全,在抗分析和抗差分方面表现更好(3) SHA-1 及其他SHA1是由 NIST NSA设计为同 DSA 一起使用的,它对长度小于264的输入,产生长度为160bit 的散列值,因此抗穷举(brute-force) 性更好。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年2022年哈希算法散列 2022 年哈希 算法
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内