6

1) 出于真正低哈希冲突的目的,我可以只使用 sha1 的 128 位中的一半而不是处理 sha1 本身吗?我知道这不适合加密哈希,但我只需要哈希表键的哈希。

2)计算时间不是优先事项,除此之外我正在散列非常小的数据。特别是,我主要会采用 2 或 3 个 64 位散列并对它们进行散列以获得另一个 64 位散列。为此目的,是否有比 sha1 更好的选择?同样,碰撞应该是非常不可能的。

3)我是一个sql新手。在 sql 中使用 64 位哈希作为 id 是个好主意吗?64 位 id 会在 sqlite 或 postgres 中导致性能问题吗?我将需要跨多个数据库(包括 Lucene 索引)协调数据,所以我认为我应该直接在表中处理哈希,而不是使用自动递增的 id(这只会在一个 db 中有意义,而不是跨所有数据存储)。我认为 64 位是一个很好的折衷方案:对于不太可能发生的冲突来说足够大,但可以节省空间(和查找时间?)。

4) CRC-64 怎么样?这会产生足够随机的分布吗?

4

5 回答 5

6

如果您的记录足够少,则几乎可以肯定您永远不会发生 64 位哈希冲突。您很可能会属于这一类。

修剪像 sha1 这样的加密哈希应该没有问题,因为如果哈希中有内部结构,那么它就不足以成为加密哈希,如果没有结构,那么比特的任何子集都应该是相当随机。请注意,我只是在谈论将其用于 ID,而不是用于任何加密目的!

但实际上,您的 SQL 没有某种 GUID 吗?如果是这样,为什么不使用它呢?

于 2009-04-16T04:04:18.637 回答
4

为了更好地比较散列的长度,请查看http://en.wikipedia.org/wiki/List_of_hash_functions

另外,请注意:SHA-1 是 160 位,而不是 128。

于 2009-04-16T03:41:27.833 回答
3

您的密钥将需要绝对唯一性,而不是唯一性的高概率。我建议使用 GUID 而不是散列作为您的密钥,以实现跨数据库兼容性。生成散列作为一种快速查找机制——你可以有一个非唯一的索引——但在发生冲突的情况下,你必须比较实际数据以确保它们是相同的。在同步数据库时,您可以检查哈希(快速使用索引),如果发现冲突,则解析数据是否相同,因此需要解析 GUID。如果没有冲突,则只需更新需要丢失条目的数据库并使用来自其他数据库的 GUID 插入。

我也认为创建自己的哈希值以节省空间没什么意义。如果您已经有其他哈希,只需使用它们(追加,不要重新哈希)。如果没有,只需使用标准哈希函数(如 MD5 或 SHA1)并存储结果数据。

于 2009-04-16T03:49:04.430 回答
2

使用 64 位哈希,您有 1% 的机会与 6.1 × 10 8条记录发生冲突。(对于其他组合,请参阅有关生日问题的 Wikipedia页面。)您可以丢弃每第二位的前 64 位或最后一位,这对散列的属性没有任何影响。

于 2011-05-25T10:39:09.387 回答
0

如果计算时间不重要,为什么不使用整个 128 位呢?除了可能的存储问题之外,还有什么真正的理由选择 64 位?(然后额外的 8 个字节不会因为如此便宜的存储而杀死你)

64 位与 128 位在 SQLite 中不会导致速度问题,我不确定 mySQL。

于 2009-04-16T03:38:36.607 回答