0

我被要求使用数组实现哈希映射。我需要插入以下键:

15, 7, 26, 39, 11, 9, 27, 5, 18, 2, 54, 22, 4

使用哈希函数放入一个大小为 19 的数组:

(3x + 7) % 19

使用线性探测,我希望得到以下数组(如果我错了,请纠正我):

Index:    0    1    2    3    4    5    6    7    8    9    10   11   12   13   14   15   16   17   18
Key:      4         11   5    18                       7    26   39   27   2    15   9    22   54

其中 26 在索引 9 处与 7 发生冲突,因此在索引 10 处插入,然后 39 在索引 10 处与 26 发生冲突,因此在索引 11 处插入。

我现在尝试在 HashMap 的数组实现中插入相同的元素,使用双散列而不是线性探测。我得到的第二个哈希函数是:

11 - (x % 11)

我有两个问题:

这是否意味着我的数组大小为 11 或仍为 19?

我最初是否使用原始哈希函数,如果给定索引是空闲的,则在其中插入元素,否则如果发生冲突,使用第二个哈希函数并在那里插入元素?

4

1 回答 1

0

根据维基百科,二级散列函数间接用于探测函数:

h(0, x) = (3x + 7) % 19
h(j, x) =  ((3x + 7) + j(11 - (x % 11))) % 19

其中 j 是碰撞计数器。

于 2016-03-07T01:28:26.207 回答