Python数据结构与算法哈希map的实现及原理

　　1-collections.MutableMapping
　　1.1 概念：这是什么？
　　大家可能想知道这一串英文是什么意思？其实只需要了解在collections库当中有一个非常重要的抽象基类MutableMappin
　　g，专门用于实现map的一个非常有价值的工具。后边我们会用到它。
　　2-我们的map基类
　　2.1 实现这个类from collections import MutableMapping class Map(MutableMapping):     class _Item:         __slots__ = (＂_key＂, ＂_value＂)          def __init__(self, key, value):             self._key = key             self._value = value         def __eq__(self, other):             return self._key == other._key         def __ne__(self, other):             return not (self == other)# 由于重写了__eq__，所以对象可以直接比较了（这里的==会执行__eq__）         def __lt__(self, other):# 小于             return self._key < other._value         # 一下三个方法其实均由上边eq、ne、lt得出         def __le__(self, other):# 小于等于             return self len(self._table)//2:#双倍扩容，常用的扩容方法，在之前用列表实现队列中提及过。             self._resize(2*len(self._table)-1)# 动态扩容     def __getitem__(self, item):# 索引 item是键         num = self._hash_zip(item)         return self._bucket_getitem(num, item)     def __delitem__(self, key):# 按键删除：其实hash也是映射容器，所以直观体现的就是键值对，而不是桶数组。         num = self._hash_zip(key)         self._bucket_delitem(num,key)# 这是真正的在桶数组中删除该键所映射的桶码中的对应元组，set和get同理         self._n -= 1     def _resize(self, length):# 扩容         old = list(self.items())         self._table = [None for x in range(length)]         self._n = 0         for (k,v) in old:             self[k] = v
　　OK了，基本的哈希表就实现了，其实仔细想想很容易，但是自己要能实现还是要理解哈希表的本质哦，外加一定量的练习才可以熟练掌握，练习的目的就是为了熟练而已。
　　5-分离链表实现的具体哈希map类
　　说明：这玩意只是一种降低冲突的手段，上一节提过，降低冲突最好的地方是发生在元组进入桶的时候，所以想必大家猜到了，接下来的分离链表也就是为了self._bucket_xxxxxxx系列方法做准备。这里之所以在上边使用@abstractmethod就是为了继承实现，目的可以实现多种将冲突的哈希表。分离链表的概念上一节也有的。
　　＂见码入面＂（借鉴：见字如面这个电视节目，有兴趣可以看看，还不错的）：class ChainHashMap(HashMap):     def _bucket_getitem(self, hash_k, key):         bucket = self._table[hash_k]# 找到名字为hash_k的桶         if bucket is None:             raise KeyError(＂No such key in this hash_map＂)         return bucket[key]#桶中键为key的元组              def _bucket_setitem(self, hash_k, key, value):         if self._table[hash_k] is None:             self._table[hash_k] = UnsortedTableMap()#调用之前写的无序映射容器作为桶         oldsize = len(self._table[hash_k])# 插入元素前计算长度         self._table[hash_k][key] = value#_table[hash_k] 为其内部类_Item的对象，这里支持getitem方法，所以可以索引key         if len(self._table[hash_k]) > oldsize:#如果桶中新装了才加一，因为有可能是修改桶中元素，而非新增，修改的话_n不加1             self._n += 1      def _bucket_delitem(self, hash_k, key):# 这我感觉没啥好说的，很简单         bucket = self._table[hash_k]         if bucket is None:             raise KeyError(＂No such key in this hash_map＂)         self._table.remove(bucket)      def __iter__(self):         for bucket in self._table:#遍历桶数组中所有的桶             if bucket is not None:# 如果桶非空则                 for item in bucket:# 遍历非空桶中的元素,                                     # 桶为UnsortedTableMap的对象，而桶中的键值对又为其父类Map的内置类_Item的对象                     yield item
　　6-用线性探测处理冲突的哈希map类
　　这种方式的好处不需要再去借助其他额外的赋值结构来表示桶。结构更加简单。不会再像上一种方法还要让桶是一个UnsortedTableMap的对象。
　　代码如下：class LineCheckMap(HashMap):     _FLAG = object()# 哨兵，或称标志位，主要用来描述某种特定的状态，     # 而在这里这个哨兵是为将删除的元素标志为其哨兵，减少删除带来的不必要的麻烦     # 其实用其他类型的值也行，这里只是为了和其他值区分     # 因为如下第一个可用桶要求是处女桶，导致那些被标志过得桶将会造成空间浪费。      def _is_avail(self, buck_num):# 判断桶是否空的（可用的）         #                    空桶                              已经删除过的桶         return  self._table[buck_num] is None or self._table[buck_num] is LineCheckMap._FLAG      def _find_slot(self, buck_num, key):# 找到存储元素的槽         first_avail_slot = 0#标志位，表示第一个可用的空桶         while True:             if self._is_avail(buck_num):# 如果桶可用                 if first_avail_slot == 0:# 如果第一个可用空桶为0                     first_avail_slot = buck_num# 将标志位更新为当前可用桶号                 if self._table[buck_num] is None:# 如果没找到该桶，则：                     return (False, first_avail_slot)# 返回错误和第一可用桶号             elif key==self._table[buck_num]._key:# 如果找到了桶元素所匹配的键                 return (True, buck_num)# 返回真和这个键所在的桶             buck_num = (buck_num+1)%len(self._table)# 线性探测的根本，参考上一节的描述，             # 同时你还会发现，这个算法思路和之前循环列表实现队列的思路很像      def _bucket_delitem(self, hash_k, key):         found, s = self._find_slot(hash_k, key)         if not found:             raise KeyError(＂No such key in this hash_map!＂)         self._table[s] = LineCheckMap._FLAG# 标志着桶中元素被删除了      def _bucket_setitem(self, hash_k, key, value):         found, s = self._find_slot(hash_k, key)         if not found:# 新增桶             self._table[s] = self._Item(key, value)#Item是HashMap父类Map的内置类             self._n += 1         else:# 旧桶改值             self._table[s]._value = value      def _bucket_getitem(self, hash_k, key):         found, s = self._find_slot(hash_k,key)         if not found:             raise KeyError(＂No such Key in this hash_map＂)         return self._table[s]._value      def __iter__(self):         for item in range(len(self._table)):             if not self._is_avail(item):                 yield self._table[item]._key
　　这篇文章连写带讲解，费了4个小时的时间，真的是很少有机会能如此浸入式地写作，说明这篇内容确实还是有点东西的，整理加上反复咀嚼确实理解很有趣，很有意思，希望各位在我总结的基础上，好好理解下，毕竟如果你程序员做久了，这些东西都是大同小异基本固定的代码，但是数据结构和算法的重点在理解其实现原理，这个才是很重要的地方，不要走偏了，不要觉得会背或者记住了这一种代码，那是没用的，必须要理解，逐层慢慢理解，对于初学者，这篇文章静下心来可能需要10个小时左右去理解和挖掘，所以每一步我都会尽我所能把我理解的传输给各位，但是理解难免有不同之处，每个人看事物的方式都不同，所以各位，尽量看，尽量理解，不要在意那些错别字，这个不是重点。如果究其有几个错别字，那我建议还是学文学吧。声明，上文中提及的代码都是有固定套路的，不存在谁抄袭谁的问题，要是了解过一点数据结构的，一眼就能看出代码是套路化的东西，重点请仔细理解我写的每句注释！！！这个很重要，方便你们真的理解这个概念，数据结构，本来在乎的就不是代码怎么写，在乎的都是，你是否有这种数据结构的蓝图在脑海中，随时可以即兴提笔来上一段自己的sao操作，这就是编程的乐趣。