如何在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函数的签名是固定的，并且其中没有递归深度参数。