對於普通程序員是否有「足夠好」的散列函數？

我們被告知我們應該爲我們的類實現hashCode（），但像我這樣的大多數人並沒有真正的想法來知道如何做到這一點，或者如果我們弄錯了會發生什麼。例如，我需要一個散列函數來索引樹中的節點（Finding the most frequent subtrees in a collection of (parse) trees）。在這種情況下，我需要基於有序的子節點遞歸地生成哈希碼，例如，對於普通程序員是否有「足夠好」的散列函數？

hashCode = function(child1.hashCode, child2.hashCode, ...)

在散列碼答案的recent discussion包含字符串的哈希（基於長素和31），也bitshifting。字符串散列是：

// adapted from String.hashCode() 
public static long hash(String string) { 
    long h = 1125899906842597L; // prime 
    int len = string.length(); 

    for (int i = 0; i < len; i++) { 
    h = 31*h + string.charAt(i); 
    } 
    return h; 
}

我對安全性不感興趣，不介意碰撞。是否有一種「通用函數」，用於組合有序對象的哈希碼，這些有用對象的做法比有害更好（並且比根本不調用它更好）？

也有一個網站，我們可以查找常見情況？字符串，列表等）

我沒有指定一種語言，因爲我希望有通用的方法。但是，如果它是嚴肅語言特定的，那麼請說明語言以及它爲什麼不通用。

UPDATE兩個建議是使用IDE的hashCode生成器。這似乎是一個很好的默認;這裏的Netbeans：

public int hashCode() { 
    int hash = 5; 
// objects 
    hash = 97 * hash + (this.rootElement != null ? this.rootElement.hashCode() : 0); 
    hash = 97 * hash + (this.tableElement != null ? this.tableElement.hashCode() : 0); 
// a string 
    hash = 97 * hash + (this.tag != null ? this.tag.hashCode() : 0); 
    return hash; 
}

來源

2009-11-06 peter.murray.rust

在Joshua Bloch的Effective Java中有一個很好的hashCode（）。示例第3章「所有對象通用的方法」是免費的（當然，它曾經在Sun的舊網站上有一個頁面可用，如果搜索，你仍然可以找到該章節的PDF版本某處）。

您也可以在Apache Commons Lang中查看HashCodeBuilder的源代碼，但不要在沒有引用它的情況下複製它。現在花時間去了解這一點 - 它會讓你成爲一個更好的人。

來源

2009-11-06 19:45:40 dustmachine

這看起來是我想要的。要共享引用：。「此類使任何類中樹立了良好的hashCode方法它遵循的書有效的Java由約書亞布洛赫所設定的規則寫一個好的hashCode方法實際上是相當困難的這個類的目的是簡化這個過程。「我懷疑這會讓我成爲一個更好的人（雖然我關心作者的精神權利），但我希望它會讓我更好的程序員... – 2009-11-06 19:59:09

因爲布洛赫的做法是接受什麼，我一直在尋找 – 2009-11-08 12:00:29

不幸的是，這些鏈接現在已經死亡。 :( – Skrylar 2013-05-06 03:06:47

如果你在Windows上，你可以使用HashData()。

來源

2009-11-06 19:44:22

好吧，所以它是Java，所以沒關係。 – 2009-11-06 19:47:24

這將如何在C＃類中使用？ – 2009-11-06 19:47:29

我很高興知道C＃ - 我沒有特別指定Java，並且我推測這裏有獨立於語言的方法。 – 2009-11-06 19:48:52

雖然缺少標籤，但我會假設你正在談論Java。

一個「懶惰」的解決方案與Eclipse 3.5打包在一起，只需按一下按鈕，它就會生成哈希碼。 toString（）和equals（）。非常好！我懷疑你可以在IDEA和NetBeans中找到類似的功能。

除此之外，實際上任何對相同輸入始終產生相同值的散列函數都可以。這（可能）只會影響像HashMaps這樣的東西的效率。

來源

2009-11-06 19:45:34

對於一些常見的情況，您可以查看Sun的JDK代碼。如果我沒有記錯的話，對於字符串，它只是保持乘以37並添加下一個字符的int值。對於列表，我認爲它做了類似的事情，將結果乘以某個素數並添加（或異或）下一個對象的哈希碼。 – 2009-11-06 19:47:47

如果您正在爲自定義類定義哈希碼，最好的方法是定義您的所有字段哈希碼函數的某種數學級聯。

在定義哈希碼時，您的目標通常是最小化碰撞，所以如果您這樣做，您通常會清楚。

hashcode=(field1.hashcode()*7)+(field2.hashcode()*3)+(field3.hashcode()*51)...

來源

2009-11-06 19:48:46 tinkertime

你應該確保乘數是素數而不是非素數（特別是不是2的冪數） – AlBlue 2009-11-06 19:50:38

這就是我所追求的數字有什麼神奇的嗎 – 2009-11-06 19:52:02

謝謝AlBlue，乘數應始終是好的，總理，進一步降低碰撞次數 – tinkertime 2009-11-06 19:55:02

在任何託管環境中，對象散列函數的原始實現都是內存地址本身。如果你不關心散列函數的屬性，只要表示相同值的單獨實例之間存在某種等價關係，就可以使用任何值。

如果您熟悉關係數據庫設計，想想你的對象的主鍵？什麼樣的價值構成了主要關鍵？

說，這是a, b and c，好了，那麼你的hashCode的實現應該是這樣的

return a.hashCode()^b.hashCode()^c.hashCode();

^是XOR（異或）逐位操作，這樣你就可以鏈在一起的任何數量的值形成一個散列值，並且仍然保持良好的分佈。

來源

2009-11-06 19:54:17

「散列函數的內存地址」 - ？你確定這個怎麼樣當對象在內存中四處移動它被壓縮時 – mfeingold 2009-11-06 19:56:59

多達是合理實用的，類Object定義的hashCode方法爲不同的對象返回不同的整數（這通常通過將對象的內部地址轉換爲整數來實現，但JavaTM編程語言不需要此實現技術。） - http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Object.html#h ashCode％28％29 – 2009-11-06 20:03:24

我把從Java文檔，它的默認實現，並且這將意味着新的對象（）。hashCode（）方法！=新的對象（）。hashCode（）方法 – 2009-11-06 20:04:36

要回答你的問題可以出現什麼問題：你的函數生成的哈希碼將被用來找到你的類的地方，如果你把它放在一個哈希表（詞典/圖）。如果你的散列函數產生太多的衝突，你的散列表的性能可能和O（n）一樣糟糕。

來源

2009-11-06 19:55:10 mfeingold

這是一個哈希碼組合功能，我使用（在C＃）：

public static int CombineHashCodes(params int[] hashCodes) 
{ 
    unchecked 
    { 
     var result = 0; 
     foreach (var hash in hashCodes) 
      result = (result * 397)^hash; 
     return result; 
    } 
}

直觀的理由是，該組合方面是XOR運算符。這是如何.NET 4它爲元組：

public static int CombineHashCodes(int h1, int h2) 
{ 
    return ((h1 << 5) + h1)^h2; 
}

來源

2009-11-06 20:15:15 eulerfx

對於普通程序員是否有「足夠好」的散列函數？

回答

相關問題