什么是hash函数
哈希函数（Hash Function），也称为散列函数，给定一个输入 x ，它会算出相应的输出 H(x) 。哈希函数的主要特征是： 另外哈希函数一般还要求以下两种特点： 1、免碰撞 ：即不会出现输入 x≠y ，但是H(x)=H(y) 的情况，其实这个特点在理论上并不成立，比如目前比特币使用的 SHA256 算法，会有 2^256 种输出，如果我们进行 2^256 + 1 次输入，那么必然会产生一次碰撞，事实上，通过 理论证明 ，通过 2^130 次输入就会有99%的可能性发生一次碰撞，不过即使如此，即便是人类制造的所有计算机自宇宙诞生开始一直运算到今天，发生一次碰撞的几率也是极其微小的。 2、隐匿性 ：也就是说，对于一个给定的输出结果 H(x) ，想要逆推出输入 x ，在计算上是不可能的。如果想要得到 H(x) 的可能的原输入，不存在比穷举更好的方法。 hash 算法的原理是试图将一个空间的数据集映射到另外一个空间（通常比原空间要小），并利用质数将数据集能够均匀的映射。目前主流的 hash 算法有： md4 、 md5 、 sha系列 。 MD4是麻省理工学院教授 Ronald Rivest 于1990年设计出来的算法。其摘要长度为128位，一般用32位的十六进制来表示。 2004年8月清华大学教授王小云，指出在计算MD4时可能发生杂凑冲撞。不久之后，Dobbertin 等人发现了MD4在计算过程中第一步和第三步中的漏洞，并向大家演示了如何利用一部普通电脑在几分钟内找到MD4中的冲突，毫无疑问，MD4就此被淘汰掉了。 1991年，Rivest 开发出技术上更为趋近成熟的MD5算法，它在MD4的基础上增加了"安全-带子"（safety-belts）的概念。虽然 MD5 比 MD4 复杂度大一些，但却更为安全。这个算法很明显的由四个和 MD4 设计有少许不同的步骤组成。 MD5 拥有很好的抗修改性，即对原数据进行任何改动，哪怕只修改1个字节，所得到的MD5值都有很大区别。 MD5很好的用在了大文件的断点续传上：如果有一个 5MB 的文件 客户端把它分割成5片 1MB 的文件 在上传的时候上传两个 MD5 值，一个是当前上传的文件片的 MD5 还有一个就是拼接之后的 MD5 (如果现在上传的是第二片 这个MD5就应该是第一片加上第二片的MD5)， 通过这样的方式能保证文件的完整性。 当如果文件传到一半断了，服务器可以通过验证文件 MD5 值就可以得知用户已经传到了第几片，并且知道之前上传的文件有没有发生变化，就可以判断出用户需要从第几片开始传递。 不过在2004年8月的国际密码学会议（Crypto’2004），王小云提出了一种快速找到 MD5 碰撞的方法（参见其 论文 ），降低了 MD5 的安全性，人们开始寻求更加可靠的加密算法。 SHA的全称是Secure Hash Algorithm(安全hash算法)，SHA系列有五个算法，分别是 SHA-1、SHA-224、SHA-256、SHA-384，和SHA-512，由美国国家安全局（NSA）所设计，并由美国国家标准与技术研究院（NIST）发布，是美国的政府标准。后四者有时并称为 SHA-2。SHA-1在许多安全协定中广为使用，包括 TLS/SSL 等，是 MD5 的后继者。 最初该算法于1993年发布，称做安全散列标准 (Secure Hash Standard)，最初这个版本被称为"SHA-0"，它在发布之后很快就被NSA撤回，因为有很大的安全缺陷，之后在1995年发布了修订版本，也就是SHA-1。 SHA-0 和 SHA-1 会从一个最大 2^64 位元的讯息中产生一串 160 位元的摘要，然后以 MD4 及 MD5 算法类似的原理来加密。 2017年，谷歌发布了最新的研究成功，宣布攻破了SHA-1，并详细描述了成功的SHA1碰撞攻击方式，使用这种方式，可以在亚马逊的云计算平台上，耗时10天左右创建出SHA-1碰撞，并且成本可以控制在11万美元以内。 即使如此，对于单台机器来说攻击的成本依然很高，发生一次SHA-1碰撞需要超过 9,223,372,036,854,775,808 个SHA1计算，这需要使用你的机器进行6500年计算。 SHA2包括了SHA-224、SHA-256、SHA-384，和SHA-512，这几个函数都将讯息对应到更长的讯息摘要，以它们的摘要长度（以位元计算）加在原名后面来命名，也就是说SHA-256会产生256位长度摘要。 SHA-2相对来说是安全的，至今尚未出现对SHA-2有效的攻击！ 由于目前大量的网站使用的SSL数字证数都是使用SHA-1签名的，而SHA-1又已经不安全，各大浏览器厂商均宣布了弃用SHA-1的时间表： 可以看出，在时间表之后，如果检测到网站的证书使用的还是SHA-1，就会弹出警告： 为了防止网站因出现上面的警告而显得不专业，我们需要尽快的申请使用跟安全放心的基于SHA-2签名的证书。
什么是Hash函数?Hash函数在密码学中有什么作用
1、哈希函数杂凑函数，是一个从消息空间到像空间的不可逆映射。 2、hash算法的原理是试图将一个空间的数据集映射到另外一个空间（通常比原空间要小），并利用质数将数据集能够均匀的映射。目前主流的hash算法有：md4、md5、sha系列。 3、Hash函数（也称散列函数或散列算法）的输入为任意长度的消息，而输出为某一固定长度的消息，即Hash函数是一种将任意长度的消息串M映射成为一个定长消息的函数，记为H。 4、hash函数是一种常见的密码学算法，它可以将任意长度的数据压缩成固定长度的哈希值（hash值）。哈希值通常用于验证数据的完整性和安全性。
哈希表详解
哈希表：即散列存储结构。 散列法存储的基本思想：建立记录关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。 这样，不经过比较，一次存取就能得到所查元素的查找方法 优点：查找速度极快（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 (0.01 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）“冲突”是不是特别讨厌？ 答：不一定！正因为有冲突，使得文件加密后无法破译！（单向散列函数不可逆，常用于数字签名和间接加密）。 利用了哈希表性质：源文件稍稍改动，会导致哈希表变动很大。
什么是哈希表啊
简单说就是按照哈希函数关系建立的表
具体内容请参考数据结构相关知识~
下面引用一些别的地方
1 基本原理
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。
2 函数构造
构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：
a) 除余法：
选择一个适当的正整数 p ，令 h(k ) = k mod p
这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。
b) 数字选择法：
如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。
3 冲突处理
线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。
4 支持运算
哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。
设插入的元素的关键字为 x ，A 为存储的数组。
初始化比较容易，例如
const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素
p=9997; // 表的大小
procedure makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[i]:=empty;
End;
哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：
function h(x:longint):Integer;
begin
h:= x mod p;
end;
我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数 locate
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (ix)and(A[(orig+i)mod S]empty) do
inc(i);
//当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元
//素存储的单元，要么表已经满了
locate:=(orig+i) mod S;
end;
插入元素
procedure insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函数的返回值
if A[posi]=empty then A[posi]:=x
else error; //error 即为发生了错误，当然这是可以避免的
end;
查找元素是否已经在表中
procedure member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A[posi]=x then member:=true
else member:=false;
end;
这些就是建立在哈希表上的常用基本运算。