哈希碰撞工具，哈希256

一、哈希函数详细讲解

哈希函数又称散列函数，杂凑函数，他是一个单向密码体制，即从明文到密文的不可逆映射，只有加密过程没有解密过程，哈希函数可以将任意长度的输入经过变化后得到固定长度的输出，这个固定长度的输出称为原消息的散列或消息映射

理想的哈希函数可以针对不同的输入得到不同的输出，如果存在两个不同的消息得到了相同的哈希值，那我们称这是一个碰撞

哈希函数的性质

a)压缩：对于任意大小的输入x，哈希值的长度很小，并且是固定的长度

b)易计算性

c)单向性，单向性也就是通过给定的哈希值得到原文是不可行的，求解哈希函数的逆很困难

d)抗碰撞性：理想的哈希函数是无碰撞的，但是实际的算法设计中很难做到，有两种抗碰撞性

i.弱抗碰撞性：对于给定的一个消息，要发现另一个消息使其碰撞在计算上不可行

ii.强抗碰撞性：对于任意的一对不同的消息，使其碰撞在计算上不可行

e)高灵敏度：当一个输入位发生变化时，会有一半以上的输出位发生变化

二、如何理解哈希表的工作原理

哈希表是根据关键值(key)来直接访问目标值(value)的一种数据结构。其特点就在于能够快捷的实现信息的查询和检索。

比如我们在手机中存放的通讯录就是用哈希表来实现的，即我们输入一个联系人的姓名，就能返回相应的电话号码。用哈希表实现的过程就是，将联系人姓名的字符通过一个哈希函数，映射成一个整数（哈希码），然后根据哈希码来索引出电话号码。比如哈希码为5，就表示是在存储位置为5，因此我们就能直接取出该位置的值，并返回结果。

那么实现哈希表的关键就在于哈希函数的构建，也就是如何建立一个合适的索引来满足如下条件：

1）同一个键每次输入到哈希函数中，其对应的哈希码也必须相同；

2）不同键对应的哈希码不能相同。

第一个条件意味着哈希函数必须是确定性的；第二个条件则要求不能出现哈希冲突。当两个或更多个键产生相同的哈希码时就会发生冲突（hashcollisions）。

比如我们现在考虑建立一个简单的哈希表来查询年龄,{Jim：5,Davis：7,Taylor:12,Bob:3}，如果我们选择哈希函数为输入键值的字符个数。那么在建立哈希表时，就讲Jim存放在位置3处，Jack存放在位置4处。而这样的话Jim和Bob的存储位置就会发生冲突，不符合哈希函数的要求。但是如果我们将哈希函数替换为首字母顺序存放，在这个数据中就没有哈希冲突了。

然而万一无法避免哈希冲突的话，我们可以用链接和线性探测的方法来避免哈希值发生碰撞。

链接就是将发生冲突的键值直接链接在链表的尾部；线性探测则是，如果在位置i处发生冲突，那么就检查i+1处是否为空，为空的话就将冲突键值放入其中，否则继续检查下一个。