0

好的，我需要一个散列函数来满足以下要求。这个想法是能够将属于相同逻辑结构但存储在文件系统的不同物理区域中的目录链接在一起。

我需要用 Java 实现它，它必须在执行会话中保持一致，并且可以返回很长的值。

我将散列目录名称/字符串。这应该可以工作，"somefolder1"并且"somefolder2"将返回不同的哈希值，就像"JJK"和"JJL". 我也想知道什么时候可能发生冲突。

有什么建议么？

谢谢

4

4 回答 4

4

好吧，几乎所有的散列函数都具有这样的特性：输入的微小变化会导致输出的大变化，这意味着“somefolder1”和“somefolder2”总是会产生不同的散列。

至于冲突，只看哈希输出有多大。Java 自己的hashcode()返回 an int，因此您可能会比MD5或SHA-1更频繁地发生冲突，例如分别产生 128 位和 160 位。

不过，您不应该尝试从头开始创建这样的函数。

但是，我不太明白您的用例是否不应该发生冲突，或者如果很少发生冲突是否可以接受。对于链接文件夹，我肯定会使用有保证的唯一标识符，而不是可能多次出现的标识符。

于 2010-01-22T12:54:19.043 回答
2

您还没有描述在什么情况下不同的字符串应该返回相同的哈希值。

一般来说，我会通过首先实现相等函数来设计散列函数。这应该会告诉你哪些数据需要包含在哈希中，哪些应该被丢弃。如果两个不同数据位之间的相等性很复杂（例如不区分大小写），那么希望该特定比较会有相应的散列函数。

无论您做什么，都不要假设相等的散列意味着相等的键（即散列是唯一的）——这始终是潜在问题的原因。

于 2010-01-22T12:55:05.960 回答
1

Java 的 String 哈希码会给你一个int，如果你想要一个long，你可以为字符串取 MD5 和的最低有效 64 位。

可能会发生碰撞，您的系统必须为此做好准备。也许如果你提供更多关于哈希码将用于什么的细节，我们可以看到冲突是否会导致问题。

于 2010-01-22T13:30:59.463 回答
1

对于具有 M 个可能值的均匀随机散列函数，在 N 个散列之后发生冲突的几率为 50%，当

N = .5 + SQRT(.25 - 2 * M * ln(.5))

查找生日问题以进行更多分析。

如果您使用完美散列提前知道所有密钥，则可以避免冲突。

于 2010-01-22T13:48:05.707 回答