我应该如何为这些需求实现一个字符串哈希函数?

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

至于冲突,看看散列输出有多大。Java自己的 hashcode() int ,因此,可以预期冲突比 MD5 或 SHA-1 ,例如分别产生128位和160位。

但是,您不应该尝试从头开始创建这样一个函数。

你没有描述在什么情况下 字符串应该返回 相同的

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

不管你做什么,不要假设相等的散列意味着相等的键(即散列是唯一的)——这总是潜在问题的原因。

Java的字符串hashcode将为您提供 int long ,可以取MD5和的最低有效位作为字符串。

可能会发生碰撞,你的系统必须做好准备。也许如果你能更详细地说明散列码的用途,我们就能知道碰撞是否会引起问题。

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

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

birthday problem 更多的分析。

如果事先知道所有的关键点,可以使用 perfect hashing .