问题标签 [universal-hashing]

我们有 n 个元素，m=2n 和 k，其中 K 是散列函数的数量，m 是位数组的大小，n 是元素的数量。k 的值是多少，使得得到误报的概率最多为 1/n

我正在努力寻找找到 k 值的概率，使得误报概率最多为 1/n。到目前为止，我所做的如下。

Pr(位 = 0) = 1-1/m == e^(-kn/m)

然后：

Pr(bit = 1) = (1-e^(-kn/m))^k

现在我被困在这一点上，我无法获得我最多误报概率为 1/n 的 k 值。

如果有人认为我到目前为止所做的事情是错误的，请告诉我。

我想将一些数据保存在 .cvs 之类的文件中。条件之一是数据写入文件后不能更改。如果我想读取数据，应该保存数据在过去没有改变，如果数据在过去被其他人改变，我想得到一个警报。

例如，我的 .csv 中的一行如下所示：

我怎样才能检查，那条线被别人改变了？
我怎样才能锁定，没有人改变我的线路之一？

我希望你知道我的意思。如果在这个主题的上下文中使用 google-search，我会经常遇到“哈希我的数据”这个主题。

它是如何工作的？

我在理解 Java 中通用哈希函数的实现时遇到了一些麻烦。哈希函数(ax + b) mod p应该在 H_1 的基础上实现。这个实现也应该适用于字符串。

我最近在做这个：

这个实现是正确的，还是我在为 String 实现通用散列函数的路径上完全错误。

谢谢你帮我解决这个问题

我希望创建一个易于记忆的散列，例如 3 个随机单词（what3words），所以我的想法是散列一个 java 对象，结果是三个随机单词。

用例：我有很多字段的对象，我需要将字段压缩为 24 个字符（这是存储这些对象的数据库中 varchar 主键列的大小，不能更改），生成的压缩值应该也很容易被记住。

最初，我决定使用 3 个不同的散列函数（即 FNV1a64Hash、CRC32Hash 和 DJB2）来创建 3 个预散列，然后将这些值用作字典中的索引，但这导致了很多冲突（Random Words tried: 10000000 No of collisions: 9272419）。请注意，我的字典大小约为 50k 个单词。

接下来，我决定只调用hashCode()对象，然后填充结果 int，最后将其拆分为 3 个 5 位数字的块，不幸的是又发生了很多冲突（Random Words tried: 10000000 No of collisions: 9999900）。我认为这部分可能归结为 int 的最大大小为 2^31，这只是一个 10 位数字，因此第一个索引始终为 00000。

我也使用了通用散列，但我再次遇到了相当多的冲突（Random Words tried: 10000000 No of collisions: 9996436）

我想知道我是否在这里遗漏了一些明显的东西，或者是否有人知道任何可以在这里提供帮助的知名算法？提前为菜鸟问题道歉，这是我第一次遇到散列，还有很多东西要学。

我在下面粘贴了我的代码和测试代码，以防有明显问题。

测试代码：