java - 什么哈希函数更好？

Question

我用 Java 编写了 HashMap 的实现。我使用开放寻址来解决冲突。为了更好的密钥分配，我想对密钥的哈希码使用一个很好的哈希函数int。我不知道什么哈希函数更适合它？

public int getIndex(K key) { return hash(key.hashCode()) % capacity; }

我需要一个哈希函数来处理密钥的哈希码。

Answer 1

任何能够平均分配您期望接收的值的散列都是一个很好的散列函数。

您的目标是最大化性能（嗯，在保持正确性的同时最大化性能）。主要关心的是尽量减少桶碰撞。这意味着理想的散列是为您的输入数据量身定制的——如果您知道您将收到什么，您可以选择产生最少冲突数量的散列，甚至可能是缓存优化的访问模式。

但是，这通常不是一个现实的选择，因此您只需选择一个其输出无偏且不可预测的哈希（其行为类似于伪随机数生成器，但具有确定性）。一些这样的函数是“杂音”散列系列。

Answer 2

using 的主要问题% capacity是它可以返回负值和正值。

HashMap 通过使用 2 的幂来避免这个问题，并使用以下方法

 public int getIndex(K key) { return hash(key.hashCode()) & (capacity-1); }

如果容量不是 2 的幂，则可以忽略高位（通常不那么随机）

 public int getIndex(K key) { return (hash(key.hashCode()) & 0x7FFFFFFF) % capacity; }

实际使用的哈希函数很重要。HashMap 使用以下

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

我会使用这个，除非你有充分的理由不这样做。例如，出于安全原因，如果您的服务可能会受到拒绝服务攻击，您将需要使用不同的哈希值来避免恶意用户将您的 HashMap 转换为 LinkedList。不幸的是，您仍然必须使用不同的 hashCode() ，并且您可以使用底层哈希码创建一长串字符串，因此稍后对其进行变异为时已晚。

这是一个 hashCode() 为 0 的字符串列表，hash() 函数对此无能为力。

为什么 String 的 hashCode() 不缓存 0？