Python數據結構與演算法教程

㈠ python數據結構與演算法-哈希map的實現及原理

1-collections.MutableMapping

1.1 概念：這是什麼？

大家可能想知道這一串英文是什麼意思？其實只需要了解在collections庫當中有一個非常重要的抽象基類MutableMappin

g，專門用於實現map的一個非常有價值的工具。後邊我們會用到它。

2-我們的map基類

2.1 實現這個類

這個基類其實也就是確定了鍵值對的屬性，並且存儲了基本的比較方法。它的對象就是一個鍵值對咯。這個很好理解。有點類似object的感覺。

3-通過map基類實現的無序映射

給大家看一個上邊的例子，這個例子來源於網路，自己改了改，能用，更加詳細而已，湊合看.

4-Python哈希表的實現的基類

4.1 咱有話直說：上才（代）藝（碼）

如果還不知道哈希表概念的同xio，請參考 python進階之數據結構與演算法–中級-哈希表（小白piao分享） 。廢話不多說，咱們擼代碼：

OK了，基本的哈希表就實現了，其實仔細想想很容易，但是自己要能實現還是要理解哈希表的本質哦，外加一定量的練習才可以熟練掌握，練習的目的就是為了熟練而已。

5-分離鏈表實現的具體哈希map類

說明：這玩意只是一種降低沖突的手段，上一節提過，降低沖突最好的地方是發生在元組進入桶的時候，所以想必大家猜到了，接下來的分離鏈表也就是為了self._bucket_xxxxxxx系列方法做准備。這里之所以在上邊使用@abstractmethod就是為了繼承實現，目的可以實現多種將沖突的哈希表。分離鏈表的概念上一節也有的。
「見碼入面」（借鑒：見字如面這個電視節目，有興趣可以看看，還不錯的）：

6-用線性探測處理沖突的哈希map類

這種方式的好處不需要再去藉助其他額外的賦值結構來表示桶。結構更加簡單。不會再像上一種方法還要讓桶是一個UnsortedTableMap的對象。
代碼如下：