10

有人可以解释这些常数的意义以及为什么选择它们吗？

static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

来源：java-se6 库

4

2 回答 2

2

理解什么是好的散列函数是很棘手的，因为实际上有很多不同的函数被使用并且用于稍微不同的目的。

Java 的哈希表的工作方式如下：

  1. 他们要求关键对象产生其哈希码。该hashCode()方法的实现可能具有明显可变的质量（在最坏的情况下，返回一个常量值！）并且绝对不会适应您正在使用的特定哈希表。
  2. 然后他们使用上述函数将位混合一点，以便高位中存在的信息也向下移动到低位。这很重要，因为接下来……</li>
  3. 他们采用哈希码的 mod（wrt 哈希表数组条目的数量）来获取哈希表链数组的索引。哈希表数组的大小很可能等于 2 的幂，因此步骤 2 中的位混合对于确保它们不会被丢弃很重要。
  4. 然后他们遍历链，直到他们到达具有相同键的条目（根据equals()方法）。

完成图片，哈希表数组中的条目数是非恒定的；如果链变得太长，则数组将替换为新的更大的数组，并且所有内容都会重新散列。这相对较快，并且对于正常使用模式（例如，很多put()s 后跟很多get()s）具有良好的性能影响。

实际使用的常量是相当随意的（可能是通过对一些简单的语料库进行实验来选择的，包括大量的Integer和String值之类的东西），但它们的目的不是：将整个值中的信息传播到值中的大部分低位确保hashCode()尽可能好地使用输出中存在的此类信息。

（您不会使用完美散列或加密散列来执行此操作；尽管名称相似，但它们具有非常不同的实现策略。前者需要了解密钥空间以便避免/减少冲突，而后者需要移动信息大约在各个方向，而不仅仅是低位。）

于 2012-09-04T15:18:51.590 回答
0

我也想知道这样的“神奇”数字。据我所知，它们是神奇的数字。
广泛的测试已经证明，奇数和素数具有可用于散列的有趣优先级（避免主/次聚类等）。
我相信大多数数字都是在研究和测试之后得出的，这些数据在统计上证明可以提供良好的分布。为什么具体这些数字会这样做，我不知道，但我有印象（希望这里的同事可以纠正我，如果我离题了），实施者都不知道为什么这些具体数字会呈现这些品质

于 2012-09-03T21:12:43.230 回答