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

Python012

Python数据结构与算法-哈希map的实现及原理,第1张

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的对象。

代码如下:

       一个简单的例子:将一个list中所有元素平方,常规的做法如下图所示,虽然实现了这个功能,但并没有给人一目了然的感觉。若换成map来实现,则会好很多。

1、map函数介绍及其简单使用

上述用一个简单的例子演示的map函数的用法及其优势,下面将详细介绍map函数的用法:map()函数接收两个参数,一个是函数,一个是Iterable,map将传入的函数依次作用到序列的每一个元素,并把结果作为新的Iterable返回。其语法格式为:

                                                        map(function,iterable...)

                                                        function---函数名

                                                        iterable---一个或多个序列

map作为高阶函数,事实上它把运算规则抽象了,我们可以用这种方式计算任意复杂的函数,再比如,把一个list的所有数据转为string类型:

再举一个小例子,对list中的各个元素开方,一步到位:

!注意:在使用math自带函数时,只需要函数名即可

2、map函数与lambda函数结合使用,下面方法同样可以达到对list中的数二次方的目的

map函数与lambda函数结合使用,可以传入两个参数相加:

还可以同时计算多个值: