3

我想知道我们是否实现了我们自己的不使用二次幂长度哈希表的哈希图（初始容量和每当我们重新调整大小时），那么在这种情况下我们可以只使用对象的哈希码并直接修改总大小而不是使用散列函数来散列对象的哈希码？

例如

   public V put(K key, V value) {
         if (key == null)
             return putForNullKey(value);
         // int hash = hash(key.hashCode());     original way
         //can we just use the key's hashcode if our table length is not power-of-two ?
         int hash = key.hashCode();              
         int i = indexFor(hash, table.length);
         ...
         ...
     }
4

3 回答 3

3

假设我们谈论的是 OpenJDK 7，附加值hash用于刺激雪崩；这是一个混合功能。使用它是因为从哈希到存储桶的映射函数，因为使用 2 的幂作为容量，只是按位&（因为a % b相当于a & (b - 1)iffb是 2 的幂）；这意味着低位是唯一重要的位，因此通过应用此混合步骤，它可以帮助防止更差的哈希值。

 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);
 }

如果您想使用不是 2 的幂的大小，则可能不需要上述内容。

实际上，将映射从哈希更改为存储桶（通常依赖于容量为 2 的幂）将需要您查看indexFor：

 static int indexFor(int h, int length) {
     return h & (length-1);
 }

你可以(h & 0x7fffffff) % length在这里使用。

于 2012-08-08T15:37:43.053 回答
1

您可以将 mod 函数视为哈希函数的一种简单形式。它将大范围的数据映射到更小的空间。假设原始哈希码设计得很好，我认为没有理由不能使用 mod 将哈希码转换为您正在使用的表的大小。

如果您的原始哈希函数没有很好地实现，例如总是返回一个偶数，那么您将只使用一个 mod 函数作为您的哈希函数来创建相当多的冲突。

于 2012-08-08T15:36:48.450 回答
1

这是真的，你可以选择伪素数。

注意： indexFor 需要使用%补偿符号而不是简单的&，这实际上会使查找速度变慢。

indexFor = (h & Integer.MAX_VALUE) % length
// or
indexFor = Math.abs(h % length)
于 2012-08-08T15:37:18.123 回答