预计阅读本页时间：-
基于散列的查找
前面讨论的查找算法在处理小数据量（顺序查找）或者有序的数据集合（二分查找）时才使用。我们需要更加强大的算法能够查找较大的集合，而且并不需要有序。最常使用的一个方法是使用散列函数来将目标元素的一个或者多个特征转换成一个值，这个值用来索引一个已经索引的散列表。基于散列的查找有着比本章描述的其他算法在平均情况下更好的性能。很多算法的书籍都是在讨论散列表时才介绍基于散列的查找，你也能够在数据结构的书籍中讨论散列表的章节中找到这个算法。
在一个基于散列的查找（图5-3），集合C的n个元素首先会加载到一个有着b个桶的散列表A中。键值的概念使得这个操作可行。对于每个元素e∈C来说，它能够通过k=key(e)映射到一个值k，如果ei=ej，那么key(ei)=key(ej)[1]。一个散列函数h=hash(e)使用了键值key(e)来将e插入到桶A[h]中。一旦散列表A被构造好了，那么查找一个元素t也被转换成在桶A[h]中寻找一个元素t，h=hash(t)。
图5-4用一个小小的例子表示了基于散列查找的一般模式。基于散列的查找包括：
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
·可能键值的全集U。每一个元素e∈C将映射到一个键值k∈U。
·散列表A存储着原始集合C的n个元素。A也许包含着元素本身或者也包含了元素的键值。在A中有b个位置。
·散列函数hash，使用key(e)计算一个整数索引h。
当实现基于散列的查找时，有两个需要注意的地方：散列函数的设计以及如何处理冲突（当两个键值映射到A的同一个桶）。对于b＜＜|U|，几乎在所有的情况下，冲突都会发生。注意，如果b＜n，那么A中没有足够的空间存储原始集合的n个元素。当这种情况出现时，通常的做法是在A中每一个桶中都存储一个元素集合（一般使用链表实现），如图5-4中的“存储元素”和“存储值”的选项（注4）。
不适当的散列函数可能会导致一个不均匀的键值分布。这样会导致两个结果：散列表中的很多桶会是没有使用过的，浪费了空间，而使用的桶又会因为多个键值同时映射到了一个桶中，导致了大量的冲突，这样使得性能更加糟糕。
对于大多数输入来说，冲突都是可能存在的。期望的冲突数量增长时，处理冲突的策略对于算法的性能有着非常重要的作用。
输入/输出
寻找的目标元素t必须有一个或者多个特征能够用来作为键值，这些键值组成了全集U。不像二分查找，原始集合C不需要是有序的。事实上，即使C中的元素在某种程度上是有序的，散列方法在插入元素到散列表A时也不会尝试去保持其有序性。
基于散列的查找的输入是散列表A，以及寻找的目标元素t。如果t在A[h]的指向的链表中，算法返回真，这里h=hash(t)。如果A[h]是空或者不在A[h]指向的链表中，那么返回假表示t不在A中（也就是说也不在C中）。图5-3的伪代码是一个简化版，存储在A中的列表的元素本身就是键值。
假设
变量n是元素集合C中的元素数目，b表示索引集合A中的桶数目。
