用Python实现数据结构之映射

发布时间：2020-05-27 11:04:33 所属栏目：Python 来源：互联网

导读：映射与字典字典dict是Python中重要的数据结构，在字典中，每一个键都对应一个值，其中键与值的关系就叫做映射，也可以说是每一个键都映射到一个值上。映射（map）是更具一般性的数据类型，具体到P

<div class="markdown-here-wrapper" data-md-url="https://i.cnblogs.com/EditPosts.aspx?postid=10350475">
<h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">映射与字典
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">字典dict是Python中重要的数据结构，在字典中，每一个键都对应一个值，其中键与值的关系就叫做映射，也可以说是每一个键都映射到一个值上。

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">映射（map）是更具一般性的数据类型，具体到Python中就是字典。

<h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">一个简单实现
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">在使用字典的同时我们一定会有一个疑问，它是怎样通过键去映射到值的呢，它怎么知道这个键的值是谁？

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">于是我们有了一个这样的想法：

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">使用列表来存储一项一项的键值对象，寻找的时候就遍历一遍列表，找到当键是你所要找的键时，取出该对象中的值value。

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">这个想法很简单，我们可以很快的实现一下：

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">这里先介绍一些相关的抽象基类，Mapping与MutableMapping，它们在collections模块中，供我们实现自定义的map类。Mapping包含dict中的所有不变方法，MutableMapping扩展包含了所有可变方法，但它们两个都不包含那五大核心特殊方法：getitem、setitem、delitem、len、iter。也就是说我们的目标就是实现这五大核心方法使该数据结构能够使用。

<span class="hljs-class"><span class="hljs-keyword" style="font-weight: bold;">class <span class="hljs-title" style="font-weight: bold; color: #0048ab;">MyMap<span class="hljs-params">(MutableMapping):
<span class="hljs-class"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;class</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;item</span><span class="hljs-params"&gt;()</span>:</span>

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__init__</span><span class="hljs-params"&gt;(self,key,value)</span>:</span>
        self.key = key
        self.value = value

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__eq__</span><span class="hljs-params"&gt;(self,other)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.key == other.key

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__ne__</span><span class="hljs-params"&gt;(self,other)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.key != other.key

<span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__init__</span><span class="hljs-params"&gt;(self)</span>:</span>
    self.table = []

<span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__getitem__</span><span class="hljs-params"&gt;(self,item)</span>:</span>
    <span class="hljs-keyword" style="font-weight: bold;"&gt;for</span> i <span class="hljs-keyword" style="font-weight: bold;"&gt;in</span> self.table:
        <span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> i.key == item:
            <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> i.value
    <span class="hljs-keyword" style="font-weight: bold;"&gt;raise</span> KeyError(<span class="hljs-string" style="color: #0048ab;"&gt;'Key Error: '</span>+ repr(item))

<span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__setitem__</span><span class="hljs-params"&gt;(self,value)</span>:</span>
    <span class="hljs-keyword" style="font-weight: bold;"&gt;for</span> i <span class="hljs-keyword" style="font-weight: bold;"&gt;in</span> self.table:
        <span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> i.key == key:
            i.value = value
            <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span>
    self.table.append(self.item(key,value))

<span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__delitem__</span><span class="hljs-params"&gt;(self,key)</span>:</span>
    <span class="hljs-keyword" style="font-weight: bold;"&gt;for</span> n,i <span class="hljs-keyword" style="font-weight: bold;"&gt;in</span> enumerate(self.table):
        <span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> i.key == key:
            self.pop(n)
            <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span>
    <span class="hljs-keyword" style="font-weight: bold;"&gt;raise</span> KeyError(<span class="hljs-string" style="color: #0048ab;"&gt;'Key Error: '</span>+ repr(key))

<span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__len__</span><span class="hljs-params"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> len(self.table)

<span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__iter__</span><span class="hljs-params"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="font-weight: bold;"&gt;for</span> i <span class="hljs-keyword" style="font-weight: bold;"&gt;in</span> self.table:
        <span class="hljs-keyword" style="font-weight: bold;"&gt;yield</span> i.key

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">上面这个办法很简单，但是却不是很有效率，我们每次都需要遍历一遍列表才能找到该键的索引，所以时间复杂的为O(n),我们希望这个映射的时间复杂度为O(1)或者是一个常数级别的，于是我们使用叫做哈希表的结构来实现

<h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">哈希表
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">首先先介绍一下哈希表的实现方式

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">1.对于一个键，我们需要计算出一个值来代表这个键，也就是将键映射到一个整数上，这个整数可以是正数也可以是负数，这一步就是求哈希值

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">2.这些哈希值有正有负，互相之间没有什么关系，并且位数也可能是好几位，我们想要把这些哈希值再次映射到一个区间[0,N-1]中，使得可以通过列表的整数索引去查找，这一步就是对哈希码的压缩，使用的函数叫做压缩函数

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">3.在经过压缩函数处理后，就可以得到原先的键对应的列表索引了，但是求哈希值与执行压缩函数的过程中，可能会有冲突发生，也就是得出的值不一定只是属于本键唯一的，可能一个其他的键也会得到同样的值。这时就要在最后把这种冲突处理掉，这一步就叫做冲突处理。

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">下面具体介绍一下这三个步骤

<h3 id="1-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 20px; border-bottom: 1px solid #aaaaaa;">1.哈希码
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">求哈希码有很多种方式

<h6 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: #777777; font-size: 16px;">将位作为整数处理
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">举个例子，Python中的哈希码是32位的，如果一个浮点数是64位，我们可以采取取其高32位为哈希码，或者低32位为哈希码，但这样极易出现冲突，所以可以采取高32位与低32位按位相加，或者按位异或

<h6 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: #777777; font-size: 16px;">多项式哈希码
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">对于像是字符串这样的对象，如果按照求和或异或的方式，可能会产生更多的冲突，比如temp10与temp01就会得到相同的哈希码。在字符串中，字符的位置非常重要，所以需要采取一种与位置有关系的哈希码计算方法，如下面这个式子：

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">x0a^(n-1)+x1a^(n-2)+……+x(n-2)a+x(n-1)

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">(x0,x1,x2,……,xn-1)是一个32位整数的n元组，是对象x的二进制表示

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">采用这种计算方式就可以与位置有关联了

<h6 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: #777777; font-size: 16px;">循环移位哈希码
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">利用二进制位循环移位方式，如下面这个字符串循环移位哈希码计算的实现：

> )
        h += ord(character)
     h

>是右移，&是按位与，|是按位或，ord()函数返回一个字符的ascii码或unicode值

                        （编辑：安卓应用网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

用Python实现数据结构之映射

（编辑：安卓应用网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

`（编辑：安卓应用网）【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!`