java - JDK源码中java.util.Hashtable的hashCode函数如何理解

Question

正如纪录片中所说，“此代码滥用 loadFactor 字段作为 hashCode in progress 标志执行双重任务，以免恶化空间性能。负负载因子表示哈希码计算正在进行中”这段话怎么理解？

public synchronized int hashCode() {
    /*
     * This code detects the recursion caused by computing the hash code
     * of a self-referential hash table and prevents the stack overflow
     * that would otherwise result.  This allows certain 1.1-era
     * applets with self-referential hash tables to work.  This code
     * abuses the loadFactor field to do double-duty as a hashCode
     * in progress flag, so as not to worsen the space performance.
     * A negative load factor indicates that hash code computation is
     * in progress.
     */
    int h = 0;
    if (count == 0 || loadFactor < 0)
        return h;  // Returns zero

    loadFactor = -loadFactor;  // Mark hashCode computation in progress
    Entry[] tab = table;
    for (int i = 0; i < tab.length; i++)
        for (Entry e = tab[i]; e != null; e = e.next)
            h += e.key.hashCode() ^ e.value.hashCode();
    loadFactor = -loadFactor;  // Mark hashCode computation complete

return h;

Answer 1

使用负载因子作为进行中检查的目的是确保如果存在返回哈希表本身的循环引用链，代码不会陷入无限循环。例如，想象一个类型为 Hashtable<String,Hashtable> 的哈希表，即从字符串到其他哈希表的映射。然后，表中的条目可能包含对同一哈希表本身的引用；或者，它可能指向另一个相同类型的哈希表，然后该哈希表又指向同一个表。因为哈希码递归计算键和值的哈希码，然后将它们组合起来产生最终的哈希码，如果它没有检测到循环引用(图中的循环)，它将陷入无限循环。

当代码遇到循环引用时，它会注意到这一点，因为负载因子将是负数，表明已经遇到了哈希表。在这种情况下，它将通过返回 0 而不是进一步递归来中断循环。

我在 XEmacs 上做了很多工作，它的 Lisp 解释器中有类似的散列代码。它使用了一个不同的技巧:它有一个递归深度值，该值被传递给相当于 hashCode 的值。函数并在每次函数递归到另一个对象时递增。如果深度超过一定数量，它拒绝进一步递归。这不像 Java 的技巧那么脆弱，但在 Java 中是不可能的，因为 hashCode函数的签名是固定的，其中没有递归深度参数。