我在Java中編寫我的HashMap實現。我使用開放尋址來解決衝突。爲了更好的密鑰分發,我想使用一個很好的哈希函數來獲得密鑰的哈希碼。我不知道什麼散列函數更好?什麼散列函數更好?
public int getIndex(K key) { return hash(key.hashCode()) % capacity; }
我需要密鑰哈希碼的散列函數。
我在Java中編寫我的HashMap實現。我使用開放尋址來解決衝突。爲了更好的密鑰分發,我想使用一個很好的哈希函數來獲得密鑰的哈希碼。我不知道什麼散列函數更好?什麼散列函數更好?
public int getIndex(K key) { return hash(key.hashCode()) % capacity; }
我需要密鑰哈希碼的散列函數。
使用% 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()函數沒有什麼可以做的。
任何分配您希望均勻接收的值的散列都是一個很好的散列函數。
您的目標是最大限度地提高性能(當然,在保持正確性的同時最大化性能)。主要關心的是儘量減少桶碰撞。這意味着理想的哈希是針對您的輸入數據量身打造的 - 如果您知道您會收到什麼,您可以選擇哈希產生最小數量的衝突,甚至可以實現緩存最佳訪問模式。
然而,這通常不是一個現實的選擇,所以你只需選擇一個散列,其輸出是無偏且不可預測的(其行爲像一個僞隨機數生成器,但具有確定性)。一些這樣的功能是「雜音」散列族。
你的問題並不十分清楚。你是否重新實現了HashMap(爲什麼?)或爲希望用作HashMap鍵的類編寫hashCode()方法?在你的示例中,你爲什麼要重新哈希密鑰提供的hashCode? – 2012-02-04 07:04:20