什麼散列函數更好？

我在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

什麼散列函數更好？

回答

相關問題