什麼是實現__hash __（）的正確和好方法？

Question

什麼是實施__hash__()的正確和好方法？

我在說的函數返回一個哈希碼，然後用來插入對象到哈希表又名字典。

由於__hash__()返回一個整數，用於將對象「裝箱」到散列表我假設返回的整數的值應該爲公共數據均勻分佈（以最小化衝突）。 獲取此類值的最佳做法是什麼？碰撞是一個問題嗎？ 在我的情況下，我有一個小類，它充當一個容器類，它包含一些整數，一些浮點數和一個字符串。

Answer 1

實現__hash__()的簡單而正確的方法是使用關鍵元組。這不會是一個專門的哈希值作爲快，但是如果你需要，那麼你或許應該實現C.

類型下面是一個使用密鑰散列和平等的例子：

class A(object): 
    def __key(self): 
     return (self.attr_a, self.attr_b, self.attr_c) 

    def __eq__(x, y): 
     return x.__key() == y.__key() 

    def __hash__(self): 
     return hash(self.__key()) 

此外，documentation of __hash__有更多信息，這在某些特定情況下可能很有價值。

Answer 2

取決於您返回的散列值的大小。這很簡單的邏輯，如果你需要返回一個基於四個32位整數散列的32位整數，你會得到衝突。

我喜歡位操作。像，下面的C僞代碼：

int a; 
int b; 
int c; 
int d; 
int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F); 

這樣的系統可以爲彩車工作過，如果你只是把他們作爲自己的位值而不是實際代表浮點值，也許更好。

對於字符串，我很少/不知道。

Answer 3

我可以嘗試回答你的問題的第二部分。

碰撞可能不是哈希碼本身，而是哈希碼映射到集合中的索引。例如，你的散列函數可以返回從1到10000的隨機值，但是如果你的散列表只有32個條目，你會在插入時發生衝突。

此外，我認爲衝突將由內部集合來解決，並且有許多方法可以解決衝突。最簡單的（也是最差的）是，如果在索引i處插入一個條目，則向我加1，直到找到一個空的點並插入爲止。檢索然後以相同的方式工作。這會導致對某些條目的檢索效率低下，因爲您可能有一個條目需要遍歷整個集合才能找到！

其他衝突解決方法通過在插入項目以擴散事件時移動散列表中的條目來減少檢索時間。這會增加插入時間，但假設您閱讀的內容比插入內容更多。還有一些方法可以嘗試並分支出不同的碰撞條目，從而使條目能夠聚集在一個特定的點上。另外，如果您需要調整集合的大小，您需要重新提供一切或使用動態哈希方法。

總之，根據你使用的散列碼你可能必須實現你自己的衝突解決方法。如果你沒有將它們存儲在一個集合中，那麼你可能會用一個散列函數，它只是在很大範圍內生成散列碼。如果是這樣，你可以確定你的容器比需要的大（當然越大越好），這取決於你的記憶問題。

這裏有一些鏈接，如果你有興趣更多：

coalesced hashing on wikipedia

維基百科也有各種衝突解決方法summary：

此外，「File Organization And Processing」的撒普涵蓋碰撞的很多解決方法廣泛。 IMO是哈希算法的一個很好的參考。

Answer 4

微軟研究院的Paul Larson研究了各種散列函數。他告訴我，

for c in some_string: 
    hash = 101 * hash + ord(c) 

工作出奇的很好的各種各樣的字符串。我發現類似的多項式技術適用於計算不同子域的散列。

Answer 5

約翰·米利金提出一個類似的解決方案：

class A(object): 

    def __init__(self, a, b, c): 
     self._a = a 
     self._b = b 
     self._c = c 

    def __eq__(self, othr): 
     return ((self._a, self._b, self._c) == 
       (othr._a, othr._b, othr._c)) 

    def __hash__(self): 
     return hash((self._a, self._b, self._c)) 

這種解決方案的問題是，hash(A(a, b, c)) == hash((a, b, c))。換句話說，散列與其關鍵成員的元組相沖突。也許這在實踐中經常不重要？

的Python documentation on __hash__建議使用類似XOR的子組件的哈希值相結合，這給了我們這樣的：

class B(object): 

    def __init__(self, a, b, c): 
     self._a = a 
     self._b = b 
     self._c = c 

    def __eq__(self, othr): 
     return (isinstance(othr, type(self)) 
       and (self._a, self._b, self._c) == 
        (othr._a, othr._b, othr._c)) 

    def __hash__(self): 
     return (hash(self._a)^hash(self._b)^hash(self._c)^
       hash((self._a, self._b, self._c))) 

獎勵：更強大的__eq__在那裏拋出的良好措施。

更新：正如Blckknght指出的那樣，更改a，b和c的順序可能會導致問題。我添加了一個額外的^ hash((self._a, self._b, self._c))來捕獲被哈希值的順序。如果要組合的值不能重新排列（例如，如果它們具有不同的類型，因此_a的值永遠不會被分配給_b或_c等），則可以移除該最終的^ hash(...)。