什么散列函数更好？

我在Java中编写我的HashMap实现。我使用开放寻址来解决冲突。为了更好的密钥分发，我想使用一个很好的哈希函数来获得密钥的哈希码。我不知道什么散列函数更好？什么散列函数更好？

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

我需要密钥哈希码的散列函数。

来源

2012-02-04 gizzy

你的问题并不十分清楚。你是否重新实现了HashMap（为什么？）或为希望用作HashMap键的类编写hashCode（）方法？在你的示例中，你为什么要重新哈希密钥提供的hashCode？ – 2012-02-04 07:04:20

使用% 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（）函数没有什么可以做的。

Why doesn't String's hashCode() cache 0?

来源

2012-02-04 09:22:15

任何分配您希望均匀接收的值的散列都是一个很好的散列函数。

您的目标是最大限度地提高性能（当然，在保持正确性的同时最大化性能）。主要关心的是尽量减少桶碰撞。这意味着理想的哈希是针对您的输入数据量身打造的 - 如果您知道您会收到什么，您可以选择哈希产生最小数量的冲突，甚至可以实现缓存最佳访问模式。

然而，这通常不是一个现实的选择，所以你只需选择一个散列，其输出是无偏且不可预测的（其行为像一个伪随机数生成器，但具有确定性）。一些这样的功能是“杂音”散列族。

来源

2012-02-04 07:07:24 Borealid

什么散列函数更好？

回答

相关问题