编辑:一些人将此问题标记为可能重复 this另外一个。虽然我同意知道生日悖论如何适用于哈希函数,但这 2 个问题(和各自的答案)解决了 2 个不同但相关的主题。 另一个问题是问“碰撞的几率是多少”,而这个问题的主要焦点是“我怎样才能确保碰撞永远不会发生”。
我在 S3 中存储了一个数据湖,每天 ETL 脚本都会转储前一天的额外数据。
由于管道的构建方式,具有管理员访问权限的非常粗心的用户可能会通过手动与来 self 们的 OLTP 数据库的转储文件进行交互并在 ETL 脚本出现时在所述数据湖中生成重复项不应该。
我认为防止数据重复的一个好主意是在我的 ETL 脚本中插入一种安全措施:
- 为每个条目生成一个散列。
- 将所述哈希存储在其他地方(如 dynamodb 表)。
- 每当有新数据出现时,也对其进行哈希处理,并将其与现有的哈希值进行比较。
- 如果现有哈希中有任何新哈希,则完全拒绝相关条目。
但是,我对哈希知之甚少,而且我读到过,虽然不太可能,但 2 个不同的来源可以产生相同的哈希。
我知道在这种情况下很难做到这一点,但我想知道是否有办法 100% 确定这一点。
非常感谢任何想法。
最佳答案
长答:你要研究和探索的东西叫做“完美散列”(即保证不发生冲突的散列。https://en.wikipedia.org/wiki/Perfect_hash_function
简短回答:像 sha-1 这样的加密防碰撞算法可能可以安全地用于除最大(每天 PB)数据集之外的所有数据集,即使这样也可能没问题。 Git 在内部使用 sha-1,代码存储库可能处理地球上最多的文件并且很少发生冲突。 详见:https://ericsink.com/vcbe/html/cryptographic_hashes.html#:~:text=Git%20uses%20hashes%20in%20two,computed%20when%20it%20was%20stored .
中等答案:总体而言,这实际上是一个非常困难的问题,也是计算机科学的一个常见研究领域,在很大程度上取决于您的特定用例和您所处的环境。布谷鸟哈希、抗碰撞算法和哈希一般来说,可能都是很好的研究术语。在选择这些方法时,空间(内存)和时间(需要的计算机能力)背后也有很多艺术和科学。一个好的经验法则是完美哈希通常比像 sha-1 这样的抗冲突加密哈希占用更多的空间和时间。
关于hash - 我如何确保哈希函数不会为 2 个以上的不同条目生成相同的密码?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64915078/