HashMap＃hash（int）方法的说明

Question

有人可以向我解释静态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);
}

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

澄清 我知道运算符，真值表和按位运算。我只是无法真正解码实现，也无法真正评论。甚至是背后的原因。

Answer 1

>>>是逻辑右移（无符号扩展）（JLS 15.19 Shift
Operators
），并且^是按位异或（JLS
15.22.1 Integer Bitwise
Operators

）。

关于这样做的原因，文档提供了一个提示：HashMap使用2的幂的长度表，并通过掩盖掉哈希码的较高位并仅获取其较低位来哈希键。

// 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()尝试使相关性与较高的位有关，否则将被屏蔽掉（indexFor基本上丢弃的较高位，h而仅在处使用较低的k位length == (1 << k)）。

将此与Hashtable使用密钥的哈希码的方式（应该没有二乘幂长度表）进行对比。

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

通过执行更昂贵的%操作（而不是简单的位屏蔽），的性能对Hashtable在较低位（尤其table.length是素数）中分布较差的哈希码不太敏感。