常见的hash算法有哪些及其原理是什么
MD4（RFC 1320）是 MIT 的Ronald L. Rivest在 1990 年设计的，MD 是 Message Digest（消息摘要） 的缩写。
它适用在32位字长的处理器上用高速软件实现——它是基于 32位操作数的位操作来实现的。
MD5（RFC 1321）是 Rivest 于1991年对MD4的改进版本。
它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。
MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。
SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举（brute-force）性更好。
SHA-1 设计时基于和MD4相同原理，并且模仿了该算法。
散列表，它是基于快速存取的角度设计的，也是一种典型的“空间换时间”的做法。
顾名思义，该数据结构可以理解为一个线性表，但是其中的元素不是紧密排列的，而是可能存在空隙。
散列表（Hash table，也叫哈希表），是根据关键码值（Key value）而直接进行访问的数据结构。
也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
这个映射函数叫做散列函数，存放记录的数组叫做散列表。
比如我们存储70个元素，但我们可能为这70个元素申请了100个元素的空间。
70/100=0.7，这个数字称为负载因子。
我们之所以这样做，也是为了“快速存取”的目的。
我们基于一种结果尽可能随机平均分布的固定函数H为每个元素安排存储位置，这样就可以避免遍历性质的线性搜索，以达到快速存取。
但是由于此随机性，也必然导致一个问题就是冲突。
所谓冲突，即两个元素通过散列函数H得到的地址相同，那么这两个元素称为“同义词”。
这类似于70个人去一个有100个椅子的饭店吃饭。
散列函数的计算结果是一个存储单位地址，每个存储单位称为“桶”。
设一个散列表有m个桶，则散列函数的值域应为［0，m-1］。
标签:
