哈希表hashTable：哈希表hashTable是一种通过哈希函数，将特定的键映射到特定值的一种数据结构，它维护键和值之间一一对应关系。

    对于高级语言内核来讲，哈希表hashTable绝对是数据结构中的关键，很多高级语言是显示的支持哈希表hashTable的，哈希表hashTable的实践应用也非常广泛，编译器会维护一个符号表来保存标记，提供增删改查等操作。

    设计合理的哈希表hashTable的时间复杂度是O(1)，而最最糟糕的哈希表hashTable时间复杂度为O(n)，通常，它总是O(1)。而O(n)是因为，哈希表hashTable变成了一个链表。

    名词解释：

    1、键：操作数据的标识，例如PHP数组中的索引。

    2、槽：用于保存数据的坑。

    3、哈希映射函数：将键映射到数据应该存放的槽所在位置的函数。

    4、哈希冲突：哈希函数将两个不同的键映射到同一个索引的情况。

    哈希表hashTable可以理解为关联数组，数组使用键来寻址，如果键的范围较小且是数字的话， 我们可以直接使用数组来完成哈希表hashTable，而如果关键字范围太大，如果直接使用数组我们需要为所有可能的键申请空间。 很多情况下这是不现实的。即使空间足够，空间利用率也会很低，这并不理想。同时键也可能并不是数字， 在PHP中尤为如此，所以人们使用一种映射函数(哈希函数)来将键映射到特定的域中。

    通过合理设计的哈希函数，我们就能将键映射到合适的范围，因为我们的键空间可以很大(例如字符串键)， 在映射到一个较小的空间中时可能会出现两个不同的键映射被到同一个index上的情况， 这就是我们所说的出现了冲突。 目前解决哈希表hashTable冲突的方法主要有两种：链接法和开放寻址法。目前PHP中哈希冲突解决方法就是链接法。

    冲突解决 - 连接法：

    链接法通过使用一个链表来保存槽值的方式来解决冲突，也就是当不同的键映射到一个槽中的时候使用链表来保存这些值。 所以使用链接法是在最坏的情况下，也就是所有的键都映射到同一个槽中了，这样哈希表hashTable就退化成了一个链表， 这样的话操作链表的时间复杂度则成了O(n)，这样哈希表hashTable的性能优势就没有了， 所以选择一个合适的哈希函数是最为关键的。由于目前大部分的编程语言的哈希表hashTable实现都是开源的，大部分语言的哈希算法都是公开的算法， 虽然目前的哈希算法都能良好的将键进行比较均匀的分布，而这个假使的前提是键是随机的，正是由于算法的确定性， 这就导致了别有用心的黑客能利用已知算法的可确定性来构造一些特殊的键，让这些键都映射到 同一个槽位导致哈希表hashTable退化成单链表，导致程序的性能急剧下降，从而造成一些应用的吞吐能力急剧下降， 尤其是对于高并发的应用影响很大，通过大量类似的请求可以让服务器遭受DoS(服务拒绝攻击)， 这个问题一直就存在着，只是最近才被各个语言重视起来。哈希冲突攻击利用的哈希表hashTable最根本的弱点是：开源算法和哈希实现的确定性以及可预测性， 这样攻击者才可以利用特殊构造的键来进行攻击。要解决这个问题的方法则是让攻击者无法轻易构造 能够进行攻击的键序列。PHP采用的是一种治标不治本的做法: 限制用户提交数据字段数量。这样可以避免大部分的攻击，不过应用程序通常会有很多的数据输入方式，比如，SOAP，REST等等， 比如很多应用都会接受用户传入的JSON字符串，在执行json_decode()的时候也可能会遭受攻击。 所以最根本的解决方法是让哈希表hashTable的碰撞键序列无法轻易的构造，目前PHP中还没有引入不增加额外的复杂性情况下的完美解决方案。

    冲突解决 - 开放寻址法：

    通常还有另外一种解决冲突的方法：开放寻址法。使用开放寻址法是槽本身直接存放数据， 在插入数据时如果键所映射到的索引已经有数据了，这说明发生了冲突，这是会寻找下一个槽， 如果该槽也被占用了则继续寻找下一个槽，直到寻找到没有被占用的槽，在查找时也使用同样的策略来进行。由于开放寻址法处理冲突的时候占用的是其他槽位的空间,这可能会导致后续的键在插入的时候更加容易出现 哈希冲突，所以采用开放寻址法的哈希表hashTable的装载因子不能太高，否则容易出现性能下降。

相关内容：用PHP的实现一个高效的数据库（文件存储，NOSQL）  使用哈希表来构建自己的数据库 

一、我是新手我怕谁

    新手程序猿通常会直接存储明文密码在数据库中，好一点的会使用MD5来加密密码后存储md5(password)，再好一点的会sha1加密密码后存储sha1(password)。将常用的组合哈希后存入数据库，用来爆库，这个就是所谓的彩虹表。

二、加盐salted

    在密码中加入随机数字或字符，然后再进行哈希，看起来叼了很多，但是实际上对于现在计算机来说，即使简单的使用了盐和哈希的加密，短密码仍然会在非常短的情况下就会被破解出来。

三、美国标准

    美国政府的标准，已经用于政府和军方的系统。PBKDF2加密算法，全程是Password-Based Key Derivation Function。

    PBKDF2加密算法就是牺牲了时间来换取安全，一个明文的密码+随机的盐，然后哈希散列加密后存储起来，这是我们前面说的（二、加盐salted）。把这个过程重复100次，得到的结果存储起来。

    请注意，尽管我们说牺牲了时间，又说到了重复100次，那也是很快的，因为我们的普通服务器单次的运算都是在毫秒级。

四、scrypt

    scrypt是由著名的FreeBSD黑客 Colin Percival为他的备份服务 Tarsnap开发的。scrypt不仅计算所需时间长，而且占用的内存也多，使得并行计算多个摘要异常困难，因此利用彩虹表进行暴力攻击更加困难。scrypt没有在生产环境中大规模应用，并且缺乏仔细的审察和广泛的函数库支持。但是，scrypt在算法层面只要没有破绽，它的安全性应该高于PBKDF2。

五、请使用bcrypt！请使用bcrypt！请使用bcrypt！

    bcrypt是跨平台的、专门为密码存储而设计的算法，bcrypt所接受的密码长度必须是8至56个字符，并将在内部被转化为448位的密钥。基于Blowfish加密算法变形而来。

    bcrypt在默认情况下，在删除数据之前将使用随机数据三次覆盖原始输入文件，以阻挠可能会获得数据的人恢复数据的尝试。如果您不想使用此功能，可设定禁用此功能

　 　bcrypt最大的好处是有一个参数，可用于调整计算强度，而且该参数是包括在输出的摘要中的。随着计算能力的提高，应该可以逐步增大这个参数，增大这个参数后并不会影响原来的用户。

 　　bcrypt经过了很多安全专家的仔细分析，使用在以安全著称的OpenBSD中，一般认为它比PBKDF2更能承受随着计算能力加强而带来的风险。