點選上方“機器學習與python集中營”，星标公衆号 重磅幹貨，第一時間送達
☞機器學習、深度學習、python全棧開發幹貨 作者：草yang年華 來源：個人原創
前言：我們經常會聽見很多的概念，哈希值，哈希表，可哈希對象，不可哈希對象，散清單，字典，映射，等等，那麼這麼多的概念後面到底又有什麼差別和聯系，它們的本質又是怎麼樣的，本此系列文章将針對這些概念進行說明，鑒于篇幅較多，本次系列文章将分為兩篇來說明，此為第二篇，會涉及到以下概念，可變對象mutable與不可變對象inmutable，可哈希hashable與不可哈希unhashable，為什麼字典dict的鍵Key一定要是可哈希的？
前一篇文章參考：https://blog.csdn.net/qq_27825451/article/details/102820692
一、可哈希對象與不可哈希對象的直覺了解
前提：能夠較好地了解什麼是可變對象mutable與不可變對象inmutable。以及明白哈希值value的唯一性。
1.1 什麼是可哈希(hashable)？
簡要的說可哈希的資料類型，即不可變的資料結構(數字類型(int，float，bool)字元串str、元組tuple、自定義類的對象)。
(1)為什麼不可變資料類型是可哈希hashable的呢？哈希有啥作用？
對于不可變類型而言，不同的值意味着不同的記憶體，相同的值存儲在相同的記憶體，如果将我們的不可變對象了解成哈希表中的Key,将記憶體了解為經過哈希運算的哈希值Value，這不正好滿足哈希表的性質嘛。如下：
當然了，這不是說哈希值就是id位址，這還是不一樣的，參見下面：
再看一個例子：
1.2 什麼是不可哈希(unhashable)？
同理，不可哈希的資料類型，即可變的資料結構 (字典dict，清單list，集合set)
對于可變對象而言，比如一個清單，更改清單的值，但是對象的位址本身是不變的，也就是說不同的Key,映射到了相同的Value，這顯然是不符合哈希值的特性的，即出現了哈希運算裡面的沖突。如下：
如果此時對a和b使用hash函數，則會出錯，如下：
TypeError: unhashable type: 'list'
總結：上面的說明僅僅是感性上的認識哦，并不是本質原因哈！
二、從實質上來了解hashable和unhashable對象
2.1 什麼是hashable(可哈希性)
An object is hashable if it has a hash value which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__()or __cmp__() method). Hashable objects which compare equal must have the same hash value.
如果一個對象是可哈希的,那麼在它的生存期内必須不可變(而且該對象需要一個哈希函數),而且可以和其他對象比較(需要比較方法).比較值相同的對象一定有相同的哈希值，即一個對象必須要包含有以下幾個魔術方法：
- __eq__():用于比較兩個對象是否相等
- __cmp__():用于比較兩個對象的大小關系，它與__eq__隻要有一個就可以了
- __hash__()：實際上就是哈希函數(散列函數)，傳回經過運算得到的哈希值
前面既然說了整數int是可哈希對象，不放我們看一下它具不具備這幾個魔術方法：
我們發現他的确具有上面說的這幾個魔術方法。
清單是不可哈希的，我們看一下清單的魔術方法有哪一些：
In [54]: a=[1,2,3]
In [55]: dir(a)
Out[55]:
[...
'__eq__',
...
'__hash__',
...
']
我們發現一個問題，為什麼可變對象list明明是不可哈希的，為什麼也有着兩個方法呢？
因為所有類型的基類object中實作了這兩個魔術方法，但是并不是說有這兩個方法就一定是可哈希的，關鍵是要如何實作__eq__()方法和__hash__()方法，list并沒有實作，隻是有這幾個魔術方法而已，在實作的裡面出發了上面的異常。我們可以看一下基類object的魔術方法，如下：
2.2 自定義類型的對象是不是可哈希的呢？
看一下如下代碼：
我們發現自定義的類的對象是可哈希的，雖然我們不知道這個哈希值是如何得到的，但是我們知道他的确是可哈希對象。
前面說了哈希值的計算實際上是通過__hash__魔術方法來實作的，我們不妨自定義一下類的魔術方法，如下：
現在對于什麼是python的可哈希對象和哈希函數如何實作應該有了比較清楚的了解了。
三、為什麼字典 key 必須是不可變的(可哈希hashable)？
3.1 字典如何在 CPython 中實作？
CPython 的字典實作為可調整大小的哈希表。與 B-樹相比，這在大多數情況下為查找(目前最常見的操作)提供了更好的性能，并且實作更簡單。
字典的工作方式是使用 hash() 内置函數計算字典中存儲的每個鍵的 hash 代碼。hash 代碼根據鍵和每個程序的種子而變化很大；例如，"Python" 的 hash 值為-539294296，而"python"(一個按位不同的字元串)的 hash 值為 1142331976。然後，hash 代碼用于計算内部數組中将存儲該值的位置。假設您存儲的鍵都具有不同的 hash 值，這意味着字典需要恒定的時間 -- O(1)，用 Big-O 表示法 -- 來檢索一個鍵。
3.2 字典 key 必須是不可變的(可哈希hashable)
字典的哈希表實作使用從鍵值計算的哈希值來查找鍵。
(1)為什麼可變對象不能作為鍵Key？
先來看一個簡單的例子：
為什麼會觸發異常呢？哈希按其位址(對象 id)列出的。在上面的兩行代碼中，第一行中的key是一個清單對象[1,2],第二行中要通路的的時候的那個key雖然也是[1,2]，但是由于清單list是可變對象，雖然這兩行的清單值一樣，但是他們并不是同一個對象，它們的存儲位址是不一樣的，即id是不一樣的，id不一樣也導緻了根據id計算得到的哈希值是不一樣的，自然沒有辦法找到原來的那一個[1,2]的哈希值在哪裡了。
注意：這需要能夠很好的了解可變對象與不可變對象的記憶體配置設定才好哦！
(2)為什麼不可變對象能作為鍵Key？
将上面例子中的清單[1,2]換成元組(1,2)，先來看一個簡單的例子：
為什麼這裡不會觸發異常呢？哈希按其位址(對象 id)列出的。在上面的兩行代碼中，第一行中的key是一個元組對象(1,2)，第二行中要通路的的時候的那個key也是(1,2)，但是由于元組tuple是不可變對象，那麼這兩行的元組值一樣，是以它們的存儲位址是一樣的，即id是一樣的，id一樣也導緻了根據id計算得到的哈希值是一樣的，哈希值一樣我自然可以搜尋得到那個100在哪個地方了。
(3)總結：
字典的key一定要是不可變對象，要是能夠哈希的對象，即hashable對象，包括：
數字類型(int，float，bool)字元串str、元組tuple、自定義類的對象，這幾類，比如下面的字典：
● 學習筆記：深度學習中的正則化
● 2019：全球十大突破性技術
● 深度神經網絡經典模型結構-shufflenet系列
● Python 63個内置函數(上篇)，你都ok嗎？
● 【用python玩花樣】python實作點陣字型
● python十道經典面試題，測試你的python功底！
機器學習與python集中營
有趣的靈魂在等你
長按掃碼可關注
你點的每個贊，我都認真當成了喜歡