如何避免crc16碰撞？

Question

我遇到了一个非常烦人的问题，使用crc16哈希来管理我的一些信息。

在我的应用程序中，我将一些信息传递给url参数，这是一个巨大的编码上下文。该上下文允许用户恢复他们的旧搜索。在这种情况下，我有一些散列元素，以确保不会占用太多字符。

似乎有些元素返回相同的哈希(crc16算法)。

我将其转换为字符串: crc.ToString("X4")；例如，两个不同的元素给出了5A8E。

我尝试使用crc32，但是如果这样做，旧的上下文就不会被识别。

你知道我怎么能找到解决办法吗？非常感谢

Answer 1

即使CRC16是一个理想的哈希函数(它不是)，只要有16位，Birthday Paradox意味着在一组仅为2^8 =256个项的集合中，哈希冲突的概率约为50%。你几乎肯定需要更多的东西。

你不能让旧的散列继续工作，让它们区分现有的冲突--这是个矛盾。但是您可以实现一个新的、更好的散列方案，在URL参数中添加一个标志来指示您正在使用这个新方案，确保您的所有页面只生成这些新样式URL，并在旧样式URL中生成“祖父”(这将继续产生与前面相同的冲突)。我建议给用户一个大的，明亮的信息，以更新他们的书签，并自动重定向页面，无论何时你得到一个旧的风格的URL。

Answer 2

为了解释我考虑过的另一个解决方案，我正在实施。

我只是为我的元素准备了一个crc32和一个crc16散列。我现在构建的新urls使用32，但是使用crc16散列作为旧urls的后盾。

所以，当我尝试比较Hash时，我从新的Hash开始，如果找不到任何元素，我就回过头来，将它与crc16哈希进行比较。

这样我就能得到任何案子了。