103

5-7

5-7
：查找元素
public boolean search (V v){
int h = hashMethod.hash(v);
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

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.