1-collections.MutableMapping
易縣ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：028-86922220（備注：SSL證書合作）期待與您的合作！
1.1 概念：這是什么？
大家可能想知道這一串英文是什么意思？其實只需要了解在collections庫當(dāng)中有一個非常重要的抽象基類MutableMappin
g，專門用于實現(xiàn)map的一個非常有價值的工具。后邊我們會用到它。
2-我們的map基類
2.1 實現(xiàn)這個類
這個基類其實也就是確定了鍵值對的屬性，并且存儲了基本的比較方法。它的對象就是一個鍵值對咯。這個很好理解。有點類似object的感覺。
3-通過map基類實現(xiàn)的無序映射
給大家看一個上邊的例子，這個例子來源于網(wǎng)絡(luò)，自己改了改，能用，更加詳細(xì)而已，湊合看.
4-Python哈希表的實現(xiàn)的基類
4.1 咱有話直說：上才（代）藝（碼）
如果還不知道哈希表概念的同xio，請參考 python進(jìn)階之?dāng)?shù)據(jù)結(jié)構(gòu)與算法–中級-哈希表（小白piao分享） 。廢話不多說，咱們擼代碼：
OK了，基本的哈希表就實現(xiàn)了，其實仔細(xì)想想很容易，但是自己要能實現(xiàn)還是要理解哈希表的本質(zhì)哦，外加一定量的練習(xí)才可以熟練掌握，練習(xí)的目的就是為了熟練而已。
5-分離鏈表實現(xiàn)的具體哈希map類
說明：這玩意只是一種降低沖突的手段，上一節(jié)提過，降低沖突最好的地方是發(fā)生在元組進(jìn)入桶的時候，所以想必大家猜到了，接下來的分離鏈表也就是為了self._bucket_xxxxxxx系列方法做準(zhǔn)備。這里之所以在上邊使用@abstractmethod就是為了繼承實現(xiàn)，目的可以實現(xiàn)多種將沖突的哈希表。分離鏈表的概念上一節(jié)也有的。
“見碼入面”（借鑒：見字如面這個電視節(jié)目，有興趣可以看看，還不錯的）：
6-用線性探測處理沖突的哈希map類
這種方式的好處不需要再去借助其他額外的賦值結(jié)構(gòu)來表示桶。結(jié)構(gòu)更加簡單。不會再像上一種方法還要讓桶是一個UnsortedTableMap的對象。
代碼如下：
可哈希 就是可以用python內(nèi)置函數(shù) hash 得出哈希值。
對任意對象 o，如果 o.__hash__() 返回一個整型值，那 o 就是可哈希的。
各種標(biāo)量、tuple、正確實現(xiàn)了 __hash__ 函數(shù)的類的實例都是可哈希的。
哈希表: 是一個很容易就能便捷的定位到元素的一個集合，通常會被稱為槽，每個槽都可以存放一個元素。
hash函數(shù): 元素與元素所屬的槽之間的映射關(guān)系稱為hash函數(shù)。item % len(list)，集合的元素乘除哈希表的長度。
哈希(Hash)算法：`hash（object）`
哈希算法將一個不定長的輸入，通過散列函數(shù)變換成一個定長的輸出，即散列值。是一種信息摘要算法。對象的hash值比原對象擁有更低的內(nèi)存復(fù)雜度。
它不同于加密。哈希（hash）是將目標(biāo)文本轉(zhuǎn)換成具有相同長度的，不可逆的雜湊字符串，而加密則是將文本轉(zhuǎn)換為具有相同長度的，可逆的密文。
哈希（hash）算法是不可逆的，只能由輸入產(chǎn)生輸出，不能由輸出產(chǎn)生輸入。而加密則是可逆的。即可以從輸入產(chǎn)生輸出，也可以反過來從輸出推出輸入。
對于hash算法，不同的數(shù)據(jù)應(yīng)該生成不同的哈希值。如果兩個不同的數(shù)據(jù)經(jīng)過Hash函數(shù)計算得到的Hash值一樣。就稱為哈希碰撞（collision）。哈希碰撞無法被完全避免。只能降低發(fā)生概率。
好的hash函數(shù)會導(dǎo)致最少的hash碰撞。
*
可哈希性（hashable）：
可哈希的數(shù)據(jù)類型為不可變的數(shù)據(jù)結(jié)構(gòu)（如字符串srt，元組tuple，對象集objects等）。這種數(shù)據(jù)被稱為可哈希性。
不可哈希性：
不可哈希的數(shù)據(jù)類型，為可變的數(shù)據(jù)結(jié)構(gòu)（如字典dict，列表list和集合set等）。
如果對可變的對象進(jìn)行哈希處理，則每次對象更新時，都需要更新哈希表。這樣我們則需要將對象移至不同的數(shù)據(jù)集，這種操作會使花費過大。
因此設(shè)定不能對可變的對象進(jìn)行hash處理。
**
**
Python3.x添加了hash算法的隨機(jī)性，以提高安全性，因此對于每個新的python調(diào)用，同樣的數(shù)據(jù)源生成的結(jié)果都將不同。
哈希方法有（MD5, SHA1, SHA256與SHA512等）。常用的有SH256與SHA512。MD5與SHA1不再常用。
- MDH5 (不常用)
- SHA1 (不常用)
- SHA256 (常用)
- SHA512 (常用)
一種局部敏感的hash算法，它產(chǎn)生的簽名在一定程度上可以表征原內(nèi)容的相似度。
可以被用來比較文本的相似度。
安裝simhash：
Pip3 install simhash
感知哈希算法（perceptual Hash Algorithm）。用于檢測圖像和視頻的差異。
安裝Imagehash:
pip3 install Imagehash
比較下面兩張圖片的Imagehash值
可以看到兩張圖片的hash值非常相似。相似的圖片可以生成相似的哈希值是Imagehash的特點。
Python中字符串是可哈希的，即可以作為字典的鍵或者HashTable的鍵使用。
您可以這樣子使用Python內(nèi)置函數(shù)hash（散列函數(shù)）：
您也可以將字符串轉(zhuǎn)為一個集合：
總之，Python里面有很多內(nèi)置的hash功能性數(shù)據(jù)結(jié)構(gòu)和函數(shù)。
dict對象是Python中一個原始的數(shù)據(jù)類型，按照鍵值對的方式存儲，中文名為字典，其通過鍵名查找對應(yīng)的值有很高的效率，時間復(fù)雜度在常數(shù)級別O(1)。Python dict的底層是依靠哈希表(Hash Table)進(jìn)行實現(xiàn)的，使用開放地址法解決沖突。所以其查找的時間復(fù)雜度會是O(1)，why？
哈希表是key-value類型的數(shù)據(jù)結(jié)構(gòu)，通過關(guān)鍵碼值直接進(jìn)行訪問。通過散列函數(shù)進(jìn)行鍵和數(shù)組的下標(biāo)映射從而決定該鍵值應(yīng)該放在哪個位置，哈希表可以理解為一個鍵值需要按一定規(guī)則存放的數(shù)組，而哈希函數(shù)就是這個規(guī)則。
算法中時間和空間是不能兼得的，哈希表就是一種用合理的時間消耗去減少大量空間消耗的操作，這取決于具體的功能要求。
創(chuàng)建一個數(shù)組，數(shù)組下標(biāo)是索引號，數(shù)組中的值是要獲得的數(shù)據(jù)，這樣只需要O(1)的時間復(fù)雜度就可以完成操作，但是擴(kuò)展性不強(qiáng)，有以下兩個方面的考慮：
-1- 新添加的元素超出數(shù)組索引范圍，這就需要重新申請數(shù)組進(jìn)行遷移操作。
-2- 假設(shè)一種極端的情況：只存在兩個元素，索引號分別是1和100000000001，按照先前的設(shè)計思路，會浪費很大的存儲空間。
會不會存在一個方法，為已有的索引創(chuàng)建新的索引，通過壓縮位數(shù)，讓新索引可以和原有的大范圍的稀疏索引進(jìn)行一一對應(yīng)，新索引所需要的存儲空間要大大減小，這就是哈希思想。
上面的例子中哈希函數(shù)的設(shè)計很隨意，但是從這個例子中我們也可以得到信息：
哈希函數(shù)就是一個映射，因此哈希函數(shù)的設(shè)定很靈活，只要使得任何關(guān)鍵字由此所得的哈希函數(shù)值都落在表長允許的范圍之內(nèi)即可；
因為新的索引對舊的索引進(jìn)行了空間上的壓縮，所以不可能所有的輸入都只對應(yīng)唯一一個輸出，也就是哈希函數(shù)式有可能發(fā)生沖突的，哈希函數(shù)不可能做成一對一的映射關(guān)系，其本質(zhì)是一個多對一的映射。
直接定址法：很容易理解，key=Value+C； 這個“C”是常量。Value+C其實就是一個簡單的哈希函數(shù)。
除法取余法： 很容易理解， key=value%C;解釋同上。
數(shù)字分析法：這種蠻有意思，比如有一組value1=112233，value2=112633，value3=119033，針對這樣的數(shù)我們分析數(shù)中間兩個數(shù)比較波動，其他數(shù)不變。那么我們?nèi)ey的值就可以是key1=22,key2=26,key3=90。
平方取中法。此處忽略，見名識意。
折疊法：這種蠻有意思,比如value=135790，要求key是2位數(shù)的散列值。那么我們將value變?yōu)?3+57+90=160，然后去掉高位“1”,此時key=60，哈哈，這就是他們的哈希關(guān)系，這樣做的目的就是key與每一位value都相關(guān)，來做到“散列地址”盡可能分散的目地。
當(dāng)兩個不同的數(shù)據(jù)元素的哈希值相同時，就會發(fā)生沖突。解決沖突常用的手法有2種：
開放地址法：
如果兩個數(shù)據(jù)元素的哈希值相同，則在哈希表中為后插入的數(shù)據(jù)元素另外選擇一個表項。當(dāng)程序查找哈希表時，如果沒有在第一個對應(yīng)的哈希表項中找到符合查找要求的數(shù)據(jù)元素，程序就會繼續(xù)往后查找，直到找到一個符合查找要求的數(shù)據(jù)元素，或者遇到一個空的表項。
鏈接法：
將哈希值相同的數(shù)據(jù)元素存放在一個鏈表中，在查找哈希表的過程中，當(dāng)查找到這個鏈表時，必須采用線性查找方法。
python的dict采用了哈希表，最低能在 O(1)時間內(nèi)完成搜索，在發(fā)生哈希沖突的時候采用的是開放尋址法。java的HashMap也是采用了哈希表實現(xiàn)，但是在發(fā)生哈希沖突的時候采用的是鏈接法。
重慶分公司
重慶分公司
