编辑“哈希（Hash）”（章节）

=== 哈希表 ===
哈希表是哈希函数的一个主要应用，使用哈希表能够快速的按照''关键字''查找数据记录。（注意：关键字不是像在加密中所使用的那样是秘密的，但它们都是用来“解锁”或者访问数据的。）例如，在英语字典中的关键字是英文单词，和它们相关的记录包含这些单词的定义。在这种情况下，哈希函数必须把按照字母顺序排列的字符串映射到为哈希表的内部数组所建立的索引上。

哈希表哈希函数的几乎不可能/不切实际的理想是把每个关键字映射到唯一的索引上（参考完美哈希），因为这样能够保证直接访问表中的每一个数据。

一个好的哈希函数（包括大多数加密哈希函数）具有均匀的真正随机输出，因而平均只需要一两次探测（依赖于装填因子）就能找到目标。同样重要的是，随机哈希函数不太会出现非常高的冲突率。但是，少量的可以估计的冲突在实际状况下是不可避免的（参考生日悖论或鸽洞原理）。

* '''链式哈希'''：每个槽是一个链表或链的头部，碰撞的项会被添加到链中。链表可以保持随机顺序并线性搜索，或按顺序排列，或者按访问频率自排序以加速访问。
* '''开放地址哈希'''：从已占用的槽开始以指定方式探测表，通常采用线性探测、二次探测或双重哈希，直到找到一个空槽或探测完整个表（溢出）。搜索数据项时遵循相同的程序，直到找到目标项、找到空槽或探测完整个表（数据项不在表中）。

在很多情况下，heuristic哈希函数所产生的冲突比随机哈希函数少的多。Heuristic函数利用了相似关键字的相似性。例如，可以设计一个heuristic函数使得像<code>FILE0000.CHK</code>, <code>FILE0001.CHK</code>, <code>FILE0002.CHK</code>，等等这样的文件名映射到表的连续指针上，也就是说这样的序列不会发生冲突。相比之下，对于一组好的关键字性能出色的随机哈希函数，对于一组坏的关键字经常性能很差，这种坏的关键字会自然产生而不仅仅在攻击中才出现。性能不佳的哈希函数表意味着查找操作会退化为费时的线性搜索。