我被要求使用数组实现哈希映射。我需要插入以下键:
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?
我最初是否使用原始哈希函数,如果给定索引是空闲的,则在其中插入元素,否则如果发生冲突,使用第二个哈希函数并在那里插入元素?