适用范围

快速查找，删除的基本数据结构，通常需要总数据量可以放入内存

基本原理

　- hash函数选择，针对字符串，整数，排列，具体相应的hash方法。

• 碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法。

扩展

　　d-left hashing中 的 d 是多个的意思，我们先简化这个问题，看一看 2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做 T1 和 T2 ，给 T1 和 T2 分别配备一个哈希函数， h1 和 h2 。在存储一个新的key时，同时用两个哈希函数进行计算，得出两个地址 h1[key]和 h2[key]。这时需要检查 T1 中的 h1[key] 位置和 T2 中的 h2[key] 位置，哪一个位置已经存储的（有碰撞的）key比较多，然后 将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。 但是这种方法只能使用在静态集合上，一旦集合发生变化，就需要进行重新计算。

问题实例：

海量日志数据，提取出某日访问百度次数最多的那个IP。

答：IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将 ip 直接存入内存，然后进行统计。