算法技术手册（原书第2 版）

搜索算法

｜

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 算法分析

只要散列函数能够相对均匀分布数据，那么散列搜索方法就可以表现出极为优秀的性能 ...