问题标签 [universal-hashing]

我需要对长度为n^2的数字序列S进行哈希处理，其中每个数字是两个数字的总和，每个数字都是其中一个序列上的一个元素：.{x_1,..., x_n},{y_1,..., y_n}

我正在使用通用散列，所以问题是如果 S 的成员有无限多的可能性，我如何找到键 U 的宇宙。

If my intention is only to have a good hash function that spreads data evenly into all of the buckets, then I need not come up with a family of hash functions, I could just do with one good hash function, is that correct?

The purpose of having a family of hash functions is only to make it harder for the enemy to build a pathological data set as when we pick a hash function randomly, he/she has no information about which hash function is employed. Is my understanding right?

EDIT: Since someone is trying to close as unclear; This question is to know the real purpose of employing a Universal family of hash functions.

我正在使用 Electron，使用 JS 和 HTML 5 构建的 Githubs 桌面框架。我需要检查 fileA 是否与 fileB 不同，并且类似地使用 2 个字符串。

这些文件和字符串可以大小相同但不同。它们可能很小（2-3 字节）或很大（2-3 兆字节）。

该应用程序的性质意味着我需要每半秒左右检查一次（我对轮询时间有一些余地）。

此数据存储在本地数据库中，类似于 sqlite。我可以完全控制这个数据库中的内容。我最初的想法是在数据库中创建和存储每个文件/字符串的 MD5 哈希以及文件/字符串的 mime 类型和大小。这样我可以检查大小的差异，如果大小相同，则回退到 mime 类型，如果大小相同，则返回 md5。

我的问题是轮询频率。简而言之，我正在获取剪贴板内容并根据数据库检查它，因此需要在每次轮询时计算大小、mime 类型和 md5 哈希值。Mime 类型和大小应该没问题，但 md5ing 8MB 图像可能会变慢。

还有另一种我应该注意的方法吗？

谢谢

如果您不熟悉通用散列，它主要是尝试使用一些涉及随机性的相当简单的数学来保证少量的冲突（相反，例如使用普通的旧模数）。问题是它对我不起作用：

我首先测试模散列并确定最长的链长（链长表示散列桶大小）：

我选择了一个导致一个非常大的链的输入（id est 一个使用普通模数表现不佳的输入）并将这个与通用散列相结合。通用散列使用随机性，因此我可以采用恒定输入并仍然得到不同的结果。

问题来了。我尝试了 100 个大小为 128 的随机输入数组，并计算平均最长链和总最长链，但两种算法的性能相似。

您可以在我的repo中查看我的 main 。

我的问题是：这个结果可以预期吗？对于使用模数已经表现不佳的输入，通用散列是否表现得更好？还是我只是搞砸了我的实施（更有可能）。

提前非常感谢！

我花了几天时间试图让图书馆在我的系统上工作。该库有几种生成 MPHF 的算法。我对最小散列函数的理解是，当我使用 MPHF 散列两个不同的键时，它们将返回两个不同的 id。我生成的 200 万个键似乎不是这种情况（整数，由算法读取为字符串）。我已经尝试了该库实现的几种算法，但所有这些算法都会导致很多键出现重复的“ID”。

这是我写的：

如果算法声称生成最小完美散列函数，那么每个不同键的 ID 不应该是唯一的吗？有 2048383 个键。对于我的项目，我需要将 id 从 0 映射到 2048382，因为我计划使用最小的完美哈希函数。我不确定我的理解哪里出了问题。请帮忙。

我目前正在使用通用散列（矩阵散列）在 C++ 中实现 HashTable。我实现矩阵的方法是制作一个指针数组（它们只是随机位，它们不能作为指针“工作”，而是作为 32x64 位矩阵）。为了对键进行散列，我将指针键与矩阵相乘（使用位运算），从而形成一个 32 位列（我们的散列键）。这就提出了一个大问题：

是否可以使用一个类（更准确地说，一个 C++ 字符串）来填充随机位并进行位操作？我不在乎字符串中的数据是不是纯垃圾，我只是用它来散列。或者，作为替代方案，我怎样才能创建一个 32 字节的类型并将一个字符串转换为一个？

我正在寻找一种快速简便的方法来在我的 Java 项目中使用（通用）成对独立哈希函数系列。

理想情况下，我会有一些对象UniversalFamily（代表家庭），它会用一个hash()散列整数的方法返回我的对象​​。

示例用法：

在我开始修补之前，是否已经有类似的东西可用？

我不想生成令牌来验证用户的电子邮件，我了解了通用hashing（从一系列哈希函数中随机选择一个哈希函数）并且我在PHP

它是生成令牌的安全方法吗？

在这个问题中，我得到了以下映射

由此，必须导出一个显式的通用散列函数，并暗示这可以通过一组 4 个函数来完成。不幸的是，尽管搜索了有关如何执行此操作的文章，但我仍然感到困惑。非常感谢任何有助于理解如何找到此散列函数并朝着正确方向前进的帮助！

编辑：

经过一番深思熟虑，这就是我想出的；这是正确的吗？

我试图了解通用散列相对于普通散列的有用性，除了函数每次随机生成，阅读 Cormen 的书。

根据我对通用散列的理解，我们选择要使用的函数

其中 p 是大于所有键的素数，m 是数据表的大小，a,b 是随机数。

因此，例如，如果我想读取 80 个人的 ID，并且每个 ID 的值介于 [0,200] 之间，那么 m 将是 80，p 将是 211（下一个素数）。对？我可以使用该功能让我们说

但为什么这会有所帮助？我很有可能最终会有很多空位，无缘无故地占用空间。降低数字 m 以获得更小的表不是更有用，这样空间就不会无缘无故地使用吗？

任何帮助表示赞赏