通過研究字典的底層實現(xiàn)，我們找到了字典快速且高效的秘密，就是哈希表。而提到哈希表，必然繞不開哈希值，因為它決定了映射之后的索引。

如果想計算對象的哈希值，那么要保證對象必須是可哈希的。如果不可哈希，那么它就無法計算哈希值，自然也就無法作為字典的 key。那什么樣的對象是可哈希的呢？

• 因為哈希值不能發(fā)生改變，所以對象必須是不可變對象；
• 當(dāng)對象的哈希值相等時，要判斷對象是否相等，所以對象必須實現(xiàn) __eq__ 方法；

所以如果對象滿足不可變、并且實現(xiàn)了 __eq__ 方法，那么它就是可哈希的，只有這樣的對象才能作為字典的 key 或者集合的元素。

像整數(shù)、浮點(diǎn)數(shù)、字符串等內(nèi)置的不可變對象都是可哈希的，可以作為字典的 key。而像列表、字典等可變對象則不是可哈希的，它們不可以作為字典的 key。然后關(guān)于元組需要單獨(dú)說明，如果元組里面的元素都是可哈希的，那么該元組也是可哈希的，反之則不是。

# 鍵是可哈希的就行，值是否可哈希則沒有要求
d = {1: 1, "xxx": [1, 2, 3], 3.14: 333}

# 列表是可變對象，因此無法哈希
try:
    d = {[]: 123}
except TypeError as e:
    print(e)
    """
    unhashable type: 'list'
    """

# 元組也是可哈希的
d = {(1, 2, 3): 123}

# 但如果元組里面包含了不可哈希的對象
# 那么整體也會變成不可哈希對象
try:
    d = {(1, 2, 3, []): 123}
except TypeError as e:
    print(e)
    """
    unhashable type: 'list'
    """

而我們自定義類的實例對象也是可哈希的，并且哈希值是通過對象的地址計算得到的。

class Some:
    pass

s1 = Some()
s2 = Some()
print(hash(s1), hash(s2))
"""
8744065697364 8744065697355
"""

當(dāng)然 Python 也支持我們重寫哈希函數(shù)，比如：

class Some:

    def __hash__(self):
        return 123

s1 = Some()
s2 = Some()
print(hash(s1), hash(s2))
"""
123 123
"""
print({s1: 1, s2: 2})
"""
{<__main__.Some object at 0x0000029C0ED045E0>: 1, 
 <__main__.Some object at 0x0000029C5E116F20>: 2}
"""

因為哈希值一樣，映射出來的索引自然也是相同的，所以在作為字典的 key 時，會發(fā)生沖突。由于類的實例對象之間默認(rèn)不相等，因此會改變規(guī)則重新映射，找一個可以寫入的位置。

如果兩個對象相等，它們的哈希值一定也相等。

注意：我們自定義類的實例對象默認(rèn)都是可哈希的，但如果類里面重寫了 __eq__ 方法，且沒有重寫 __hash__ 方法的話，那么這個類的實例對象就不可哈希了。

class Some:

    def __eq__(self, other):
        return True

try:
    hash(Some())
except TypeError as e:
    print(e)
    """
    unhashable type: 'Some'
    """

為什么會有這種現(xiàn)象呢？首先上面說了，在沒有重寫 __hash__ 方法的時候，哈希值默認(rèn)是根據(jù)對象的地址計算得到的。而且對象如果相等，那么哈希值一定是一樣的，并且不可變。

但我們重寫了 __eq__，相當(dāng)于控制了 == 操作符的比較結(jié)果，兩個對象是否相等就由我們來控制了，可哈希值卻還是根據(jù)地址計算得到的。因為兩個對象地址不同，所以哈希值不同，但是對象卻可以相等、又可以不相等，這就導(dǎo)致了矛盾。所以在重寫了__eq__、但是沒有重寫 __hash__ 的情況下，其實例對象便不可哈希了。

但如果重寫了 __hash__，那么哈希值就不再通過地址計算了，因此此時是可以哈希的。

class Some:

    def __eq__(self, other):
        return True

    def __hash__(self):
        return 123

s1 = Some()
s2 = Some()
print({s1: 1, s2: 2})
"""
{<__main__.Some object at 0x00000202D7D945E0>: 2}
"""

我們看到字典里面只有一個元素，因為重寫了 __hash__ 方法之后，計算得到的哈希值都是一樣的。如果沒有重寫 __eq__，實例對象之間默認(rèn)是不相等的，因此哈希值一樣，但是對象不相等，那么會重新映射。但我們重寫了 __eq__，返回的結(jié)果是 True，所以 Python 認(rèn)為對象是相等的，那么由于 key 的不重復(fù)性，只會保留一個鍵值對。

但需要注意的是，在比較相等時，會先比較地址是否一樣，如果地址一樣，那么哈希表會直接認(rèn)為相等。

class Some:

    def __eq__(self, other):
        return False

    def __hash__(self):
        return 123

    def __repr__(self):
        return "Some Instance"

s1 = Some()
# 我們看到 s1 == s1 為 False
print(s1 == s1)
"""
False
"""
# 但是只保留了一個 key，咦，兩個 key 不相等，難道不應(yīng)該重新映射嗎？
# 原因就是剛才說的，在比較是否相等之前，會先判斷地址是否一樣
# 如果地址一樣，那么認(rèn)為是同一個 key，直接判定相等
print({s1: 1, s1: 2})
"""
{Some Instance: 2}
"""

s2 = Some()
# 此時會保留兩個 key，因為 s1 和 s2 地址不同，s1 == s2 也為 False
# 所以哈希表認(rèn)為這是兩個不同的 key
# 但由于哈希值一樣，那么映射出來的索引也一樣
# 因此寫入 s2: 2 時相當(dāng)于發(fā)生了索引沖突，于是會重新映射
# 但總之這兩個 key 都會被保留
print({s1: 1, s2: 2})  
"""
{Some Instance: 1, Some Instance: 2}
"""

同樣的，我們再來看一個 Python 字典的例子。

d = {1: 123}

d[1.0] = 234
print(d)  # {1: 234}

d[True] = 345
print(d)  # {1: 345}

天哪嚕，這是咋回事？首先整數(shù)在計算哈希值的時候，得到的結(jié)果就是其本身；而浮點(diǎn)數(shù)顯然不是，但如果浮點(diǎn)數(shù)的小數(shù)點(diǎn)后面是 0，那么它和整數(shù)是等價的。

因此 3 和 3.0 的哈希值一樣，并且兩者也是相等的，因此它們被視為同一個 key，所以相當(dāng)于是更新。同理 True 也一樣，因為 bool 繼承自 int，所以它等價于 1，比如：9 + True = 10。因此 True 和 1 相等，并且哈希值也相等，那么索引 d[True] = 345 同樣相當(dāng)于更新。

但是問題來了，值更新了我們可以理解，字典里面只有一個元素也可以理解，可為什么 key 一直是 1 呢？理論上最終結(jié)果應(yīng)該是 True 才對啊。

其實這算是 Python 偷了個懶吧（開個玩笑），因為 key 的哈希值是一樣的，并且也相等，所以只會更新 value，而不會修改 key。

從字典在設(shè)置元素的時候我們也知道，如果將 key 映射成索引之后，發(fā)現(xiàn)哈希索引數(shù)組的槽沒有人用，那么就按照先來后到的順序?qū)㈡I值對存儲在鍵值對數(shù)組中，再把它在鍵值對數(shù)組中的索引存在哈希索引數(shù)組的指定槽中。

但如果發(fā)現(xiàn)槽有人用了，那么根據(jù)槽里面存的索引，去鍵值對數(shù)組中查找指定的 entry，然后比較兩個 key 是否相等。如果對應(yīng)的 key 不相等，則重新映射找一個新的槽；如果相等，則說明是同一個 key，那么把 value 換掉即可。

所以在替換元素的整個過程中，根本沒有涉及到對鍵的修改，因此在上面那個例子中，value 會變、但 key 始終是 1，而不是 True。

為了加深理解，我們再舉個例子：

d = {"高老師": 666}

class A:
    def __hash__(self):
        return hash("高老師")

    def __eq__(self, other):
        return True

# A() == "高老師" 為 True，兩者哈希值也一樣
# 所以相當(dāng)于對 key 進(jìn)行更新
d[A()] = 777
print(d)  # {'高老師': 777}

print(d["高老師"])  # 777
print(d[A()])  # 777

只要兩個對象相等，并且哈希值相等，那么對于哈希表來說，它們就是同一個 key。

另外我們反復(fù)在提哈希值，而哈希值是通過哈希函數(shù)運(yùn)算得到的，一個理想的哈希函數(shù)要保證哈希值盡量均勻地分布于整個哈希空間中，越是相近的值，其哈希值差別應(yīng)該越大。還是那句話，哈希函數(shù)對哈希表的好壞起著至關(guān)重要的作用。

以上我們就詳細(xì)地聊了聊對象的哈希值，如果對象可以計算哈希值，那么它一定實現(xiàn)了 __hash__ 方法，而內(nèi)置的不可變對象都實現(xiàn)了。

事實上內(nèi)置的哈希函數(shù) hash，本質(zhì)上也是調(diào)用了 __hash__。

print(hash("hello"))
print("hello".__hash__())
"""
-7465190714692855315
-7465190714692855315
"""