hash - 如何确保散列函数不会为 2+ 个不同的条目生成相同的密码？

Question

编辑：有些人将此问题标记为另一个问题的潜在重复。虽然我同意知道生日悖论如何适用于散列函数，但这两个问题（以及各自的答案）解决了 2 个不同但相关的主题。另一个问题是问“碰撞的几率是多少”，而这个问题的主要焦点是“我怎样才能确保碰撞永远不会发生”。

我有一个存储在 S3 中的数据湖，每天都有一个 ETL 脚本转储前一天的其他数据。

由于管道的构建方式，具有管理员访问权限的非常轻率的用户可能会通过手动与来自我们的 OLTP 数据库的转储文件交互并在不应该触发 ETL 脚本时在所述数据湖中产生重复项.

我认为防止数据重复的一个好主意是在我的 ETL 脚本中插入一种安全措施：

• 为每个条目生成一个哈希。
• 将所说的哈希存储在其他地方（如 dynamodb 表）。
• 每当有新数据进入时，也要对其进行哈希处理，并将其与已经存在的哈希值进行比较。
• 如果任何新散列在现有散列中，则完全拒绝相关条目。

但是，我对散列知之甚少，我读到虽然不太可能，但 2 个不同的来源可以产生相同的散列。

我知道在这种情况下真的很难发生，但我想知道是否有办法 100% 确定它。

任何想法都非常感谢。

标签： hash

Answer 1

长答案：您想要学习和探索的内容称为“完美哈希”（即哈希保证不会发生冲突。https://en.wikipedia.org/wiki/Perfect_hash_function

简短的回答：像 sha-1 这样的加密防碰撞算法可能可以安全地用于除最大（每天 PBs）数据集之外的所有数据集，即使这样也可能没问题。Git 在内部使用 sha-1，代码存储库可能处理地球上最多的文件，并且很少发生冲突。详见：https ://ericsink.com/vcbe/html/cryptographic_hashes.html#:~:text=Git%20uses%20hashes%20in%20two,computed%20when%20it%20was%20stored 。

中等答案：总体而言，这实际上是一个相当困难的问题，也是计算机科学的一个常见研究领域，很大程度上取决于您的特定用例和您正在操作的环境。Cuckoo 散列、抗碰撞算法和散列一般是可能所有研究的好术语。在选择这些方法时，空间（内存）和时间（需要的计算机能力）背后还有很多艺术和科学。一个好的经验法则是，与 sha-1 这样的抗冲突加密哈希相比，完美的哈希通常会占用更多的空间和时间。