Hashtable和HashMap中的哈希函数有什么区别？

Question

我知道Hashtable和HashMap之间的区别。然而，这两个类似乎都使用哈希函数来完成工作。Hashtable中使用的哈希函数和HashMap中使用的哈希函数有什么区别吗？

特别地，它们使用的哈希算法是否有区别？这两个类中用于哈希的公式是什么？

换句话说，计算索引（哈希值）的方式是否不同？

- A. Mashreghi

---

可能是哈希：它如何在内部工作？的重复问题。 - Tibrogargan

最后，两者都使用添加到集合中的对象的hashCode()。因此，用于确定该“哈希”的算法取决于您如何在添加的对象上实现hashCode()（或者一般情况下它是如何实现的）。 - dognose

实际上，对于Java 8，算法是（显著）不同的；请参见我的答案。 - Stephen C

@Tibrogargan 我不认为这是那个问题的重复。至少我没有在那里看到我的答案。 - A. Mashreghi

Answer 1

特别的，它们使用的哈希算法是否有差异？这两个类中用于哈希的公式是什么？

当你将对象用作哈希表键时，主要的哈希函数是对象的`hashCode()`方法。关键类需要实现一个合适的哈希函数。

`Hashtable`和`HashMap`类将关键字的哈希码值转换为主哈希表链数组中的索引。然而，在`Hashtable`和`HashMap`之间在如何进行此过程方面存在差异。

对于`Hashtable`(Java 8)，代码如下:

 hash = key.hashCode();
 index = (hash & 0x7FFFFFFF) % tab.length;

对于 Java 8 中的 HashMap，代码（有效地）如下：

 // (I have restructured the code for ease of comparison.)
 int h;
 hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 index = (tab.length - 1) & hash;

正如您所看到的，HashMap会重新排列由键的hashCode函数返回的hashCode值。源代码中解释如下:

“[此方法]计算key.hashCode（）并将散列的高位（XOR）向下传播。由于表格使用2次幂掩码，因此仅在当前掩码上方位上的位不同的哈希集始终会发生冲突。 （已知示例包括持有小表中连续整数的Float键的集合。）因此，我们应用了一种将较高位的影响向下传播的变换。在速度，实用性和位扩展的质量之间存在权衡。由于许多常见的哈希集已经合理分布（因此无法受益于扩展），而且因为我们使用树来处理大量冲突的bin，因此我们只是以最便宜的方式XOR一些移位位，以减少系统性损失，并将最高位的影响纳入索引计算中，否则由于表界限而永远不会使用。”

注：

1.与Hashtable相比，＆与％的区别在于哈希数组大小是素数，但在Java 8中HashMap的大小是2的幂。 2.在Java 8 HashMap中，如果键类实现了Comparable，则实现将长哈希链转换为二叉树。 3.HashMap处理null键，但Hashtable不这样做。

然而，在HashMap中所有这些额外的复杂性仅在您的键类具有设计/实现不良的hashCode（）方法时才会发挥作用......或者如果有人故意试图制造哈希冲突。

换句话说，如果您的键类设计良好，则这些差异“不应该有任何影响”。

- Stephen C

Answer 2

java.util.Hashtable<K,V>类似于java.util.Vector<T>。这是在开发早期添加到SDK中的一个类，已经被HashMap<K,V>取代（就像ArrayList<T>取代了Vector<T>一样）。

因此，除非您需要所有操作的隐式同步（这默认情况下使用Hashtable），否则您根本不应该使用它，但您仍然可以使用Collections.synchronizedMap来实现目的，或者使用ConcurrentHashMap<K,V>。

如Javadoc所述：

从Java 2平台v1.2开始，这个类被改装为实现Map接口，成为Java Collections Framework的成员。与新的集合实现不同，Hashtable是同步的。如果不需要线程安全的实现，则建议使用HashMap代替Hashtable。如果需要线程安全的高并发实现，则建议使用ConcurrentHashMap代替Hashtable。

这两个类的哈希应该是相同的，因为它们都将使用int Object::hashCode来实现它们的目的。

- Jack

---

例如在 ArrayList 中，当容量达到上限时数组大小会乘以1.5；然而，在 Vector 中这个比率是2。因此，它们并不完全相同。 - A. Mashreghi

那在任何重要的方式上都不是真正重要的。 - Louis Wasserman

实际上，对于Java 8，算法（显著）不同；请参见我的答案。 - Stephen C

@A.Mashreghi - 可以说，这不是哈希算法的差异，而是调整大小算法的差异。 - Stephen C

@A.Mashreghi，我看到你接受了错误的答案。Stephen C 给出了正确的答案。 - Gaurava Agarwal