Skip to Main Content
算法技术手册(原书第2 版)
book

算法技术手册(原书第2 版)

by George T.Heineman, Gary Pollice, Stanley Selkow
August 2017
Intermediate to advanced content levelIntermediate to advanced
360 pages
8h 35m
Chinese
China Machine Press
Content preview from 算法技术手册(原书第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 算法分析
只要散列函数能够相对均匀分布数据,那么散列搜索方法就可以表现出极为优秀的性能 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

Aurélien Géron
Go语言编程

Go语言编程

威廉·肯尼迪
C++语言导学(原书第2版)

C++语言导学(原书第2版)

本贾尼 斯特劳斯特鲁普

Publisher Resources

ISBN: 9787111562221