短字符串的哈希码可以相同吗？

Question

我有一些长度很短的字符串（少于10个字符）。我会将它们转换成整数并用作主键。 （由于小问题，我不能使用字符串主键。）我知道无限长度的字符串哈希码可能会冲突，但是短字符串也会发生冲突吗？

- Cinakyn

---

https://dev59.com/g2kw5IYBdhLWcg3wJXMh - user2864740

参见http://www.drmaciver.com/2008/07/javalangstringhashcode/ - Scrabble单词有很多冲突。一些统计数据：“大小为2的字母数字字符串有3844个。其中3570个与至少一个其他字符串发生了碰撞。也就是说，这些字符串中只有274个（约7%）没有与其他东西发生碰撞。 哦，好吧。“没关系，没有人会愚蠢到依赖hashCode来区分两个对象的内容。” - user2864740

Answer 1

当然可以。例如，Ea 和 FB 是碰撞字符串，每个字符串只有两个字符的长度！示例：

public static final void main(String[] args) {
    System.out.println("Ea".hashCode() + " " + "FB".hashCode());
}

打印出 2236 2236。

---

Java中的String#hashCode函数并不像随机函数一样随机。对于短字符串来说，很容易生成哈希冲突；即使是对于长字符串而言，其表现也没有明显改善。

一般情况下，即使你只使用每个字符6位（ASCII字母和数字以及一些符号），当你使用一个6个字符的字符串时就已经超过了32位哈希码的可能值 -- 也就是说，在2^36个6位字符的字符串中将绝对保证会有哈希冲突。

- nneonneo

---

+1 个直接的[反例]。看到一个字符串/哈希碰撞图可能会很有趣，这可能已经存在了... - user2864740

实际上，这可以用来创建拒绝服务攻击，将HashMap的O(1)行为变成O(N)：https://dev59.com/7Woy5IYBdhLWcg3wQr1i - yshavit

@yshavit的问题已经在Java 8中解决了，这个版本是在你发表评论几个月之前发布的；^) - Holger

@Holger，是什么让你突然冒出这个问题的？:-P - yshavit

@yshavit 搜索了一些与字符串哈希相关的内容，这是搜索结果中的一部分。 - Holger

Answer 2

哈希码的大小为32位。

在Java中，char大小为16位。

因此，在理论上，所有2个字符的字符串都可以具有不同的哈希码，尽管其中一些哈希码必须与空字符串和单字符字符串的哈希码发生冲突。即使只考虑“所有两个字符或更短的字符串”，也会发生冲突。到你有10个字符时，可能性会更多，超过了可用的哈希码数量。

冲突仍然很少见，但您应该始终假设它们可能发生。

- Jon Skeet

---

+1 是指出这不仅仅是 Java 有一个愚蠢的哈希函数，而是一个根本性问题。 - Michael Anderson

也许值得注意的是，“罕见”并不意味着很罕见。使用生日悖论，即使使用分布良好的哈希函数，一个包含16k个项的集合也不太可能避免碰撞。(有关准确的数字，请参见http://en.wikipedia.org/wiki/Birthday_attack) - Michael Anderson

@MichaelAnderson：我猜这取决于你所说的“罕见”是什么意思。至少发生一次碰撞的概率可能相当高，但任何特定的一对碰撞的概率都相当小。无论如何，我认为你必须考虑到它，所以这并不太重要 ;) - Jon Skeet

@Holger 我觉得你没有理解我的观点。其他答案表明，Java字符串的哈希值分布对于简单字符串来说是不好的。这个答案指出，即使有完美的哈希分布，我们也应该预期会发生碰撞。 - Michael Anderson