问题标签 [universal-hashing]

我被告知Hashtable在.NET使用重新散列以减少/避免碰撞。

IE。“重新哈希的工作方式如下：假设我们有一组不同的哈希函数，H1 ... Hn，并且在从哈希表中插入或检索项目时，最初使用 H1 哈希函数。如果这导致冲突，则尝试 H2 并向前直到 Hn 以避免 Hashtable 中的冲突。”</p>

假设：我们有一个带有 n（其中 n < Infinity）元素的哈希表，其中渐近时间复杂度为 o(1)；我们（CLR）在应用一些散列函数（Hn-1 散列函数，其中 n>1）时实现了这一点。

问题：当我们寻找（检索）任何元素（如果使用不同的散列函数）时，谁能解释一下 CLR 如何将 Key 映射到散列码？CLR 如何跟踪（如果有）任何活动对象（哈希表）的哈希函数？

提前致谢

嗨，我正在阅读关于 CLRS 上的通用散列的章节。

在第 234 页

推论 11.4

通过在具有 m 个槽的表中链接使用通用散列和冲突解决方案，需要预期时间 Theta(n) 来处理包含 O(m) 个 INSERT 操作的 n 个 INSERT、SEARCH 和 DELETE 操作序列。

我有点明白这个想法，但我很难理解这个英文句子。结尾“包含 O (m) INSERT 操作”是什么意思？

这是否意味着已经执行了 n = O(m) 插入。然后，....我不知道。我无法解析这句话。第一次插入和第二次插入有什么区别？

我想听听你的意见。

谢谢！

据我目前的理解，通用散列是一种在运行时随机选择散列函数以保证任何类型输入的合理性能的方法。

我知道我们可能会这样做，以防止有人故意选择恶意输入进行操纵（知道确定性哈希函数的可能性）。

我的问题如下：这不是真的吗，我们仍然需要保证每次散列时都会将密钥映射到相同的地址？例如，如果我们想检索信息，但哈希函数是随机选择的，我们如何保证我们可以取回我们的数据？

我知道我可以散列奇异值作为dict. 例如，我可以将哈希5作为dict.

我目前面临一个问题，需要我对一系列值进行散列。

基本上，我需要一种更快的方法来做到这一点：

其中x是一些float任意精度的参数。

我能想到的最快方法是散列，但问题是：我可以(0.1, 0.2)用作密钥，但这仍然会花费我 O(n) 运行时间，并且最终不会比elifs 的转换好（我必须遍历键并检查是否key[0] <= x <= key[1]）。

有没有办法散列一系列值，以便我可以检查散列表0.15并仍然得到#execute B？

如果这样的散列是不可能的，我还能如何改进它的运行时间？我正在处理足够大的数据集，线性运行时间不够快。

编辑：为了回应奇恩的回答，我必须注意不能假设间隔是规则的。事实上，我几乎可以保证他们不是

为了回应评论中的请求，我应该提到我这样做是为了在遗传算法中实现基于适应度的选择。算法本身是做功课的，但具体实现只是为了提高生成实验数据的运行时间。

我使用布隆过滤器模拟集合交集近似。我尝试了很多简单的散列函数来将值散列到过滤器。但它不擅长避免碰撞。所以有人建议了一个通用的哈希函数。但我不确定它是如何工作的。我的程序旨在仅将密钥传递给散列函数，散列函数返回散列。谁能帮我写代码？谢谢

如何计算插入 2 个元素后没有碰撞的概率。答案是 4/9，但我看不出它是 4/9

我正在实现通用散列并使用以下通用散列函数：

h(k)=((A*k)mod 2^64) rsh 64-r

其中 A 是之间的随机数

2^61 和 2^62。

C++中的rand()函数具有返回类型整数，它不能生成那么大的数字。那么如何在这个范围内生成随机数呢？（数字应该是非常随机的，即每个数字应该有相同的概率被选中）

笔记：

不起作用，因为返回的数字rand是int。

我试图了解通用散列是如何工作的。它被定义h(x) = [(a*x + b) mod p] mod m在哪里a,b- 随机数，m- 哈希表的大小，x- 键和p- 素数。例如，我有几个不同的键：

为了创建一个通用哈希函数，我必须遵循：

但可能每次我都会得到 0 到 99 范围内的数字，并且可能会有很多碰撞。

所以我的问题是：我正确理解并应用了通用哈希？

我正在阅读这个与通用散列相关的视频讲座。它显示了散列 IP 地址的示例。每个 IP 地址由 4 个 32 位整数 (x1,x2,x3,x4) 组成，其中任何 xi 的最大值为 255。

教程说哈希表的大小应该大于 255 或任何 xis。为什么会这样？

我所知道的是：

• 一致性哈希：统一的分布式存储系统
• 锥形哈希：非均匀分布式存储系统

我想知道：

• 这个怎么运作？
• 它有什么用？
• 这两种散列有什么区别？

我无法理解这两者之间的区别。请有人帮我解决这个问题！