散列表、哈希

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

• 直接取余法:f(x):= x mod maxM ; maxM一般是不太接近 2^t 的一个质数。
• 乘法取整法:f(x):=trunc((x/maxX)*maxlongit) mod maxM，主要用于实数。
• 平方取中法:f(x):=(x*x div 1000 ) mod 1000000); 平方后取中间的，每位包含信息比较多。
  （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) SHA-1 及其它
  SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4同样原理,而且模仿了该算法。