
106
|
第
5
章
表
5
-
7
:构建散列表的时间比较
b
/ 个 我们的 JDK 散列表(
α
=
0
.
75
) JDK 散列表(
α
=
4
.
0
) JDK 散列表
散列表 (
α
=n/b)
构造时间
/s
构造时间
/s #
重散列
构造时间
/s #
重散列
构造时间
/s
次数
/s
次数
/s
4,095 403.61 42.44 7 35.30 4 104.41
8,191 222.39 41.96 6 35.49 3 70.74
16,383 135.26 41.99 5 34.90 2 50.90
32,767 92.80 41.28 4 33.62 1 36.34
65,535 66.74 41.34 3 29.16 0 28.82
131,071 47.53 39.61 2 23.60 0 22.91
262,143 36.27 36.06 1 21.14 0 21.06
524,287 31.60 21.37 0 22.51 0 22.37
1,048,575 31.67 25.46 0 26.91 0 27.12
5.3.5 衍生算法
散列搜索
的一个主要衍生算法是通过限制每个桶只包含单个元素来改进了处理冲突。与
其在桶中放入只有一个元素的链表,我们转而使用一种名为
开放定址
的技术,这种技术
直接将冲突元素存储在
散列表
H
的其他空桶中
,如图
5-2
所示。散列表在使用了开放定
址技术之后,完全没有使用链表,从而成功地减少了存储费用 ...