搜索算法
103
搜索算法
将散列表建好后,在表中查找元素变得极为简单如例
5-7
代码所示。一旦散列函数
返回散列表的索引,我们需要检查相应的桶是否为空。如果为空,返回空,表示查找
的字符串不在集合中;否则,在相应的桶中遍历链表,以查找目标字符串。
5-7
:查找元素
public boolean search (V v){
int h = hashMethod.hash(v);
LinkedList<V> list = (LinkedList<V>) listTable[h];
if (list == null) { return false; }
return list.contains(v);
}
int hash(V v){
int h = v.hashCode();
if (h < 0) { h = 0 - h; }
return h % tableSize;
}
注意散列函数能够确保散列索引是在
[0,
tableSize
)
范围内的。如果在
String
类上使
hashCode
函数,设计散列函数时必须考虑到
hashCode
内部的整数计算可能会溢出从
而返回负数。这是必须要处理的情况,因为如果值是负数,那么取模运算也会返回负数
(-
5%3
Java
中等于-
2
),例 ,使
JDK
String
hashCode
函数,字符串
aaaaaa
返回值为-
1 425 372 064
5.3.4 算法分析
只要散列函数能够相对均匀分布数据,那散列搜索方法就可以表现出极为优秀的性能
散列搜索方法搜索元素的平均时间为常数,即为
O
(1)
整个搜索过程包括单次的查询
H
以及随后在发生冲突的短列表中进行的线性查询
。在散列表中查找元素可以包含以下
个部分:
计算散列值。
通过散列值索引到相应元素集合。
如果有冲突,那么继续寻找,直找到所需元素。
所有
散列搜索
算法实现都包含前两个部分,但是不同的实现处理冲突的策略不相同。
计算散列值的费用必须限制在某个常数上界内。在本节的例子中,散列值的计算时间将
会和字符串的长度成正比。对于任何有穷单词集合来说,都存在一个最长的字符串,长
度为
k
。如果
T
k
是计算最长字符串散列值的时间,那么计算其他任何字符串的散列值只
需要
T
k
的时间。所以散列值的计算也可以被认为是一个常数时间的操作。
104
5
算法的第二步也应该是常数时间的操作。如果散列表存放在二级存储器,那么也有相
应的算法能够在二级存储器上定位元素,即便有寻址的费用,我们也可以认为该操作的
上界是常数时间。
如果能够证明算法的第三步也是有着常数时间的上界,那么就可以很容易地证明整个
列搜索
性能是常数时间。当使用链表来实现时,我们可以定义一个
负载因子
α
=
n/b
其中
b
是散列表中桶的数量,
n
是存储在散列表中元素的数量。负载因子表示的是在单
个链表中的平均元素数量。表
5-5
中给出了不同
b
值下散列表的实际负载因子。注意
b
不断增加时,链表的最大长度也在下降
b
足够大时,只有一个元素的桶数目变
得越来越多。在最后一行,
81%
的元素被映射到只有它们自己的桶中,而且每个桶的平
均元素数量降到了只有个位数。无论初始数据的规模多大,我们都可以选择一个足够大
b
,来保证每个桶只包含很少的元素。也就是说,在散列表中搜索元素的费用其实与
初始数据的规模并无关系,这种费用其实只是一个固定的值,我们可以推导出散列搜索
其实均摊性能为
O
(1)
5
-
5
:示例代码所创建的散列表的统计数据
b
负载因子
α
链表最小长度 链表最大长度 不同数量桶的数目
4,095 52.15 27 82 0
8,191 26.07 9 46 0
16,383 13.04 2 28 0
32,767 6.52 0 19 349
65,535 3.26 0 13 8,190
131,071 1.63 0 10 41,858
262,143 0.815 0 7 94,319
524,287 0.41 0 7 142,530
1,048,575 0.20 0 5 173,912
5-6
比较了例
5-7
的代码使用
JDK
java.util.Hashtable
创建的不同规模的散列
表的性能。对于标有
p
= 1.0
的测试来说,
213 557
个单词中的每一个都会被用来作为目
标元素。对于标记为
p
= 0.0
的测试来说,每一个单词都会用
*
来替换最后一个字符,
以确保目标元素不会在表中。我们在两种情况下都进行了同样多次数的搜索,以确保花
费在计算散列值的费用大致相等。
我们进行了
100
次实验,并且抛弃最好和最坏的结果。表
5-6
的结果便是剩余
98
次实验
的平均值。可以参见表
5-5
来更好地了解结果。
搜索算法
105
搜索算法
5
-
6
:不同的散列表规模下,查找需要花费的时间
b
/
5
-
7
中的散列表 默认容量的 java.util.Hashtable
p
= 1.0
p
= 0.0
p
= 1.0
p
= 0.0
4,095 200.53s 373.24s 82.11s 38.37s
8,191 140.47s 234.68s 71.45s 28.44s
16,383 109.61s 160.48s 70.64s 28.66s
32,767 91.56s 112.89s 71.15s 28.33s
65,535 80.96s 84.38s 70.36s 28.33s
131,071 75.47s 60.17s 71.24s 28.28s
262,143 74.09s 43.18s 70.06s 28.43s
524,287 75.00s 33.05s 69.33s 28.26s
1,048,575 76.68s 29.02s 72.24s 27.37s
随着负载因子的减少,每个元素链接表的平均长度将缩短,进而使得性能得到提升。
实践中得知,在
b
= 1 045 875
时,
所有链表所包含的元素均不多于
5
个。一个散列表在
有足够多的桶的情况下,每个链表的长度都将会很短,所以可以把查找性能看
O
(1)
但是,并不是所有时候我们都能有充足的内存以及优秀的散列函数来均匀分布元素到散
列表中。
Java
自带的
java.util.Hashtable
类性能比起我们的实现要更为优秀,但随着散列表规
模的增长,两者之间的性能差异将会越来越小。
java.util.Hashtable
要优化链表,
从而更高效地管理元素。不仅如此,当负载因子过大时
java.util.Hashtable
自动
地“重新构建”整个散列表;散列重构策略将在接下来的“衍生算法”一节中讨论。这
个策略将增加构造散列表的费用却能改善查找的性能。如果停止使用“散列重构”策略,
那么
java.util.Hashtable
查找性能将和上述实现的性能差不多。
5-7
给出了构造散列表时重构的次数以及所需要的总时间(单位是
ms
的关系。我们
用之前使用的单词表构造散列表,在进行了
100
次实验抛弃最好和最坏的结果后,给
出了剩余
98
次实验结果的平均值。
Java.util.Hashtable
类会在构建散列表时做一些额
外的计算以改善性能。在表
5-7
的第
3
5
列,我们注意到当散列重构发生时,额外的性
费用非常明显,并且也发现由于最后两行没有进行散列重构,因此
3
5
7
中的结
果几乎相同。散列重构通过重新构建散列表,减少元素链表的平均长度,的确显著地改
善了整体性能。

Get 算法技术手册(原书第2 版) now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.