java中hash函数都有什么用啊

Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。

简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

HASH主要用于信息安全领域中加密算法，他把一些不同长度的信息转化成杂乱的128位的编码里,叫做HASH值 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系

了解了hash基本定义，就不能不提到一些著名的hash算法，MD5 和 SHA1 可以说是目前应用最广泛的Hash算法，而它们都是以 MD4 为基础设计的。那么他们都是什么意思呢？

这里简单说一下：

1) MD4

MD4(RFC 1320)是 MIT 的 Ronald L Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位 *** 作数的位 *** 作来实现的。

2) MD5

MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好

3) SHA1 及其他

SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。

通过之前的学习，我们已经了解了哈希函数在散列表中的应用，哈希函数就是哈希算法的一个应用。那么在这里给出哈希的定义： 将任意长度的二进制值串映射为固定长度的二进制值串，这个映射规则就是哈希算法，得到的二进制值串就是哈希值 。

要设计一个好的哈希算法并不容易，它应该满足以下几点要求：

哈希算法的应用非常广泛，在这里就介绍七点应用：

有很多著名的哈希加密算法：MD5、SHA、DES它们都是通过哈希进行加密的算法。

对于加密的哈希算法来说，有两点十分重要：一是很难根据哈希值反推导出原始数据；二是散列冲突的概率要很小。

当然，哈希算法不可能排除散列冲突的可能，这用数学中的 鸽巢原理 就可以很好解释。以MD5算法来说，得到的哈希值为一个 128 位的二进制数，它的数据容量最多为 2 128 bit，如果超过这个数据量，必然会出现散列冲突。

在加密解密领域没有绝对安全的算法，一般来说，只要解密的计算量极其庞大，我们就可以认为这种加密方法是较为安全的。

假设我们有100万个，如果我们在中寻找某一个是非常耗时的，这是我们就可以使用哈希算法的原理为设置唯一标识。比如，我们可以从的二进制码串开头取100个字节，从中间取100个字节，从结尾取100个字节，然后将它们合并，并使用哈希算法计算得到一个哈希值，将其作为的唯一标识。

使用这个唯一标识判断是否在图库中，这可以减少甚多工作量。

在传输消息的过程中，我们担心通信数据被人篡改，这时就可以使用哈希函数进行数据校验。比如BT协议中就使用哈希栓发进行数据校验。

在散列表那一篇中我们就讲过散列函数的应用，相比于其它应用，散列函数对于散列算法冲突的要求低很多（我们可以通过开放寻址法或链表法解决冲突），同时散列函数对于散列算法是否能逆向解密也并不关心。

散列函数比较在意函数的执行效率，至于其它要求，在之前的我们已经讲过，就不再赘述了。

接下来的三个应用主要是在分布式系统中的应用

复杂均衡的算法很多，如何实现一个会话粘滞的负载均衡算法呢？也就是说，我们需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。

最简单的办法是我们根据客户端的 IP 地址或会话 ID 创建一个映射关系。但是这样很浪费内存，客户端上线下线，服务器扩容等都会导致映射失效，维护成本很大。

借助哈希算法，我们可以很轻松的解决这些问题：对客户端的 IP 地址或会话 ID 计算哈希值，将取得的哈希值域服务器的列表的大小进行取模运算，最后得到的值就是被路由到的服务器的编号。

假设有一个非常大的日志文件，里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？

分析一下，这个问题有两个难点：一是搜索日志很大，没办法放到一台机器的内存中；二是如果用一台机器处理这么大的数据，处理时间会很长。

针对这两个难点，我们可以先对数据进行分片，然后使用多台机器处理，提高处理速度。具体思路：使用 n 台机器并行处理，从日志文件中读出每个搜索关键词，通过哈希函数计算哈希值，然后用 n 取模，最终得到的值就是被分配的机器编号。

这样，相同的关键词被分配到了相同的机器上，不同机器只要记录属于自己那部分的关键词的出现次数，最终合并不同机器上的结果即可。

针对这种海量数据的处理问题，我们都可以采用多机分布式处理。借助这种分片思路，可以突破单机内存、CPU等资源的限制。

处理思路和上面出现的思路类似：对数据进行哈希运算，对机器数取模，最终将存储数据（可能是硬盘存储，或者是缓存分配）分配到不同的机器上。

你可以看一下上图，你会发现之前存储的数据在新的存储规则下全部失效，这种情况是灾难性的。面对这种情况，我们就需要使用一致性哈希算法。

哈希算法是应用非常广泛的算法，你可以回顾上面的七个应用感受一下。

其实在这里我想说的是一个思想： 用优势弥补不足 。

例如，在计算机中，数据的计算主要依赖 CPU ，数据的存储交换主要依赖内存。两者一起配合才能实现各种功能，而两者在性能上依然无法匹配，这种差距主要是： CPU运算性能对内存的要求远高于现在的内存能提供的性能。

也就是说，CPU运算很快，内存相对较慢，为了抹平这种差距，工程师们想了很多方法。在我看来，散列表的使用就是利用电脑的高计算性能（优势）去弥补内存速度（不足）的不足，你仔细思考散列表的执行过程，就会明白我的意思。

以上就是哈希的全部内容

哈希表：即散列存储结构。

散列法存储的基本思想：建立记录关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。

这样，不经过比较，一次存取就能得到所查元素的查找方法

优点：查找速度极快（O(1)）,查找效率与元素个数n无关！

哈希方法(杂凑法)

选取某个函数，依该函数按关键字计算元素的存储位置并按此存放；查找时也由同一个函数对给定值k计算地址，将k与地址中内容进行比较，确定查找是否成功。

哈希函数(杂凑函数)

哈希方法中使用的转换函数称为哈希函数(杂凑函数)在记录的关键码与记录的存储地址之间建立的一种对应关系

有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）＝k ， H(k)称为散列函数,画出存储结构图。

根据散列函数H（k）＝k ，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，……，

根据存储时用到的散列函数H(k)表达式，迅即可查到结果！

例如，查找key=9,则访问H(9)=9号地址，若内容为9则成功；

若查不到，应当设法返回一个特殊值，例如空指针或空记录。

很显然这种搜索方式空间效率过低。

哈希函数可写成：addr(ai)=H(ki)

选取某个函数，依该函数按关键字计算元素的存储位置并按此存放；查找时也由同一个函数对给定值k计算地址，将k与地址中内容进行比较，确定查找是否成功。哈希方法中使用的转换函数称为哈希函数(杂凑函数)在记录的关键码与记录的存储地址之间建立的一种对应关系。

通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。

有6个元素的关键码分别为：（14，23，39，9，25，11）。

选取关键码与元素位置间的函数为H(k)=k mod 7

根据哈希函数算出来发现同一个地址放了多个关键码，也就是冲突了。

在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。

所以，哈希方法必须解决以下两个问题：

1）构造好的哈希函数

（a）所选函数尽可能简单，以便提高转换速度；

（b）所选函数对关键码计算出的地址，应在哈希地址内集中并大致均匀分布，以减少空间浪费。

2）制定一个好的解决冲突的方案

查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。

从上面两个例子可以得出如下结论：

哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键码的哈希函数值都落在表长允许的范围之内即可

冲突：key1≠key2，但H(key1)=H(key2)

同义词：具有相同函数值的两个关键码

哈希函数冲突不可避免，只能尽量减少。所以，哈希方法解决两个问题：

构造好的哈希函数；

制定解决冲突基本要求：

要求一：n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。

要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。

Hash(key) = a·key + b (a、b为常数)

优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突

缺点：要占用连续地址空间，空间效率低。

例关键码集合为{100，300，500，700，800，900}，

选取哈希函数为Hash(key)=key/100，

则存储结构（哈希表）如下：

Hash(key)=key mod p (p是一个整数)

特点：以关键码除以p的余数作为哈希地址。

关键：如何选取合适的p？p选的不好，容易产生同义词

技巧：若设计的哈希表长为m，则一般取p≤m且为质数

（也可以是合数，但不能包含小于20的质因子）。

Hash(key)= ⎣ B ( A key mod 1 ) ⎦

(A、B均为常数，且0<A<1，B为整数)

特点：以关键码key乘以A，取其小数部分，然后再放大B倍并取整，作为哈希地址。

例：欲以学号最后两位作为地址，则哈希函数应为：

H(k)=100 (001 k % 1 )

其实也可以用法2实现： H(k)=k % 100

特点：选用关键字的某几位组合成哈希地址。选用原则应当是：各种符号在该位上出现的频率大致相同。

例：有一组（例如80个）关键码，其样式如下：

讨论：

① 第1、2位均是“3和4”，第3位也只有“ 7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。

② 若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。

特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。(适于不知道全部关键码情况)

理由：因为中间几位与数据的每一位都相关。

例：2589的平方值为6702921，可以取中间的029为地址。

特点：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。

适用于：关键码位数很多,且每一位上各符号出现概率大致相同的情况。

法1：移位法 ── 将各部分的最后一位对齐相加。

法2：间界叠加法──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。

例：元素42751896,

用法1： 427＋518＋96=1041

用法2： 427 518 96—> 724+518+69 =1311

7、随机数法

Hash(key) = random ( key ) (random为伪随机函数)

适用于：关键字长度不等的情况。造表和查找都很方便。

小结：构造哈希函数的原则：

① 执行速度（即计算哈希函数所需时间）；

② 关键字的长度；

③ 哈希表的大小；

④ 关键字的分布情况；

⑤ 查找频率。

设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。

1）线性探测法

Hi=(Hash(key)+di) mod m ( 1≤i < m )

其中：

Hash(key)为哈希函数

m为哈希表长度

di 为增量序列 1，2，…m-1，且di=i

关键码集为 {47，7，29，11，16，92，22，8，3}，

设：哈希表表长为m=11；

哈希函数为Hash(key)=key mod 11；

拟用线性探测法处理冲突。建哈希表如下：

解释：

① 47、7是由哈希函数得到的没有冲突的哈希地址；

② Hash(29)=7，哈希地址有冲突，需寻找下一个空的哈希地址：由H1=(Hash(29)+1) mod 11=8，哈希地址8为空，因此将29存入。

③ 另外，22、8、3同样在哈希地址上有冲突，也是由H1找到空的哈希地址的。

其中3 还连续移动了（二次聚集）

线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；

线性探测法的缺点：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，

因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。

解决方案：可采用二次探测法或伪随机探测法，以改善“堆积”问题。

2） 二次探测法

仍举上例，改用二次探测法处理冲突，建表如下：

Hi=(Hash(key)±di) mod m

其中：Hash(key)为哈希函数

m为哈希表长度，m要求是某个4k+3的质数；

di为增量序列 1^2，-1 ^2，2 ^2，-2 ^2，…，q ^2

注：只有3这个关键码的冲突处理与上例不同，

Hash(3)=3，哈希地址上冲突，由

H1=(Hash(3)+1 ^2) mod 11=4，仍然冲突；

H2=(Hash(3)-1 ^2) mod 11=2，找到空的哈希地址，存入。

3） 若di＝伪随机序列，就称为伪随机探测法

基本思想：将具有相同哈希地址的记录(所有关键码为同义词)链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。

设{ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的哈希函数为：

Hash(key)=key mod 11，

用拉链法处理冲突，则建表如图所示。

Hi=RHi(key) i=1, 2, …，k

RHi均是不同的哈希函数，当产生冲突时就计算另一个哈希函数，直到冲突不再发生。

优点：不易产生聚集；

缺点：增加了计算时间。

思路：除设立哈希基本表外，另设立一个溢出向量表。

所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表。

明确：散列函数没有“万能”通式（杂凑法），要根据元素集合的特性而分别构造。

讨论：哈希查找的速度是否为真正的O（1）？

不是。由于冲突的产生，使得哈希表的查找过程仍然要进行比较，仍然要以平均查找长度ASL来衡量。

一般地，ASL依赖于哈希表的装填因子α,它标志着哈希表的装满程度。

0≤α≤1

α 越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。

例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)

哈希函数为：H(key)=key MOD 13, 哈希表长为m=16，

设每个记录的查找概率相等

(1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m

(2) 用二次探测再散列处理冲突，即Hi=(H(key)+di) MOD m

(3) 用链地址法处理冲突

1） 散列存储的查找效率到底是多少？

答：ASL与装填因子α有关！既不是严格的O(1)，也不是O(n)

2）“冲突”是不是特别讨厌？

答：不一定！正因为有冲突，使得文件加密后无法破译！（单向散列函数不可逆，常用于数字签名和间接加密）。

利用了哈希表性质：源文件稍稍改动，会导致哈希表变动很大。