字符串的双向“哈希”

Question

我希望能从字符串生成整数，并能够将其转换回来。类似于哈希函数但是是双向的。我想在我的应用程序中使用整数作为ID，但希望在记录或调试时能够将其转换回来。

例如：

int id = IDProvider::getHash("NameOfMyObject");

object * a = createObject(id);

...

if(error)
{
    LOG(IDProvider::getOriginalString(a->getId()), "some message");
}

我听说过稍微修改的CRC32可以快速并且100％可逆，但是我找不到它，也无法自己编写。

有什么提示应该使用什么呢？ 谢谢！

编辑 我刚刚发现了我从中获取整个CRC32事物的来源：

Jason Gregory：游戏引擎架构

引用：

“与任何哈希系统一样，冲突是可能的（即，两个不同的字符串可能具有相同的哈希代码）。但是，通过适当的哈希函数，我们几乎可以保证在我们的游戏中使用的所有合理输入字符串都不会发生冲突。毕竟，32位哈希代码表示超过40亿个可能的值。因此，如果我们的哈希函数很好地将字符串均匀分布在这个非常大的范围内，我们不太可能发生碰撞。在顽皮狗公司，我们使用了CRC-32算法的变体来哈希我们的字符串，在《神秘海域：德雷克的宝藏》的开发中，我们没有遇到任何碰撞。”

- relaxxx

---

哈希不是指那个意思。 - SLaks

你是在谈论这个吗？只有CRC32的特殊情况是可逆的：https://dev59.com/G3I_5IYBdhLWcg3wHvY5 - wkl

不要误解 crc32 的作用，它的主要目的是检测位错误。 - AndersK

@SLaks 我知道哈希的意思，但我找不到其他的词。这就是为什么我用引号，并写上 something like 并使用术语 two-way 的原因。 - relaxxx

这不会给出整数，也没有绑定到C++，但为了搜索的缘故，人们可能会对base64编码感兴趣（例如在bash中，echo whatever | base64会给出d2hhdGV2ZXIK，而base64 -d则可以将其解码回whatever）。 - Skippy le Grand Gourou

Answer 1

将任意长度的字符串缩小为固定大小的整数是数学上不可能逆转的。详见鸽笼原理。有无限多的字符串，但只有2^32个32位整数。

32位哈希（假设您的整数是32位）很容易发生冲突。所以它也不是一个好的唯一标识符。

有些哈希函数可以允许您创建具有预定义哈希值的消息，但这很可能不会是原始消息。这被称为预像攻击。

针对您的问题，最好的解决方案似乎是创建一个将整数ID映射回字符串的字典。

---

要获取在哈希n个字符串时碰撞的可能性，请查看生日悖论。在这种情况下最重要的属性是：一旦已哈希消息的数量接近可用哈希值的平方根，碰撞就变得可能。因此，使用32位整数进行哈希，如果哈希大约65000个字符串，则碰撞变得可能。但如果你运气不好，它可能会更早发生。

- CodesInChaos

---

谢谢您的回答。由于各种原因，我不想使用字典来完成它。我对一些哈希函数的修改很感兴趣，请查看我问题的编辑。 - relaxxx

@放松一下，碰撞概率取决于你哈希的字符串数量和哈希的大小。如果你想要避免实际上的碰撞，我推荐使用128位以上的哈希函数。但即便如此，要恢复原始字符串仍然不容易。 - CodesInChaos

Answer 2

我有你所需的东西，它叫做“指针”。在这个系统中，“指针”总是唯一的，并且始终可以用于恢复字符串。它可以“指向”任何长度的字符串。作为奖励，它的大小与你的int相同。你可以通过使用&操作符来获取指向字符串的“指针”，就像我示例代码中展示的那样：

#include <string>
int main() {
    std::string s = "Hai!";
    std::string* ptr = &s; // this is a pointer
    std::string copy = *ptr; // this retrieves the original string
    std::cout << copy; // prints "Hai!"
}

- Puppy

---

+1 for the formulation. :) 不过，公平地说，在不同的运行中指针值是不同的。 - Xeo

这个方案存在几个问题：1）该ID只能在单个进程中使用；2）您需要让字符串保持足够长的生命周期；3）如果将其应用于内容相等但引用不同的多个字符串，则会获得不同的ID。 - CodesInChaos

@CodeInChaos 谢谢，我正准备自己写这个。 - relaxxx

@CodeInChaos：你可以使用boost来获取进程间指针。你也可以使用其他类型的智能指针来序列化指针。其次，他只打算使用一些常量字符串，因此生命周期和引用问题并不是那么重要。 - Puppy

作为额外的好处，它的大小与您的int相同。但是I32LP64不同意。 - Pod

Answer 3

你需要的是加密。哈希是单向的定义。你可以尝试使用一些值的加减和简单的XOR加密。

• 可逆哈希函数？
• 为什么MD5哈希值不可逆？
• 具有可逆属性的校验和/哈希函数
• http://groups.google.com/group/sci.crypt.research/browse_thread/thread/ffca2f5ac3093255

...并通过谷歌搜索等方式找到更多相关信息...

- HashIsGood

---

我知道哈希函数是单向的。这就是为什么我写了关于“哈希函数修改”的内容。请查看我问题的编辑。 - relaxxx

Answer 4

你可以看看完美哈希。

http://en.wikipedia.org/wiki/Perfect_hash_function

只有在所有潜在字符串事先已知的情况下才能起作用。实际上，通过这种方式，您可以创建一个有限范围的“哈希”映射，可以进行反向查找。

通常，[哈希码+哈希算法]永远不足以使原始值返回。但是，使用完美哈希，冲突被定义排除，因此如果已知源域(值列表)，则可以获取源值。

gperf是一个著名的、古老的程序，可以生成c/c++代码中的完美哈希。还有许多其他程序(请参见维基百科页面)。

- sehe

---

实际上，我几乎总是会选择使用字典而不是这个。但偶尔它可能会带来性能上的好处。 - CodesInChaos

同意。不过，其中一个好处是可以仅分享哈希函数。现在任何客户端都可以得出正确的哈希值而无需知道可能输入值的完整表格。对于具有相对较大源域的分布式软件来说，这是一个巨大的福利。 - sehe

Answer 5

这不可能。哈希是不可逆函数 - 根据定义。

- Max

Answer 6

正如大家所提到的，不可能有“可逆哈希”。但是，还有其他选择（比如加密）。

另一个选择是使用任何无损算法对字符串进行压缩/解压。

这是一种简单、完全可逆的方法，没有可能发生碰撞。

- tm.crz