问题标签 [fnv]

我正在尝试实现Fowler–Noll–Vo 哈希函数

伪代码看起来像这样

这是我的代码

现在我正在使用它

我在这里测试我的结果 ，我得到的结果是0d47307150c412cf

更新：

我将我的类型固定为

我得到的结果 fa365282a44c0ba7 仍然不匹配结果 0d47307150c412cf

关于如何解决此问题的任何建议

我被困在尝试使用 Cormen 的每个级别的通用散列来实现完美的散列技术。具体来说，使用压缩方法（至少，我认为这是我的问题）。

我正在研究字符串，我认为是短字符串（8 到 150 之间），为此，我使用 64 位密钥（对于那些像 spookyhash 这样的散列函数我得到的是较低的 64 位），问题是在 9 个存储桶中存在只有三个唯一字符串（10 个字符中的两个和 11 个字符中的一个）的冲突。

为此，我正在使用 Cormen 的哈希压缩方法：

h_ab(k) = ((ak+b)mod p) mod m

与a = 3，p = 4294967291（最大的 32 位素数），b = 5和m = 9（因为 m_j 应该是 n_j 的平方）。作为“k”，我使用的是散列函数返回的散列值（如杂音）。

例如，如果我使用像 murmur2（64 位版本）这样的哈希函数，p数应该是最大的 64 素数？这样一来，我就涵盖了所有可能的杂音可能返回的哈希值，对吗？

存在哪些其他哈希压缩技术（除除法之外），您推荐吗？

任何参考、提示、书籍、论文、帮助都非常受欢迎。抱歉这个愚蠢的问题，我是哈希函数和哈希表的新手。

提前致谢。

我正在尝试在 python-3.6 上使用 fnv 哈希函数，但出现错误

回溯（最后一次调用）：文件“C:/Users/SACHIN/AppData/Local/Programs/Python/Python36/bloom.py”，第 4 行，模块 fnv.hash(data, algorithm=fnv.fnv_1a, bits =64) 文件“C:\Users\SACHIN\AppData\Local\Programs\Python\Python36\lib\site-packages\fnv__init__.py”，第 52 行，哈希 OFFSET_BASIS[bits] 文件“C:\Users\SACHIN \AppData\Local\Programs\Python\Python36\lib\site-packages\fnv__init__.py"，第 28 行，在 fnv_1a 返回 ensure_bits_count((hash_value ^ byte) * PRIMES[bits], bits) TypeError: 不支持的操作数类型) for ^: 'int' 和 'str'

对于代码

这完全是从https://pypi.python.org/pypi/fnv/0.2.0复制的

请让我知道实际上出了什么问题。

我不明白为什么整数值“哈希”在 3 循环中/之后越来越低。

我猜这是因为 uint 限制是2,147,483,647. 但是...当我尝试逐步进行时，该值等于2146134658？。我数学不是很好，但应该低于限制。

如果您想知道这个 if 语句仅适用于我。

765010506是下一次循环运行后的哈希值。

我正在玩 FNV-1a 散列。我有一个非常简单的实现，它似乎对 32 位散列和 64 位散列非常有效：

对于 32 位散列，我使用了 uint（32 位整数）。对于 64 位哈希，我使用的是 ulong（64 位整数）。

现在，我想试试 128 位版本。但是，C# 没有 128 位整数类型。或者是吗？System.Guid的.NET 文档明确指出（在“备注”下）：

GUID 是一个 128 位整数（16 个字节），可用于所有计算机和网络

那么，为什么他们说它是一个 128 位整数呢？我可以对类型进行算术运算吗？我已经尝试过了，但我似乎无法为 System.Guid 类型分配一个数字（例如初始偏移量）。我不能说我很惊讶，但我想知道为什么这么清楚地说明这是一个“128 位整数”。

（原始问题的一种可能的解决方案显然是使用 System.Numerics.BigInteger 库。我在搜索过程中遇到了这个问题，并且想知道 MSDN 上的声明）。

我有两个 FnvHashMap，首先声明如下： FnvHashMap<(i32, i32), Employee> 第二个：FnvHashMap<(i32, i32), Employee> Employee 在哪里

我需要遍历“第一”FnvHashMap 并查看“第二”FnvHashMap 中是否有匹配的记录（emp_id 和 lang_id）
我可能不需要考虑 dept_id 和描述

提前致谢。

实现嵌套循环后的新代码

我是 Rust 新手，这是我遍历两个 FnvHashMap 并找到差异的代码

当我将这些值添加到另一个向量时，Rust 抛出编译错误

任何帮助将非常感激。谢谢

我有一些值存储为我想“解码”的 128 位 FNV-1a 哈希值。据我了解，虽然大多数散列是一种方式，但 FNV 不是加密散列。是否可以“解码”我自己创​​建的 FNV 哈希？我正在使用 golang，下面的示例哈希。

我正在尝试将意外噪声库从 C# 移植到 Lua。尝试移植 FNV-1A 算法时遇到问题。使用相同的输入值时，与素数相乘的结果不匹配。

首先，我想展示算法的 C# 代码：

这个函数在代码库的其他地方被这样调用（简化）：

我注意到sizeof(Int32)结果总是乘以Int32[]数组中的元素数。在这种情况下（在我的机器上）结果为 12，这导致 FNV32Buffer 函数中的缓冲区大小为 12 个字节的数组。

在 for 循环中，我们看到以下内容：

1. 执行按位异或运算hval
2. hval乘以一个素数

乘法运算的结果与我的 Lua 实现的结果不匹配。

我的 Lua 实现是这样的：

我没有在我的实现中提供缓冲区长度，因为 Lua 的位运算符总是在 32 位有符号整数上工作。

在我的实现中，我创建了一个字节数组，并为缓冲区表中的每个数字提取字节。在比较 C# 和 Lua 字节数组时，我得到的结果大多相似：

似乎由于字节顺序，字节顺序不同，但这我可以改变。我不相信这与我现在的问题有任何关系。

对于 C# 和 Lua 字节数组，我循环遍历每个字节并对每个字节执行 FNV-1A 算法。

当使用值{0, 0, 300}(x, y, seed) 作为 C# 和 Lua 函数的输入时，在 FNV 散列循环的第一次迭代完成后，我得到以下结果：

C#: 00000101_00001100_01011101_00011111(84696351)

卢阿：01111110_10111100_11101000_10111000（2126309560）

可以看出，在第一个散列循环之后的结果非常不同。从调试中我可以看到与素数相乘时数字会出现差异。我相信原因可能是 Lua 默认使用有符号数字，而 C# 实现适用于无符号整数。或者可能由于字节顺序的不同而导致结果不同？

我确实读过 Lua 在使用十六进制文字时使用无符号整数。由于FNV_32_PRIME是十六进制文字，我想它应该与 C# 实现相同，但最终结果不同。

如何确保 Lua 实现与 C# 实现的结果相匹配？

I'm using 32-bit FNV-1a hashing, but now I want to reserve one of the bits to hold useful information about the input key. That is, I want to use only 31 of the 32 bits for hash and 1 bit for something else.

Assuming FNV is well distributed for my application, is it safe to assume that dropping 1 bit this will increase collision rate by 32/31, as opposed to something dramatic?

The algo recommends XOR the discarded MSB with the LSB, but for 1-bit, that seems pointless. As such, would it matter which bit is discarded (MSB or LSB)? And if not, would it matter if the LSB MSB were discard after hashing each byte (i.e. using a even numbered "prime") or after 32-bit hashing the entire byte-array first.