hash

Hash （哈希，或者散列）函数在计算机领域，尤其是数据快速查找领域，加密领域用的极广。

其作用是将一个大的数据集映射到一个小的数据集上面（这些小的数据集叫做哈希值，或者散列值）。

一个应用是Hash table（散列表，也叫哈希表），是根据哈希值 (Key value) 而直接进行访问的数据结构。
也就是说，它通过把哈希值映射到表中一个位置来访问记录，以加快查找的速度。下面是一个典型的 hash 函数 / 表示意图：

哈希函数有以下两个特点：

如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。
散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的。
但也可能不同，这种情况称为 “散列碰撞”（或者 “散列冲突”）。上图中，John Smith和Sandra Dee就存在hash冲突。

Hash一个应用就是对数据集分类，比如上图，Hash值为0的表示可能在A集合中，Hash值为2的表示B集合中，依次类推，
值为15的表示F集合中。但Hash冲突会在这里会导致严重的问题，对于一个未知的新值，其可能不属于上面任何一个集合，
但由于冲突，其Hash值和上面的某一个相同，导致误报（因为事先我们不可能做一个含有无限多项输入的完整的Hash表，
也就是原来的Hash函数不可能是完美的）。并且，hash冲突也会导致查找效率低下。

缺点： 引用吴军博士的《数学之美》中所言，哈希表的空间效率还是不够高。
如果用哈希表存储一亿个垃圾邮件地址，每个email地址 对应 8bytes, 而哈希表的存储效率一般只有50%，
因此一个email地址需要占用16bytes，一亿个email地址占用1.6GB，如果存储几十亿个email address则需要上百GB的内存。
除非是超级计算机，一般的服务器是无法存储的。

References:
[1] Hash_function
[2] 散列函数
[3] hash-and-bloom-filter
[4] 布隆过滤器 – 空间效率很高的数据结构