logo标签列表

可以仅使用sha1哈希的64位作为id吗？

hashsha1
6

1) 为了实现真正低的哈希碰撞，我是否可以仅使用sha1的128位中的一半，而不必处理整个sha1？我知道这不适用于加密哈希，但我只需要将哈希用作哈希表键。

2) 计算时间不是优先考虑的问题，此外，我要对非常小的数据块进行哈希。特别地，我主要会取2或3个64位哈希值并将它们哈希以获得另一个64位哈希值。除了微小的概率之外，是否有比sha1更好的选项？

3) 我是一个sql新手。在sql中使用64位哈希作为id是否明智？64位id是否会引起sqlite或postgres的性能问题？我需要协调跨多个数据库（包括Lucene索引）的数据，所以我想应该直接在表格中处理哈希，而不必费心自增的id（这只有在一个数据库中有意义，不是所有数据存储都有）。我认为64位是一个很好的折衷：足够大来避免碰撞，但可以节省空间（和查找时间？）。

4) 那么CRC-64呢？它的分布是否足够随机？

5个回答
6
如果你的记录很少，那么在64位中几乎肯定不会发生哈希碰撞。很可能你就是这种情况。
将加密哈希值（如sha1）缩短应该没有问题，因为如果哈希中有内部结构，则不足以成为加密哈希，而如果没有结构，则任何位的子集都应该是相当随机的。请注意，我只是在谈论将其用于ID，而不是任何加密目的！
但是，你的SQL数据库中真的没有GUID吗？如果有，为什么不使用它呢？
我想GUID/UUID可能是我想要的。不确定sqlite的支持是否足够，所以我会调查一下。就像我说的，我是一个SQL新手。 - Jegschemesch
Sqlite3可以很容易地扩展支持UUID，我之前在iPhone应用程序中成功实现了这一点。 - Bob Aman
我同意这个答案。我有一个填满了数亿行的表格，为了性能原因，使用前64位作为无符号整数键而不是SHA1哈希字符串。在350万行中，我遇到了一些56位的冲突。我总是将64位哈希键与其日期组合在一起，以便两者都需要匹配。使用这种方法，每天只有3000万行可能会发生冲突，大大降低了长期发生的机会。碰撞会导致单个信息放错位置 - 在我的情况下，这是值得节省的。 - bhelm
4
3
你的键需要绝对的唯一性而不是高概率的唯一性。我建议使用GUID代替哈希作为你的键，以实现跨数据库兼容性。生成哈希作为快速查找机制--你可以在此上建立非唯一索引--但在冲突的情况下，你必须比较实际数据以确保它们是相同的。在同步你的数据库时，你可以检查哈希（使用索引快速），如果发现冲突，则解决数据是否相同，因此需要解决GUID。如果没有冲突，那么只需更新需要缺少条目的任何数据库，并使用另一个数据库中的GUID进行插入。
我也认为创建自己的哈希哈希来节省空间没有什么意义。如果你已经有了其他哈希，请使用它们（追加，不要重新哈希）。如果没有，请使用标准哈希函数，如MD5或SHA1，并存储结果数据。
1
但是为什么我需要绝对的唯一性呢？我们不是在谈论非常高的概率吗？任何两个项具有相同哈希的概率是2^128中的1，对吧？难道我们不应该担心被流星击中吗？还是MD5和sha1的分布不够随机？ - Jegschemesch
啊，我觉得我们之间存在误解，因为我不知道GUID / UUID，而你似乎认为我知道。但是GUID也不是绝对唯一的，对吧？ - Jegschemesch
是的。全局唯一（或通用唯一）标识绝对是唯一的。生成算法确保没有两台机器产生相同的标识。我的观点是，如果您将其用作主键，即使是一次冲突也无法容忍，无论它有多么罕见。 - tvanfosson
2
使用64位哈希，当有6.1×108条记录时，发生碰撞的概率为1%。（有关其他组合，请参见维基百科上的“生日问题”页面。）您可以丢弃每个二进制数的第一个64位或最后一个64位，这不会对哈希的属性产生任何影响。
0

如果计算时间不重要，为什么不选择完整的128位呢？除了可能的存储问题外，是否有任何真正的理由选择64位？（而且额外的8字节并不会因为存储便宜而对你造成困扰）

在SQLite中，64位和128位之间不会引起速度问题，至于mySQL我就不确定了。

我认为，当使用随机哈希数据作为键时，如果该键适合于机器本地整数而不是字符串，则大多数数据库系统在搜索和连接操作方面更有效率。 - bhelm
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接