HashMap#hash（int）方法说明

hashmap java hash

2022-09-01 17:47:20

有人可以向我解释静态HashMap#hash（int）方法吗？

它背后生成均匀分布的哈希值的理由是什么？

/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
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);
}

一个例子可以使它更容易消化。

澄清我知道运算符，真值表和按位操作。我只是无法真正解码实现或注释。甚至是它背后的原因。

答案 1

>>>是逻辑右移位（无符号扩展）（JLS 15.19 移位运算符），并且是按位排他或（JLS 15.22.1 整数按位运算符）。^

至于为什么要这样做，文档提供了一个提示：使用两个长度的幂表，并通过屏蔽较高的位并仅获取其哈希代码的较低位来散列密钥。HashMap

// HashMap.java -- edited for conciseness
static int indexFor(int h, int length) {
    return h & (length-1);
}

public V put(K key, V value) {
    int hash = hash(key.hashCode());
    int index = indexFor(hash, table.length);
    // ...
}

因此，试图将相关性带到较高的位，否则将被掩盖（基本上丢弃较高的位，并且只获取较低的位）。hash()indexForhklength == (1 << k)

与此形成对比的是（不应具有两次幂长度表）使用密钥哈希代码的方式。Hashtable

// Hashtable.java -- edited for conciseness
public synchronized V get(Object key) {
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % table.length;
    // ...
}

通过执行更昂贵的操作（而不是简单的位屏蔽），性能对在较低位中分布较差的哈希代码（特别是如果是质数）不太敏感。%Hashtabletable.length

答案 2

我不知道所有的转变是如何运作的，但动机在评论中列出：

HashMap的实现方式依赖于hashCode函数是否得到充分的实现。特别是，哈希值的下位应均匀分布。如果下位上有许多冲突，则 HashMap 将无法正常运行。

由于hashCode的实现超出了HashMap的控制范围（每个对象都可以实现自己的），因此它们提供了一个额外的哈希函数，该函数将对象的hashCode稍微移动一下，以确保较低的位分布更加随机。同样，我不知道这是如何工作的（或者它有多有效），但我认为它至少取决于平均分布的较高位（它似乎将较高的位网格化为较低的位）。

因此，这样做的目的是在存在实现不佳的哈希码方法的情况下尝试最小化冲突（从而提高性能）。

HashMap#hash（int） 方法说明

HashMap#hash（int）方法说明