为什么Object#hashCode()返回int而不是long

Question

为什么不这样做：

public native long hashCode();

使用替代方案：

public native int hashCode();

为了更高的概率获得独特的哈希码？

- dimitrisli

---

使用64位的JDK可能会更有意义，但即使今天，hashCode很长也不会带来太大差别。hashCode不需要是唯一的，如果你的元素数量显著少于40亿，则使用32位int就足够了。 - Peter Lawrey

@PeterLawrey 我原则上同意你的观点，但是Preshing表明，由于这个问题的本质，即使你的哈希表只有77163个条目，发生冲突的概率也有50%！ - Kedar Mhaswade

@KedarMhaswade 一个有78K条目的HashMap可能具有128k容量，因此只使用了17位搅动后的hashCode。 - Peter Lawrey

Answer 1

由于数组的最大长度为Integer.MAX_VALUE，请参阅此处。

hashCode() 的主要用途是确定要将对象插入到 HashMap/Hashtable 的后备数组中的哪个槽中。因此，如果 hashcode > Integer.MAX_VALUE，则无法将其存储在数组中。

- matt b

---

有道理，我不确定它是否记录在规范中，但来自Sun JDK的HashMap不能具有大于“1<<30”（~Integer.MAX_VALUE / 2）的表。 - Roman

支撑数组的大小通常要小得多，所以它需要进行缩减。从64位缩减并不是一个问题。另外，hashCode() 允许返回负值... - Michael Borgwardt

为什么数组中不使用long类型？ - Nikolas

@Nikolas，我们不能将long用作数组索引，想一想，对于第1个索引，你能够存储多少个子索引，例如1.1、1.2、1.3、1.1.1.1等等；这样做会带来比你需要的解决方案更多的开销！ - Papai from BEKOAIL

Answer 2

无论如何，哈希码值将用于确定相对较小的表中的行数。例如，在HashMap中，默认表仅包含16行（Sun JDK 1.6.0_17）。这意味着行号是按以下方式确定的：

int rowNumber = obj.hashCode() % rowsCount;

所以，真正的分布范围是从0到rowsCount。

更新：我记得ConcurrentHashMap的实现。简而言之，ConcurrentHashMap包含许多相对较小的表格。首先使用hashCode函数确定表格编号，然后再使用相同的函数确定所选表格中的行。

这种方法消除了数组大小的限制（甚至允许构建分布式哈希表）。

因此，我倾向于结论，hashCode返回int，因为它涵盖了绝大多数的用例。

- Roman

---

这并不完全准确，因为表的大小可以与默认值不同，无论是表增长还是将不同的参数传递给HashMap构造函数。 - matt b

还有哪里不准确吗？:) 没有人会争论表的大小可以比默认值更大。 - Roman

你需要移除最高位（现在rowNumber可能为负数）(obj.hashCode &0x7fffffff)%rowCount。由于模运算大约需要30个CPU时钟（位运算只需要1个），所以条目数保持为2的幂次，并且操作就是 (obj.hashCode & (array.length-1))。 - bestsss

Answer 3

我认为这是计算成本与哈希范围的平衡。哈希码被引用的频率非常高，每次需要哈希时传递两倍的数据会很昂贵，特别是考虑到更常见的用例 - 例如 - 如果你创建一个小的哈希具有10、100或1000个值，你将看到的哈希冲突数差异极其微不足道。对于较大的哈希，想想一个哈希需要多大才能让10**32个值开始频繁发生冲突，以及在JVM中是否可能做到这一点，考虑到需要的内存量。

- Steve B.