问题标签 [double-hashing]

为双散列表大小选择的最佳素数是什么？

侧面信息

• 哈希表是单词分析项目的一部分，马尔可夫模型，训练机器人来建模和生成文本，就好像其他人会写一样（这需要很多单词、句子、成绩单、书籍……语料库越大，更好的）
• 我不熟悉围绕素数的大部分数学，但我会阅读你们提出的所有建议，然后尝试从那里开始

我的想法是：

• 素数不应该太远/彼此接近---->我不必经常增加大小，但哈希表最终不会半空（更少的冲突，寻找理想的比例负载因子和哈希表大小）
• 最适合大型语料库 - 我不确定我必须选择的素数应该有多大，以前从未这样做过......
• 我还想过实现一个函数（不是哈希函数），它只是将哈希表的大小加倍，然后寻找最接近的素数 ------> 但它的运行时间为 O(n)因为素数只能被自身整除____（我必须检查直到当前哈希表大小的两倍的所有数字是否具有除零以外的余数，然后将大小加一/转到下一个奇数并再次测试整个循环）________ ------> 您可以想象这会非常慢，因此更好的方法是使用一组固定的素数，最多可达一百万（仅用于说明目的）左右，然后将它们用于任何尺寸更改

谢谢，任何其他问题表示赞赏

我正在尝试编辑我的哈希表以形成一个双哈希类，但似乎无法正确处理。

我想知道是否有人有任何见解。有人告诉我，我需要做的就是编辑 findPos()，现在我必须使用新策略提供新的探针。

**我做了一些研究，它说在双重探测中你会使用 R-(x mod R) 其中 R >size 和一个小于表格大小的素数。那么我要制作一个新的重新散列函数吗？

这是我的代码：

我知道在双重哈希中，

h1表示从位置 h1(key) 开始，表示h2所采取的步长。

但我不知道如何解决探测序列。

例如，如果键是14.

你能解释一下为什么答案是3,10,6,2,9,5,1,8,4,0。

我正在阅读有关 HashTable 的内容，并找到了一个易于理解的好来源。

但是我对双散列函数感到困惑。这是双重哈希函数的详细信息。

双散列使用在发生冲突时将第二个散列函数应用于密钥的想法。第二个散列函数的结果将是要插入的碰撞点的位置数。

第二个功能有几个要求：

一个流行的第二个哈希函数是： Hash2(key) = R - (key % R) 其中 R 是一个小于表大小的素数。

这是双哈希函数的图像。

现在混乱开始了。正如他们在图像中所说的那样。49 应该在索引的7位置上。[9]那么实际位置将是[6]为什么他们将 49 放在[0]索引处？其他剩余整数也一样。

当没有空索引时会发生什么？

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

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

使用线性探测，我希望得到以下数组（如果我错了，请纠正我）：

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

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

我有两个问题：

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

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

我一直在尝试进行双重哈希，但是我对使用双重哈希函数 h' 时会发生什么感到困惑。

当第一个散列函数发生冲突时，是否会将辅助散列函数的值添加到第一个散列函数的值中？

我已经尝试了很多方法并且无法解决这个问题，有问题的问题是以下链接中的图像：

http://postimg.org/image/k6ko6e0gp/

双重哈希如何解决这个问题？数组中已经有 3 个元素，还需要插入 3 个元素

在 Cormen 的“算法简介”一书中，我读到双散列（在开放寻址中）函数的形式为：

其中k是键，i是冲突情况下的下一个索引，m是表长度，hX是哈希函数。

他说双重哈希的主要问题是利用表中的所有索引。为了解决这个问题，我们应该将m设置为 2 的幂，并且h2函数应该返回奇数值。为什么（我看不到他解释）？

当提供第二个碰撞案例时，如何解决？

IE：

假设我们有一个数字数组：

[22、1、13、11、24、-1、-1、-1、-1、-1、-1]

其中 -1 表示数组中为空......

如果我们尝试使用插入 33

传入 33 将给出 2，其中数组位置 2 已被占用（有 13 个）。我们如何处理这种碰撞情况？我们是否再次将返回的 mod 值传递给 h2 ？我们替换值@那个数组值吗？（我怀疑后者并非如此。）

编辑：在 h2 中添加了括号

我在这里有一个关于双散列的作业，我总结了一点：

我有数组：17, 6, 5, 8, 11, 28, 14, 15 h1(k) = k mod 11, h2(k) = 1 + (k mod 9), Size of hash table = 11 The double哈希函数：dh(k) = k mod 11 + (j + (k mod 9)。

现在我计算哈希值：

=> 这超出了我的指数范围，而且指数越高，它也会越高。如果我将第二个 HashFuncion 的加法更改为减法，那么 HashValues 将变为负数 - 这也不好。

我究竟做错了什么？

谢谢祖萨娜

I'm currently doing hashing in my class. I need to create a double hashing function which takes a list and uses double hashing and returns a new list.

I understand how a list uses double hashing but I have trouble writing down the code for it.

This is the double hashing function that I have learned in class. I just have trouble implementing it in the code.

This is my attempt so far:

I'm fairly sure this is close to being right but I'm just making a stupid mistake or something. I understand how double hashing works but this code above does not work.

The output for this should be:

but my output is:

The value 51 in index position is not being added.

Any help is appreciated. Thank you.