什么是 Hash
 
Hash（哈希），又称“散列”。
 
散列（hash）英文原意是“混杂”、“拼凑”、“重新表述”的意思。
 
在某种程度上，散列是与排序相反的一种操作，排序是将集合中的元素按照某种方式比如字典顺序排列在一起，而散列通过计算哈希值，打破元素之间原有的关系，使集合中的元素按照散列函数的分类进行排列。
 
在介绍一些集合时，我们总强调需要重写某个类的 equlas() 方法和 hashCode() 方法，确保唯一性。这里的 hashCode() 表示的是对当前对象的唯一标示。计算 hashCode 的过程就称作 哈希。
 
为什么要有 Hash
 
我们通常使用数组或者链表来存储元素，一旦存储的内容数量特别多，需要占用很大的空间，而且在查找某个元素是否存在的过程中，数组和链表都需要挨个循环比较，而通过 哈希 计算，可以大大减少比较次数。
 

 
举个栗子：
 
现在有 4 个数 {2,5,9,13}，需要查找 13 是否存在。
 
1.使用数组存储，需要新建个数组 new int[]{2,5,9,13}，然后需要写个循环遍历查找：
 
    int[] numbers = new int[]{2,5,9,13};
    for (int i = 0; i < numbers.length; i++) {
        if (numbers[i] == 13){
            System.out.println("find it!");
            return;
        }
    }

 
1
2
3
4
5
6
7
8
 
这样需要遍历 4 次才能找到，时间复杂度为 O(n)。
 
2.而假如存储时先使用哈希函数进行计算，这里我随便用个函数：
 
 H[key] = key % 3;

 
1
2
 
四个数 {2,5,9,13} 对应的哈希值为：
 
 H[2] = 2 % 3 = 2;
 H[5] = 5 % 3 = 2;
 H[9] = 9 % 3 = 0;
 H[13] = 13 % 3 = 1;

 
1
2
3
4
5
 
然后把它们存储到对应的位置。
 
当要查找 13 时，只要先使用哈希函数计算它的位置，然后去那个位置查看是否存在就好了，本例中只需查找一次，时间复杂度为 O(1)。
 
因此可以发现，哈希 其实是随机存储的一种优化，先进行分类，然后查找时按照这个对象的分类去找。
 
哈希通过一次计算大幅度缩小查找范围，自然比从全部数据里查找速度要快。
 
比如你和我一样是个剁手族买书狂，家里书一大堆，如果书存放时不分类直接摆到书架上（数组存储），找某本书时可能需要脑袋从左往右从上往下转好几圈才能发现；如果存放时按照类别分开放，技术书、小说、文学等等分开（按照某种哈希函数计算），找书时只要从它对应的分类里找，自然省事多了。
 
哈希函数
 
哈希的过程中需要使用哈希函数进行计算。
 
哈希函数是一种映射关系，根据数据的关键词 key ，通过一定的函数关系，计算出该元素存储位置的函数。
 
表示为：
 
address = H [key]
 
几种常见的哈希函数（散列函数）构造方法
 
直接定址法 

   
取关键字或关键字的某个线性函数值为散列地址。
即 H(key) = key 或 H(key) = a*key + b，其中a和b为常数。
比如
除留余数法 

   
取关键字被某个不大于散列表长度 m 的数 p 求余，得到的作为散列地址。
即 H(key) = key % p, p < m。 
比如
数字分析法 

   
当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。
仅适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。
比如 
平方取中法 

   
先计算出关键字值的平方，然后取平方值中间几位作为散列地址。
随机分布的关键字，得到的散列地址也是随机分布的。
比如 
折叠法（叠加法） 

   
将关键字分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为散列地址。
用于关键字位数较多，并且关键字中每一位上数字分布大致均匀。 
比如 
随机数法 

   
选择一个随机函数，把关键字的随机函数值作为它的哈希值。
通常当关键字的长度不等时用这种方法。 
 
构造哈希函数的方法很多，实际工作中要根据不同的情况选择合适的方法，总的原则是尽可能少的产生冲突。
 
通常考虑的因素有关键字的长度和分布情况、哈希值的范围等。
 
如：当关键字是整数类型时就可以用除留余数法；如果关键字是小数类型，选择随机数法会比较好。
 
哈希冲突的解决
 
选用哈希函数计算哈希值时，可能不同的 key 会得到相同的结果，一个地址怎么存放多个数据呢？这就是冲突。
 
常用的主要有两种方法解决冲突：
 
1.链接法（拉链法）
 
拉链法解决冲突的做法是： 
将所有关键字为同义词的结点链接在同一个单链表中。
 
若选定的散列表长度为 m，则可将散列表定义为一个由 m 个头指针组成的指针数组 T[0..m-1] 。
 
凡是散列地址为 i 的结点，均插入到以 T[i] 为头指针的单链表中。 
T 中各分量的初值均应为空指针。
 
在拉链法中，装填因子 α 可以大于 1，但一般均取 α ≤ 1。
 

 
2.开放定址法
 
用开放定址法解决冲突的做法是：
 

  
用开放定址法解决冲突的做法是：当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。
 
 
简单的说：当冲突发生时，使用某种探查(亦称探测)技术在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。
 
按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。
 
a.线性探查法
 
hi=(h(key)+i) ％ m ，0 ≤ i ≤ m-1 
 
基本思想是： 
探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+1]，…，直到 T[m-1]，此后又循环到 T[0]，T[1]，…，直到探查到 有空余地址 或者到 T[d-1]为止。
 
b.二次探查法
 
hi=(h(key)+i*i) ％ m，0 ≤ i ≤ m-1 
 
基本思想是： 
探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+1^2]，T[d+2^2]，T[d+3^2],…，等，直到探查到 有空余地址 或者到 T[d-1]为止。
 
缺点是无法探查到整个散列空间。
 
c.双重散列法
 
hi=(h(key)+i*h1(key)) ％ m，0 ≤ i ≤ m-1 
 
基本思想是： 
探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+h1(d)], T[d + 2*h1(d)]，…，等。
 
该方法使用了两个散列函数 h(key) 和 h1(key)，故也称为双散列函数探查法。
 
定义 h1(key) 的方法较多，但无论采用什么方法定义，都必须使 h1(key) 的值和 m 互素，才能使发生冲突的同义词地址均匀地分布在整个表中，否则可能造成同义词地址的循环计算。
 
该方法是开放定址法中最好的方法之一。
 
哈希的应用
 
哈希表
分布式缓存
 
哈希表（散列表）
 
哈希表（hash table）是哈希函数最主要的应用。
 
哈希表是实现关联数组（associative array）的一种数据结构，广泛应用于实现数据的快速查找。
 

 
用哈希函数计算关键字的哈希值（hash value）,通过哈希值这个索引就可以找到关键字的存储位置，即桶（bucket）。哈希表不同于二叉树、栈、序列的数据结构一般情况下，在哈希表上的插入、查找、删除等操作的时间复杂度是 O(1)。
 
查找过程中，关键字的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。 
影响产生冲突多少有以下三个因素：
 
哈希函数是否均匀；
处理冲突的方法；
哈希表的加载因子。
 
哈希表的加载因子和容量决定了在什么时候桶数（存储位置）不够，需要重新哈希。
 
加载因子太大的话桶太多，遍历时效率变低；太大的话频繁 rehash，导致性能降低。所以加载因子的大小需要结合时间和空间效率考虑。
 
在 HashMap 中的加载因子为 0.75，即四分之三。
 
分布式缓存
 

  
网络环境下的分布式缓存系统一般基于一致性哈希（Consistent hashing）。简单的说，一致性哈希将哈希值取值空间组织成一个虚拟的环，各个服务器与数据关键字K使用相同的哈希函数映射到这个环上，数据会存储在它顺时针“游走”遇到的第一个服务器。可以使每个服务器节点的负载相对均衡，很大程度上避免资源的浪费。
  
在动态分布式缓存系统中，哈希算法的设计是关键点。使用分布更合理的算法可以使得多个服务节点间的负载相对均衡，可以很大程度上避免资源的浪费以及部分服务器过载。 使用带虚拟节点的一致性哈希算法，可以有效地降低服务硬件环境变化带来的数据迁移代价和风险，从而使分布式缓存系统更加高效稳定。
 
 
Thanks
 
http://www.nowamagic.net/librarys/veda/detail/1273
 
http://blog.csdn.net/cywosp/article/details/23397179/
 
http://www.cnblogs.com/qiaoshanzi/p/5295554.html
 
http://baike.baidu.com/view/549615.htm
 
https://books.google.co.jp/books?id=wCWmdhdX1AYC&pg=PA214&lpg=PA214&dq=%E6%95%B0%E5%AD%97%E5%88%86%E6%9E%90%E6%B3%95&source=bl&ots=5ieOT99Dob&sig=UcYbua2lwYocCQr32HF0XDF34h4&hl=zh-CN&sa=X&ved=0ahUKEwj104zw__fPAhUDw7wKHf3cAhIQ6AEISzAJ#v=onepage&q=%E6%95%B0%E5%AD%97%E5%88%86%E6%9E%90%E6%B3%95&f=false
 
http://sjjp.tjuci.edu.cn/sjjg/DataStructure/DS/web/chazhao/chazhao9.4.3.3.htm
 
http://www.cnblogs.com/qiaoshanzi/p/5295554.html


(function () {
('pre.prettyprint code').each(function () { var lines = 

(this).text().split(′\n′).length;var
numbering = $('
').addClass('pre-numbering').hide();

(this).addClass(′has−numbering′).parent().append(
numbering); for (i = 1; i

目录
 
一、什么是哈希（Hash）
 
二、哈希的原理和特点
 
三、哈希的实际用途
 
四、典型的哈希函数
 
（一）MD5
 
（二）SHA
 
五、Hash构造函数的方法
 

一、什么是哈希（Hash）
 
哈希也称“散列”函数或“杂凑”函数。它是一个不可逆的单向映射，将任意长度的输入消息M（或文件F）映射成为一个较短的定长哈希值H（M），也叫散列值（HashValue）、杂凑值或消息摘要。可见，这是一种单向密码体制，只有加密过程，没有解密过程（因此Hash求逆很困难）。
 
二、哈希的原理和特点
 
单向性：从哈希值不能反向推导原始数据（计算不可行），即从哈希输出无法倒推输入的原始数值。这是哈希函数安全性的基础。
灵敏性：对输入数据敏感，哪怕只改了一个Bit，得到的哈希值也大不相同。换言之，消息M的任何改变都会导致哈希值H（M）发生改变。
易压易算：Hash本质上是把一个大范围集合映射到另一个小范围集合。故输入值的个数必须与小范围相当或者更小，不然冲突就会很多。所以，哈希算法执行效率要高，散列结果要尽量均衡。
抗碰撞性：理想Hash函数是无碰撞的，但实际上很难做到这一点。有两种抗碰撞性：一种是弱抗碰撞性，即对于给定的消息，要发现另一个消息，满足在计算上是不可行的；另一种是强抗碰撞性，即对于任意一对不同的消息，使得在计算上也是不可行的。
也可以这么理解：正向快速、逆向困难、输入敏感、冲突避免
 
三、哈希的实际用途
 
Hash能把一个大范围映射到一个小范围，能对输入数据或文件进行校验，还可用于查找等。具体的：
 
唯一标识或数据检验：能够对输入数据或文件进行校验，判断是否相同或是否被修改。如图片识别，可针对图像二进制流进行摘要后MD5，得到的哈希值作为图片唯一标识；如文件识别，服务器在接受文件上传时，对比两次传送文件的哈希值，若相同则无须再次上传（传统的奇偶校验和CRC校验一定程度上能检测并纠正数据传输中的信道误码，但没有抗数据篡改的能力）。
安全加密：对于敏感数据比如密码字段进行MD5或SHA加密传输。哈希算法还可以检验信息的拥有者是否真实。如，用保存密码的哈希值代替保存密码，基本可以杜绝泄密风险。
数字签名。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。对Hash值，又称“数字摘要”进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。
散列函数:是构造散列表的关键。它直接决定了散列冲突的概率和散列表的性质。不过相对哈希算法的其他方面应用，散列函数对散列冲突要求较低，出现冲突时可以通过开放寻址法或链表法解决冲突。对散列值是否能够反向解密要求也不高。反而更加关注的是散列的均匀性，即是否散列值均匀落入槽中以及散列函数执行的快慢也会影响散列表性能。所以散列函数一般比较简单，追求均匀和高效。
*负载均衡：常用的负载均衡算法有很多，比如轮询、随机、加权轮询。如何实现一个会话粘滞的负载均衡算法呢？可以通过哈希算法，对客户端IP地址或会话SessionID计算哈希值，将取得的哈希值与服务器列表大小进行取模运算，最终得到应该被路由到的服务器编号。这样就可以把同一IP的客户端请求发到同一个后端服务器上。
*数据分片：比如统计1T的日志文件中“搜索关键词”出现次数该如何解决？我们可以先对日志进行分片，然后采用多机处理，来提高处理速度。从搜索的日志中依次读取搜索关键词，并通过哈希函数计算哈希值，然后再跟n(机器数)取模，最终得到的值就是应该被分到的机器编号。这样相同哈希值的关键词就被分到同一台机器进行处理。每台机器分别计算关键词出现的次数，再进行合并就是最终结果。这也是MapReduce的基本思想。再比如图片识别应用中给每个图片的摘要信息取唯一标识然后构建散列表，如果图库中有大量图片，单机的hash表会过大，超过单机内存容量。这时也可以使用分片思想，准备n台机器，每台机器负责散列表的一部分数据。每次从图库取一个图片，计算唯一标识，然后与机器个数n求余取模，得到的值就是被分配到的机器编号，然后将这个唯一标识和图片路径发往对应机器构建散列表。当进行图片查找时，使用相同的哈希函数对图片摘要信息取唯一标识并对n求余取模操作后，得到的值k，就是当前图片所存储的机器编号，在该机器的散列表中查找该图片即可。实际上海量数据的处理问题，都可以借助这种数据分片思想，突破单机内存、CPU等资源限制。
*分布式存储：一致性哈希算法解决缓存等分布式系统的扩容、缩容导致大量数据搬移难题。
四、典型的哈希函数
 
常见Hash算法有MD5和SHA系列，目前MD5和SHA1已经被破解，一般推荐至少使用SHA2-256算法。
 
（一）MD5
 
MD5属于Hash算法中的一种，它输入任意长度的信息，在处理过程中以512位输入数据块为单位，输出为128位的信息（数字指纹）。常用场景：
 
1、防篡改，保障文件传输可靠性：如SVN中对文件的控制；文件下载过程中，网站提供MD5值供下载后判断文件是否被篡改；BT中对文件块进行校验的功能。
 
2、增强密码保存的安全性：例如网站将用户密码的MD5值保存，而不是存储明文用户密码，当然，还会加SALT，进一步增强安全性。
 
3、数字签名：在部分网上赌场中，使用MD5算法来保证过程的公平性，并使用随机串进行防碰撞，增加解码难度。
 
算法实现过程：
 
第一步：消息填充，补长到512的倍数。最后64位为消息长度（填充前的长度）的低64位，一定要补长(64+1~512)，内容为100…0（如若消息长448，则填充512+64）。
 
第二步：分割，把结果分割为512位的块：Y0，Y1，…（每一个有16个32比特长字）。
 
第三步：计算，初始化MD buffer，128位常量(4个32bit字)，进入循环迭代，共L次。每次一个输入128位，另一个输入512位，结果输出128位，用于下一轮输入。
 
第四步：输出，最后一步的输出即为散列结果128位。
 
（二）SHA-1  Secure Hash Algorithm
 
安全哈希算法（Secure Hash Algorithm）主要适用于数字签名标准（Digital Signature Standard DSS）里面定义的数字签名算法（Digital Signature Algorithm DSA）。对于长度小于2^64b的消息，SHA-1将输入流按照每块512b（64B）进行分块，并产生20B或160b的信息摘要。
 
 
1.补位
 
消息补位使其长度在对512取模以后的余数是448。也就是说，（补位后的消息长度）% 512 = 448。即使长度已经满足对512取模后余数是448，补位也必须要进行。
 
补位是这样进行的：先补一个1，然后再补0，直到长度满足对512取模后余数是448。总而言之，补位是至少补一位，最多补512位。还是以前面的“abc”为例显示补位的过程。
 
原始信息：  011000010110001001100011
 
补位第一步：0110000101100010011000111,首先补一个“1”
 
补位第二步：01100001011000100110001110…..0，然后补423个“0”
 
我们可以把最后补位完成后的数据用16进制写成下面的样子，确保是448b：
 
61626380000000000000000000000000
 
00000000000000000000000000000000
 
00000000000000000000000000000000
 
0000000000000000
 
2.补长度
 
补长度是将原始数据的长度补到已经进行了补位操作的消息后面。通常用一个64位的数据来表示原始消息的长度。如果消息长度不大于2^64，那么第一个字就是0。
 
在进行了补长度的操作以后，整个消息就变成下面这样了（16进制格式）：
 
61626380000000000000000000000000
 
00000000000000000000000000000000
 
00000000000000000000000000000000
 
00000000000000000000000000000018
 
如果原始的消息长度超过了512，我们需要将它补成512的倍数。然后我们把整个消息分成一个一个512位的数据块。分别处理每一个数据块，从而得到消息摘要。
 
3.使用的常量
 
一系列的常量字K(0),K(1),...,K(79)，如果以16进制给出。它们如下：
 
Kt=0x5A827999(0<=t<=19)
 
Kt=0x6ED9EBA1(20<=t<=39)
 
Kt=0x8F1BBCDC(40<=t<=59)
 
Kt=0xCA62C1D6(60<=t<=79).
 
4.需要使用的函数
 
在SHA1中我们需要一系列的函数。每个函数ft(0<=t<=79)都操作32位字B，C，D并且产生32位字作为输出。
 
ft(B,C,D)可以如下定义：
 
ft(B,C,D)=(BANDC)or((NOTB)ANDD)(0<=t<=19)
 
ft(B,C,D)=BXORCXORD(20<=t<=39)
 
ft(B,C,D)=(BANDC)or(BANDD)or(CANDD)(40<=t<=59)
 
ft(B,C,D)=BXORCXORD(60<=t<=79).
 
5.计算消息摘要
 
必须使用进行了补位和补长度后的消息来计算消息摘要。计算需要两个缓冲区，每个都由5个32位的字组成，还需要一个80个32位字的缓冲区。第一个5个字的缓冲区被标识为A，B，C，D，E。第一个5个字的缓冲区被标识为H0,H1,H2,H3,H4。80个字的缓冲区被标识为W0,W1,...,W79。
 
另外还需要一个一个字的TEMP缓冲区。
 
为了产生消息摘要，在第4部分中定义的16个字的数据块M1,M2,...,Mn会依次进行处理，处理每个数据块Mi包含80个步骤。
 

 在处理每个数据块之前，缓冲区{Hi}被初始化为下面的值（16进制）
 
H0=0x67452301
 
H1=0xEFCDAB89
 
H2=0x98BADCFE
 
H3=0x10325476
 
H4=0xC3D2E1F0.
 

 现在开始处理M1,M2,...,Mn。为了处理Mi,需要进行下面的步骤
 
(1)将Mi分成16个字W0,W1,...,W15,W0是最左边的字
 
(2)对于t=16到79令Wt=S1(Wt-3XORWt-8XORWt-14XORWt-16).
 
(3)令A=H0,B=H1,C=H2,D=H3,E=H4.
 
(4)对于t=0到79，执行下面的循环
 
TEMP=S5(A)+ft(B,C,D)+E+Wt+Kt;
 
E=D;D=C;C=S30(B);B=A;A=TEMP;
 
(5)令H0=H0+A,H1=H1+B,H2=H2+C,H3=H3+D,H4=H4+E.
 
在处理完所有的Mn,后，消息摘要是一个160位的字符串，以下面的顺序标识H0H1H2H3H4。
 
（三）SHA-2系列
 
SHA-2是六个不同算法的合称，包括：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。除了生成摘要的长度、循环运行的次数等一些微小差异外，这些算法的基本结构是一致的。对于任意长度的消息，SHA256都会产生一个256bit长的消息摘要。
 
详细参见：sha256算法原理 - Practical - 博客园
 
至今尚未出现对SHA-2有效的攻击，SHA-2和SHA-1并没有接受公众密码社区的详细检验，所以它们的密码安全性还不被广泛信任。
 
总体上，HAS-256与MD4、MD5以及HSA-1等哈希函数的操作流程类似，在哈希计算之前首先要进行以下两个步骤：
 
对消息进行补位处理，最终的长度是512位的倍数；
以512位为单位对消息进行分块为M1,M2,…,Mn
处理消息块：从一个初始哈希H0开始，迭代计算：Hi = Hi-1 + CMi(Hi-1)
其中C是SHA256的压缩函数，+是mod 2^32加法,Hn是消息区块的哈希值。
 
五、Hash构造函数的方法
 
1.直接定址法（极少用）
 
以数据元素关键字k本身或它的线性函数作为它的哈希地址，即：H（k）=k或H（k）=a×k+b；(其中a,b为常数)。
 
此法仅适合于：地址集合的大小==关键字集合的大小，其中a和b为常数。
 
2.数字分析法
 
假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时，可以通过对关键字的各位进行分析，丢掉分布不均匀的位，作为哈希值。它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。
 
此法适于:能预先估计出全体关键字的每一位上各种数字出现的频度。
 
3.折叠法
 
将关键字分割成若干部分，然后取它们的叠加和为哈希地址。两种叠加处理的方法：移位叠加:将分割后的几部分低位对齐相加；边界叠加:从一端沿分割界来回折叠，然后对齐相加。
 
所谓折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位），这方法称为折叠法。这种方法适用于关键字位数较多，而且关键字中每一位上数字分布大致均匀的情况。
 
折叠法中数位折叠又分为移位叠加和边界叠加两种方法，移位叠加是将分割后是每一部分的最低位对齐，然后相加；边界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。
 
此法适于：关键字的数字位数特别多。
 
4.平方取中法
 
这是一种常用的哈希函数构造方法。这个方法是先取关键字的平方，然后根据可使用空间的大小，选取平方数是中间几位为哈希地址。哈希函数H(key)=“key2的中间几位”因为这种方法的原理是通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。
 
此法适于:关键字中的每一位都有某些数字重复出现频度很高的现象。
 
5.减去法
 


 减去法是数据的键值减去一个特定的数值以求得数据存储的位置。
 
6.基数转换法
 
将十进制数X看作其他进制，比如十三进制，再按照十三进制数转换成十进制数，提取其中若干为作为X的哈希值。一般取大于原来基数的数作为转换的基数，并且两个基数应该是互素的。
 
7.除留余数法
 
假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为h（k）=k%p，其中%为模p取余运算。除留余数法的模p取不大于表长且最接近表长m素数时效果最好，且p最好取1.1n～1.7n之间的一个素数（n为存在的数据元素个数）。
 
8.随机数法
 
设定哈希函数为:H(key)=Random(key)其中，Random为伪随机函数
 
此法适于：对长度不等的关键字构造哈希函数。
 
9．随机乘数法
 
亦称为“乘余取整法”。随机乘数法使用一个随机实数f,0≤f<1,乘积f*k的分数部分在0～1之间，用这个分数部分的值与n（哈希表的长度）相乘，乘积的整数部分就是对应的哈希值，显然这个哈希值落在0～n-1之间。其表达公式为：Hash(k)=「n*(f*k%1)」其中“f*k%1”表示f*k的小数部分，即f*k%1=f*k-「f*k」
 
此方法的优点是对n的选择不很关键。通常若地址空间为p位就是选n=2p.Knuth对常数f的取法做了仔细的研究，他认为f取任何值都可以，但某些值效果更好。如f=（-1）/2=0.6180329...比较理想。
 
10．字符串数值哈希法
 
把字符串的前10个字符的ASCⅡ值之和对N取摸作为Hash地址，只要N较小，Hash地址将较均匀分布[0，N]区间内。对于N很大的情形，可使用ELFHash(ExecutableandLinkingFormat,ELF,可执行链接格式)函数，它把一个字符串的绝对长度作为输入，并通过一种方式把字符的十进制值结合起来，对长字符串和短字符串都有效，这种方式产生的位置可能不均匀分布。
 
11.旋转法
 
旋转法是将数据的键值中进行旋转。旋转法通常并不直接使用在哈希函数上，而是搭配其他哈希函数使用。

什么是哈希函数？
 
（哈希函数，又称散列算法，英语：Hash Function）是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。
 在java的String类中有hashcode方法：
 
 当然Integer，boolean，对象等都有自己的哈希函数。
 那么哈希函数的有几种构造方法呢？
 
上图是String类的哈希函数，计算出来的哈希值与字符串的字符个数和ASCII码有关。由此计算出的哈希值必唯一。
除此之外还有随机乘数法、ASCII码加和法、移位法。
还有直接定址法、除留余数、平方取中。
 
哈希值
 
哈希值又称哈希码，是哈希函数计算出来，表示一个对象的值。
 
`如果两个哈希值是不相同的（根据同一函数），那么这两个散列值的原始输入一定是不相同的。
相同的哈希函数计算出来的哈希值是不一定唯一`的，如果两个字符串的哈希值相同，那么字符串一定是相同的。但如果用除留余数法计算出来的哈希值，哈希值相同，输入值却不同。
如果两个哈希值相同，两个输入值很可能(极大概率)是相同的，但也可能不同，这种情况称为“哈希碰撞”。
 
哈希表
 
哈希表的由来
 
链表是一个能够快速插入删除的数据结构，但是查找需要遍历。
数组是一个找到比较快的数据结构，但是必须知道数组的下标，如果不知道数组的下标，依然需要遍历。但是插入和删除也是比较麻烦。
 
由上述的两个问题，能不能找到一个快速插入删除、不需要数组下标的数据结构-------哈希表
 
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
 
哈希表怎么创建的？
 
数组是知道下标后，直接找到下标对应的值。在校园中，我们如果知道一个学生的学号，那么可以很快找到他的名字。那么基于这种知道学号就可以找出对应学生的姓名怎么实现呢？
 哈希函数计算哈希值
 我们的学号是唯一的，并且是一个int型的数字。我们可以根据哈希函数（除留余数法）计算出哈希值，
 并以哈希值为数组下标，存储名字。
 由此我们可以根据关键码值（key-value）来进行访问。
 
所以哈希表，也是采用了数组的思想，将key映射到数组中的位置。如何映射的呢？通过哈希函数计算哈希值。
 
但是问题来了，通过除留余数法（除以13）计算出来的哈希值相同怎么办？比如学号是5，则哈希值为5。那么序号为18，哈希值也为5。这样就产生了哈希碰撞。
 
哈希碰撞
 
回到前面，我们创建哈希表的原因是数组和链表并不能很好的满足查找一个元素（知道学号，怎么知道名字（这个例子有点憨批））。计算机的资源是有限的，不可能去创建一个很大的数组供我们去查询。在缩短数组长度，并且进行存储。肯定会有碰撞的时候。当然这个问题可以解决，如下。
 哈希碰撞是可以解决的，比如用开放地址法，链地址法。
 
链地址法
 
我们将相同的哈希值的元素，放在一个链表上，这样不同哈希值也就有不同的链表，我们将这些链表拼成一个数组。
 
 这就是链表+数组创建的哈希表，解决了哈希碰撞的问题。
 
哈希查找的高效率也是有一定代价的，具体来说它是一种以空间换时间的查找算法，哈希表的构造需要合适的哈希函数，在构造哈希表时要分配跟多的空间来给记录，在记录发生冲突的时候，我们就需要一些冲突的处理方法。哈希表的构造过程也会因此更加复杂。

哈希函数命令：Get-FileHash -Algorithm [算法] 文件路径
 支持的哈希算法：SHA1,SHA256,SHA384,SHA512,MACTripleDES,MD5,RIPEMD160
 以Win10为例，右击“开始”菜单，选择“Windows PowerShell(管理员)”；
 
 
例如：
 
 
 
 
  
Get-FileHash -Algorithm SHA256 D:\新建文件夹\test\readme.txt