java - Hashtable 与 HashMap 中的哈希函数？

Question

我知道 Hashtable 和 HashMap 的区别。但是，这两个类似乎都在使用散列函数 来完成工作。 Hashtable使用的哈希函数和HashMap使用的哈希函数有区别吗？

特别是他们使用的哈希算法有区别吗？这两个类的哈希公式是什么？

也就是说，索引(哈希值)的计算方式不同吗？

Answer 1

In particular, is there a difference between the hashing algorithm they use? What is the formula used to hash in these two classes?

当您将对象用作哈希表键时，主要使用的哈希函数是对象的 hashCode() 方法。实现合适的哈希函数取决于关键类。

Hashtable 和HashMap 类采用键的哈希码值并将其转换为主哈希表链数组中的索引。但是，Hashtable 和 HashMap 之间发生这种情况的方式有所不同。

• Hashtable (Java 8) 的代码是这样的:

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

• 对于 HashMap (Java 8)，代码(有效地)是这样的:

   // (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 值进行打乱。这在源代码中解释如下:

[This method] computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don't benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

注意事项:

1. & 与 % 的区别是因为在 Hashtable 中哈希数组大小是质数，而在 HashMap (Java 8) 大小是2的幂。

2. 在 Java 8 HashMap 中，如果键类实现了 Comparable，实现会将长哈希链变成二叉树。

   <

3. HashMap 处理 null 键，但 Hashtable 不处理。

---

但是，HashMap 中所有这些额外的复杂性只有在您的关键类具有设计/实现不佳的 hashCode() 方法时才会发挥作用……或者如果有人故意尝试设计哈希冲突。

换句话说，如果您的关键类设计得很好，那么差异应该无关紧要。