奇怪的Python設置和哈希行爲 - 這是如何工作的？

我有一個叫GraphEdge的類，我希望通過它的tail和head成員在集合（內置set類型）中唯一地定義它，這些成員通過__init__進行設置。奇怪的Python設置和哈希行爲 - 這是如何工作的？

如果我沒有定義__hash__，我看到了以下行爲：

>>> E = GraphEdge('A', 'B') 
>>> H = GraphEdge('A', 'B') 
>>> hash(E) 
139731804758160 
>>> hash(H) 
139731804760784 
>>> S = set() 
>>> S.add(E) 
>>> S.add(H) 
>>> S 
set([('A', 'B'), ('A', 'B')])

set沒有辦法知道E和H是由我的定義是相同的，因爲他們有不同的哈希值（這是就我所知，集合類型用於確定唯一性），因此它將兩者都作爲獨特的元素添加。所以我定義了一個比較幼稚的散列函數GraphEdge像這樣：

def __hash__(self): 
    return hash(self.tail)^hash(self.head)

現在上面按預期工作：

>>> E = GraphEdge('A', 'B') 
>>> H = GraphEdge('A', 'B') 
>>> hash(E) 
409150083 
>>> hash(H) 
409150083 
>>> S = set() 
>>> S.add(E) 
>>> S.add(H) 
>>> S 
set([('A', 'B')])

在這種情況下

但顯然，('A', 'B')和('B', 'A')將返回相同的哈希值，所以我希望我不能將('B', 'A')添加到已包含('A', 'B')的集合中。但是，這是不是發生了什麼：

>>> E = GraphEdge('A', 'B') 
>>> H = GraphEdge('B', 'A') 
>>> hash(E) 
409150083 
>>> hash(H) 
409150083 
>>> S = set() 
>>> S.add(E) 
>>> S.add(H) 
>>> S 
set([('A', 'B'), ('B', 'A')])

所以是使用散列或不設置的類型？如果是這樣，最後的情況怎麼可能？如果不是，爲什麼第一種情況（沒有定義__hash__）工作？我錯過了什麼嗎？

編輯：爲未來的讀者參考，我已經有__eq__定義（也可根據tail和head）。

來源

2010-01-29 ezod

你有散列衝突。在散列衝突時，集合使用==運算符來檢查它們是否真的彼此相等。

來源

2010-01-29 01:06:43

啊，這是有道理的。簡單地總是返回0作爲散列來強制設置使用==運算符會更好嗎？我看不到它比散列函數本身會引入更多的開銷。 – ezod 2010-01-29 01:10:56

確保每個單獨的對象都有一個散列衝突，這樣可以保證你的性能。哈希用於在集合內部創建對象。 – 2010-01-29 01:14:31

@jleedev：注意，謝謝。現在使用更好的散列函數。 – ezod 2010-01-29 01:15:54

理解hash和==如何一起工作很重要，因爲兩者都被集合使用。對於x和y兩個值，重要的規則是：

x == y ==> hash(x) == hash(y)

（x等於y意味着x和y的散列值相等）。但是，反過來並不正確：兩個不相等的值可以具有相同的散列值。

集合（和字典）將使用散列來近似等式，但將使用真正的等式操作來確定兩個值是否相同。

來源

2010-01-29 01:12:05

如果您至少需要其中一個，則應始終同時定義__eq__()和__hash__()。如果兩個對象的哈希值相等，則會執行額外的__eq__()檢查來驗證唯一性。

來源

2010-01-29 01:12:34

奇怪的Python設置和哈希行爲 - 這是如何工作的？

回答

相關問題