寻找一种哈希函数/有序整数/转换为/随机整数/。

Question

我正在寻找一个常数时间算法，可以将有序整数索引值转换为随机哈希索引。如果它是可逆的，那就太好了。我需要每个索引的哈希键都是唯一的。我知道这可以通过在大文件中查找表来完成。例如，创建所有整数的有序集合，然后随机洗牌并以随机顺序写入文件。然后您可以根据需要读取它们。但是这将需要在大文件中进行搜索。我想知道是否有一种简单的方法，例如使用伪随机生成器按需创建序列？使用PRNG而不是洗牌生成打乱的范围 答案，由Linear Feedback Shift Registers的erikkallen提供的看起来很合适。我刚试过了，但它会产生重复和空洞。谢谢！ David Allan Finch

- David Allan Finch

---

我认为这里的信息不足以提供一个好的解决方案。你需要哈希多少个整数？该整数列表中会有重复项吗？你的列表将具有哪些值范围？ - EvilTeach

有序整数可以是负数吗？ - EvilTeach

我想使用无符号长整型或长长整型的全部范围（即32位或64位）。 - David Allan Finch

只是好奇——“遗传算法”标签是怎么出现的？ - Jason S

我输入了“算法”，因为那似乎是我想要的。自动完成功能输入了“遗传算法”。如果标签不正确，我很乐意将其删除。 - David Allan Finch

Answer 1

现在的问题是你是否需要一个真正随机的映射，或者只需要一个“弱”的排列。假设是后者，如果你使用无符号32位整数（比如说），进行2的补码算术运算，那么任何奇数乘以它都是双射和可逆映射。当然，XOR也是一样的，因此你可以尝试使用一个简单的模式，比如：

unsigned int hash(int x) {
   return (((x ^ 0xf7f7f7f7) * 0x8364abf7) ^ 0xf00bf00b) * 0xf81bc437;
}

数字本身并没有什么神奇的地方。因此，您可以更改它们，甚至可以随机化它们。唯一需要注意的是乘数必须是奇数。而且你必须使用循环计算（忽略溢出）。这可以被反转。要进行反演，您需要能够计算出正确的互补乘数A和B，之后就可以进行反演。

unsigned int rhash(int h) {
    return (((x * B) ^ 0xf00bf00b) * A) ^ 0xf7f7f7f7;
}

你可以通过数学计算来得出A和B，但更简单的方法是运行一个循环并搜索它们（离线状态下）。

该方程式使用异或和乘法混合，使映射非线性化。

- antti.huima

---

有趣的是A和B不是互逆的，A=1/0x8364abf7，或者存在舍入问题。 - David Allan Finch

不，它们在那个意义上不是互逆的。它们是模2**32下有限乘法群中的互逆元素。这与有理数域中的互逆元素无关。 - Antti Huima

我已经快速运行了前十万个数字，结果看起来良好且非常快速。我希望明天有更多时间来测试一个更大的数字集。 - David Allan Finch

是的，它很好也很快 :) 唯一的问题是最低位比较线性... 但这在大多数情况下不会影响你的应用。如果你想要改变这个，你可以在第一次乘法后加上 ((x<<13)|(x>>19)) 到方程式中。反过来也是显而易见的。 - Antti Huima

Answer 2

您可以尝试构建适合您需求的费斯特网络。这些通常用于密码学（例如DES），但至少需要64位，因此您可能需要自己构建一个适合您需求的网络。它们是通过构造可逆的。

- starblue

---

我认为这是正确的答案，但我需要一些时间来想出如何实现 Feistel 网络。 - David Allan Finch

Answer 3

假设您的目标是将分组值分散到整个范围内，似乎以某种预定义顺序洗牌位可能会奏效。例如，给定8位二进制码 ABCDEFGH，可以像 EGDBHCFA 这样排列它们，或者类似的模式。

代码只需要简单的掩码、移位和加法序列即可。

- AShelly

---

是的，那就是我想到的那种东西，但我希望可能会有更随机的东西。 - David Allan Finch

Answer 4

嗯...如果你有很多数字，你可以使用普通的STL列表，并按“随机”标准进行排序。

bool
nonsort(int i, int j)
{
    return  random() & 31 >16 ? true : false;
}

std::list<int> li;
// insert elements
li.sort(nonsort);

然后，您可以使用常规迭代器获取所有整数。请记住，要使用srand()初始化随机值为时间或任何其他伪随机值。

- Diego Sevilla

---

我不知道你可以用排序做到这一点，对于较小的值，我认为这将是一个很好的解决方案。但是我在考虑一个无符号长长整型的大小来处理全部范围。 - David Allan Finch

Answer 5

对于这组限制条件，确实没有解决方案。尝试将32位无符号哈希到32位无符号将导致碰撞，除非您进行简单的操作，例如进行1对1映射。每个数字都是其自身的哈希。

- EvilTeach