散列算法口诀表

❶ 单向散列算法的常见算法

常见散列函数(Hash函数)有： MD5（Message Digest Algorithm 5）：是RSA数据安全公司开发的一种单向散列算法，MD5被广泛使用，可以用来把不同长度的数据块进行暗码运算成一个128位的数值。 SHA（Secure Hash Algorithm）这是一种较新的散列算法，可以对任意长度的数据运算生成一个160位的数值。 MAC（Message Authentication Code）：消息认证代码，是一种使用密钥的单向函数，可以用它们在系统上或用户之间认证文件或消息，常见的是HMAC（用于消息认证的密钥散列算法）。 CRC（Cyclic Rendancy Check）：循环冗余校验码，CRC校验由于实现简单，检错能力强，被广泛使用在各种数据校验应用中。占用系统资源少，用软硬件均能实现，是进行数据传输差错检测地一种很好的手段（CRC 并不是严格意义上的散列算法，但它的作用与散列算法大致相同，所以归于此类）。

❷ 什么是哈希算法，公式是什么

哈希是 hash的音译,就是 散列, 散列算法是把一系列的值转换为地址(位置,数字)的一类算法, 没有公式. 实际上这不是一种而是一类算法, 好的散列算法和不好的散列算法差别很大. 散列一般是难以反向运算的.原因是输入和输出理论上是多对一的操作. (把无限的问题空间映射到有限的地址位置,肯定必须多对一)

加密本质上是换了一种编码方式,使得不可阅读. 实际上把英文翻译成中文,对一个不懂中文的老外来说,这也是一种不严密的加密. 加密和散列不同,加密是存在一个解密的算法的,所以加密运算一般是可逆的, 一般是一对一的.

❸ 什么是散列法

散列法是把字符串映射到整数的处理，
通常是到一个相对小的范围。一个
“散列函数”
映射一个字符串
(或其它的数据结构)
到一个有界的数字
(散列存贮桶)，这个数字可以更容易的用于数组的索引或者进行反复的比较。明显的，
一个从潜在的有很多组的字符串到小范围整数的映射不是唯一的。任何使用散列的算法都要处理
“冲突”
的可能。有许多散列函数和相关的算法被开发了出来;
一个全面的说明已经超出了本文的范围。

❹ 数据结构与算法之美笔记——散列表（上）

摘要:

我们已经知道随机访问数组元素时间复杂度只有 ，效率极高，当我们想利用数组的这个特性时就需要将元素下标与存储信息对应。例如，一个商店只有四件商品，依次编号 0 至 3，这样就可以将四件商品信息按照编号对应下标的方式存储到数组中，依据编号就可以快速从数组中找到相应商品信息。

如果一段时间之后，商店盈利并且重新进货 100 件商品，商家想对大量商品在编号上区分类别，这时候需要使用类别编号加顺序编号的方式标识每件商品，这种编号变得复杂，并不能直接对应数组下标，此时的商品编号又该如何对应数组下标以实现快速查找商品的功能？这时候我们可以将类别编号去除之后按照顺序编号对应数组下标，同样也能享受数组高效率随机访问的福利。这个例子中，商品编号称为“ 键 ”或“ 关键字 ”，将键转化为数组对应下标的方法就是“ 散列函数 ”或“ Hash 函数 ”，由散列函数生成的值叫做“ 散列值 ”或“ Hash 值 ”，而这样的数组就是散列表。

从散列表的原理来看，数据通过散列函数计算得到散列值是关键，这个步骤中散列函数又是其中的核心，一个散列函数需要遵守以下三个原则。

因为散列函数生成的散列值对应数组下标，而数组下标就是非负整数，所以需要满足第一个原则；两个相等的数据经过散列算法得到的散列值肯定相等，否则利用散列值在散列表中查找数据就无从谈起；至于第三个原则虽然在情理之中，却不那么容易做到，即使是被广泛运用的散列算法也会出现散列值冲突的情况，导致无法满足第三个原则。

散列函数作为散列表的核心部分，必然不能拖散列表的执行效率后腿，毕竟散列表的查询、插入和删除操作都需要经过散列函数，所以散列函数不能太复杂，执行效率不能太低。由于散列函数不可避免地都会出现散列冲突情况，散列函数要尽量降低散列冲突，使散列值能够均匀地分布在散列表中。

解决散列冲突主要有“ 开放寻址 ”（open addressing）和“ 链表法 ”（chaining）两类方法。

开放寻址法是指插入操作时，当生成的散列值对应槽位已经被其他数据占用，就探测空闲位置供插入使用，其中探测方法又分为“ 线性探测 ”（Linear Probing）、“ 二次探测 ”（Quadratic Probing）和“ 双重散列 ”（Double hashing）三种。

线性探测是其中较为简单的一种，这种探测方式是当遇到散列冲突的情况就顺序查找（查找到数组尾部时转向数组头部继续查找），直到查找到空槽将数据插入。当进行查找操作时，也是同样的操作，利用散列值从散列表中取出对应元素，与目标数据比对，如果不相等就继续顺序查找，直到查找到对应元素或遇到空槽为止，最坏情况下查找操作的时间复杂度可能会下降为 。

散列表除了支持插入和查找操作外，当然也支持删除操作，不过并不能将需删除的元素置为空。如果删除操作是将元素置为空的话，查找操作遇到空槽就会结束，存储在被删除元素之后的数据就可能无法正确查找到，这时的删除操作应该使用标记的方式，而不是使用将元素置空，当查找到被标识已删除的元素将继续查找，而不是就此停止。

线性探测是一次一个元素的探测，二次探测就是使用都是线性探测的二次方步长探测。例如线性探测是 ，那二次探测对应的就是 。

双重探测是当第一个散列函数冲突时使用第二个散列函数运算散列值，利用这种方式探测。例如，当 冲突时，就使用 计算散列值，如果再冲突就使用 计算散列值，依此类推。

关于散列表的空位多少使用“ 装载因子 ”（load factor）表示，装载因子满足数学关系 ，也就是说装载因子越大，散列表的空闲空间越小，散列冲突的可能性也就越大，一般我们会保持散列表有一定比例的空闲空间。

为了保持散列表一定比例的空闲空间，在装载因子到达一定阈值时需要对散列表数据进行搬移，但散列表搬移比较耗时。你可以试想下这样的步骤，在申请一个新的更大的散列表空间后，需要将旧散列表的数据重新通过散列函数生成散列值，再存储到新散列表中，想想都觉得麻烦。

散列表搬移的操作肯定会降低散列表的操作效率，那能不能对这一过程进行改进？其实可以将低效的扩容操作分摊至插入操作，当装载因子达到阈值时不一次性进行散列表搬移，而是在每次插入操作时将一个旧散列表数据搬移至新散列表，这样搬移操作的执行效率得到了提高，插入操作的时间复杂度也依然能保持 的高效。当新旧两个散列表同时存在时查询操作就要略作修改，需先在新散列表中查询，如果没有查找到目标数据再到旧散列表中查找。

当然，如果你对内存有更高效的利用要求，可以在装载因子降低至某一阈值时对散列表进行缩容处理。

除了开放寻址之外，还可以使用链表法解决散列冲突的问题。散列值对应的槽位并不直接存储数据，而是将数据存储在槽位对应的链表上，当进行查找操作时，根据散列函数计算的散列值找到对应槽位，再在槽位对应的链表上查找对应数据。

链表法操作的时间复杂度与散列表槽位和数据在槽位上的分布情况有关，假设有 n 个数据均匀分布在 m 个槽位的散列表上，那链表法的时间复杂度为 。链表法可以不用像开放寻址一样关心装载因子，但需要注意散列函数对散列值的计算，使链表结点能够尽可能均匀地分布在散列表槽位上，避免散列表退化为链表。有时黑客甚至会精心制造数据，利用散列函数制造散列冲突，使数据集中某些槽位上，造成散列表性能的极度退化。

面对这样的恶意行为散列表只能坐以待毙吗？其实不然，当槽位上的链表过长时，可以将其改造成之前学习过的跳表等，链表改造为跳表后查询的时间复杂度也只是退化为 ，依然是可以接受的范围。

链表法在存储利用上比开放寻址更加高效，不用提前申请存储空间，当有新数据时申请一个新的结点就行。而且链表法对装载因子也不那么敏感，装载因子的增高也只是意味着槽位对应的链表更长而已，链表增长也有将链表改造为跳表等结构的应对策略，所以链表法在装载因子超过 1 的情况下都可保持高效。

开放寻址不存在像链表法一样有链表过长而导致效率降低的烦恼，不过装载因子是开放寻址的晴雨表，装载因子过高会造成散列冲突机率的上升，开放寻址就需要不断探测空闲位置，算法的执行成本会不断被提高。而且在删除操作时只能将数据先标记为删除，对于频繁增删的数据效率会受到影响。

当然也可以在这种风险出现前进行散列表的动态扩容，不过这样就会出现大量空闲的存储空间，导致存储的利用效率过低，这种现象在数据量越大的情况下越明显。所以开放寻址比较适用于数据量较小的情况。

链表法对于散列冲突的处理更加灵活，同时对存储空间的利用效率也更高，但链表结点除了存储数据外还需要存储指针，如果存储数据较小指针占用的存储甚至会导致整体存储翻倍的情况，但存储数据较大时指针占用的存储也就可以忽略不计，所以链表法较适合存储数据对象较大，但频繁的增删操作不会对链表法造成明显的影响。因为这样的特点，链表法更加适合大数据量，或者数据对象较大的时候，如果数据操作频繁，那链表法更是不二之选。

散列表由数组扩展而来，使用散列函数将键计算为散列值，散列值对应数据存储的数组下标。虽然散列表的执行效率较高，但会有散列冲突的问题，可以通过开放寻址法和链表法解决此问题。

开放寻址存储利用效率较低，适用数据量较小并且增删不频繁的情况，如果数据量较大，增删频繁的情况更加适用链表法，相对之下链表法更加普适。

❺ 散列算法的算法思想

我也只能说说思想

散列算法的算法就是争取一个萝卜一个坑的原则

比如说有5个数 12,25,30,45,50,这几个数有个规律,就是十位数都不相同,

如果我设置一个散列函数f(value)=value/10;平常的时候,我们查找50，要比较

5次(其他算法可能不同),这里用散列算法只需要1次,就是解散列函数,key=50/10

=5,要找的数就在第5个位子.但是上面问题还是很多的,比如说查找55呢?就会出

错<因为55解散列函数之后,也是在第5个位子>,还有等等等问题,很显然这个是我

散列函数没设置好,当你把散列函数设置好了后,由于数据的庞大,冲突很有可能

产生,那么就需要我们来处理冲突了,所以写散列算法就是设置好的散列函数和

处理冲突的过程.这里散列算法涉及的查找就跟查找的数量无关,跟冲突率有直接

的关系

❻ 散列算法的软件开发散列算法

软件开发 中的散列函数或散列算法，又称哈希函数，英语：Hash Function,是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。
所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。但另一方面，散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的。但也可能不同，这种情况称为“散列碰撞”，这通常是两个不同长度的散列值，刻意计算出相同的输出值。输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。
典型的散列函数都有无限定义域，比如任意长度的字节字符串，和有限的值域，比如固定长度的比特串。在某些情况下，散列函数可以设计成具有相同大小的定义域和值域间的一一对应。一一对应的散列函数也称为排列。可逆性可以通过使用一系列的对于输入值的可逆“混合”运算而得到。
由于散列函数的应用的多样性，它们经常是专为某一应用而设计的。例如，加密散列函数假设存在一个要找到具有相同散列值的原始输入的敌人。一个设计优秀的加密散列函数是一个“单向”操作：对于给定的散列值，没有实用的方法可以计算出一个原始输入，也就是说很难伪造。为加密散列为目的设计的函数，如MD5，被广泛的用作检验散列函数。这样软件下载的时候，就会对照验证代码之后才下载正确的文件部分。此代码有可能因为环境因素的变化，如机器配置或者IP地址的改变而有变动。以保证源文件的安全性。
错误监测和修复函数主要用于辨别数据被随机的过程所扰乱的事例。当散列函数被用于校验和的时候，可以用相对较短的散列值来验证任意长度的数据是否被更改过。