预计阅读本页时间：-
分析
基于散列的查找有着非常优秀的性能特征。我们将简略地分析一下。在散列表中查找一个元素可以分为如下几个部分：
·计算散列值。
·通过散列值索引到相应元素。
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
·如果有冲突，那么寻找到需要找的元素。
所有基于散列的查找算法都包含头两个部分；但是不同的变种处理冲突的策略是不同的。
计算散列值的开销必须限制在常数时间内。如果你思考一下本节的例子，计算散列值将会和字符串的长度成比例。对于任何有穷单词集合来说，都存在一个最长的字符串，长度为k。如果tk是计算最长字符串散列值的时间，那么它计算任何散列值需要≤tk的时间。计算散列值因此被认为是一个常数时间的操作。
算法的第二部分也是时间的操作。如果表存储在二级存储器，根据元素的位置以及在设备上定位元素所需要的时间可能会有相应的改进算法，不过这个也是常数时间的操作。如果我们能够证明计算的第三部分也是有着常数时间的上界，那么我们就能很容易地证明基于散列的查找是常数时间的性能。当我们使用链时，我们将会定义一个负载因子，α=n/b，b是散列表中桶的数量，n是存储在散列表中元素的数量。负载因子表示的是在单个链中的平均元素数量。
在链中寻找元素的最坏时间是O(n)，只有在所有的元素都被映射到表中同样的桶时。要查找的桶的平均数目是α。如果希望能够知道详细的分析，请参见（Cormen等，2001）的第11章。
表5-5比较了例5-8的代码，它们都使用JDK类java.util.Hashtable，只是大小有不同而已。对于标有p=1.0的测试来说，213 557个单词中的每一个都会被用来作为目标元素。对于标记为p=0.0的测试来说，每一个单词都会用*来替换最后一个字符，以确保目标元素不会在表中。注意到我们在两种情况下都使用同样多的查找单词，确保散列的开销是相同的。我们进行了100次实验，并且抛弃掉最好和最坏的结果。表5-5表明了剩余98次实验的平均值。表5-6是我们在对散列表相关数据做的统计。随着负载因子的降低，链表的平均元素数量也下降了，这直接改善了性能。
散列表的规模加倍时，寻找一个元素的时间却下降了，因为链表的长度变得更短，从实践中得知，在b=1 045 875时，没有链表包含超过5个元素。因为一个散列表能够变得足够大，使得每个链表都很短，所以其查找性能可以看做是O(1)。但是，即使是在（一直）有充足的内存以及优秀的散列函数来分布元素到散列表中时，这也是很少发生的情况。在b=1 045 875，并且采用例5-6中的散列函数时，213 557个单词中大约81%被映射到唯一的桶中。
表5-6中给出了随着b增长，散列表的实际负载因子。注意当b足够大时，只有一个元素的桶数目变得越来越多，而且链表的最大长度也在下降。你可以看到当散列表的规模变得足够大时，查找的性能就是O(1)。
已有的java.util.Hashtable类性能比我们的代码要优秀，但是随着散列表规模的增长，节省的时间越来越少。因为java.util.Hashtable对List类进行了优化，能够高效地管理元素链表。此外，当负载因子太高时，java.util.Hashtable自动地“重新散列”整个散列表；重散列策略将在接下来的“变种”一节中讨论。它将增加构造散列表的开销，但是改善了查找的性能。如果我们阻止使用“重散列”策略，那么java.util.Hashtable的查找性能将和我们的实现的性能差不多。表5-7给出了重散列的次数以及构造散列表的总时间的关系。我们从之前描述过的单词表中构造散列表，在进行了100次实验，抛弃最好和最坏的结果后，这个表是剩余98次实验结果的平均值。在构造散列表来改善性能时，这个类的设计者进行了一些额外的计算（做了一个很常见的权衡）。在表5-7的第3、5列，我们注意到当重散列发生时，有着很明显的性能开销。并且也发现最后两行没有进行重散列，所以在列3、5、7中的结果是差不多的。通过重新构建散列表，减少元素链表的平均长度，重散列的确改善了整体性能。
