Hash哈希

模型算法

密码学的几个算法（HASH、对称加密、公私钥）

什么是哈希？

我们就需要一种指纹一样的标志来检查文件的可靠性，这种指纹就是我们现在所用的Hash算法(也叫散列算法)。

在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。

哈希函数就是一种映射，是从关键字到存储地址的映射。
通常，包含哈希函数的算法的算法复杂度都假设为O(1)，这就是为什么在哈希表中搜索数据的时间复杂度会被认为是”平均为O(1)的复杂度”.

基本概念

在讲解具体内容前，首先我们要清楚以下几个概念：
1. 冲突（碰撞）
对于不同的关键字ki、kj，若ki != kj，但H(ki) = H(kj)的现象叫冲突(collision) ，即不同的输入却有相同的输出。我们应该尽量避免冲突，因为冲突不仅会使我们在查找的时候效率变慢，还甚至会被攻击者利用从而大量消耗系统资源。

散列算法（Hash Algorithm），又称哈希算法，杂凑算法，是一种从任意文件中创造小的数字「指纹」的方法。与指纹一样，散列算法就是一种以较短的信息来保证文件唯一性的标志，这种标志与文件的每一个字节都相关，而且难以找到逆向规律。因此，当原有文件发生改变时，其标志值也会发生改变，从而告诉文件使用者当前的文件已经不是你所需求的文件。

• 散列算法的不可逆性可以用来加密保护
  当然，作为一种指纹，散列算法最重要的用途在于给证书、文档、密码等高安全系数的内容添加加密保护。这一方面的用途主要是得益于散列算法的不可逆性，这种不可逆性体现在，你不仅不可能根据一段通过散列算法得到的指纹来获得原有的文件，也不可能简单地创造一个文件并让它的指纹与一段目标指纹相一致。散列算法的这种不可逆性维持着很多安全框架的运营，而这也将是本文讨论的重点。

经常使用的构造散列函数的方法

　　散列函数能使对一个数据序列的訪问过程更加迅速有效，通过散列函数，数据元素将被更快地定位：

　　1. 直接寻址法：取keyword或keyword的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，当中a和b为常数（这样的散列函数叫做自身函数）

　　2. 数字分析法：分析一组数据，比方一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体同样，这种话，出现冲突的几率就会非常大，可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大，假设用后面的数字来构成散列地址，则冲突的几率会明显减少。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

　　3. 平方取中法：取keyword平方后的中间几位作为散列地址。

　　4. 折叠法：将keyword切割成位数同样的几部分，最后一部分位数能够不同，然后取这几部分的叠加和（去除进位）作为散列地址。

　　5. 随机数法：选择一随机函数，取keyword的随机值作为散列地址，通经常使用于keyword长度不同的场合。

　　6. 除留余数法：取keyword被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅能够对keyword直接取模，也可在折叠、平方取中等运算之后取模。对p的选择非常重要，一般取素数或m，若p选的不好，easy产生同义词。
查找的性能分析

hash:零内存消耗，均匀，快速，简洁，来自Google的一致性哈希算法

https://blog.helong.info/blog/2015/03/13/jump_consistent_hash/

消息摘要和Hash算法的区别

hash算法是将输入内容变换为长度固定的输出，它主要是用于可以更快速地判断两个内容是否相同。

• 应用场景1：
  url 布隆过滤的hash方式，把url映射成id

• 应用场景2：
  数据库记录根据自增的主键id,运用规则hash算出该id需要存储在那个水平分区表里面

信息摘要是hash算法的一种，但拥有额外更严格的条件，例如不能逆运算，更严格的碰撞要求等

• 应用领域
  md5 sha crc32 ....

md5 对撞

王小云教授曾经成功制造出MD5的碰撞，即md5(a) = md5(b)。这样的碰撞只能随机生成，并不能根据一个已知的a求出b（即并没有破坏MD5的无冲突特性）。但这已经让他声名大噪了。

Hash算法总结 http://www.jianshu.com/p/bf1d7eee28d0

http://www.alloyteam.com/2017/05/hash-functions-introduction/