|
<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。也就是说我们的目标就是实现这五大核心方法使该数据结构能够使用。
collections MutableMapping
<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"><span class="hljs-keyword" style="font-weight: bold;">class</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">item</span><span class="hljs-params">()</span>:</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__init__</span><span class="hljs-params">(self,key,value)</span>:</span>
self.key = key
self.value = value
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__eq__</span><span class="hljs-params">(self,other)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.key == other.key
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__ne__</span><span class="hljs-params">(self,other)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.key != other.key
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__init__</span><span class="hljs-params">(self)</span>:</span>
self.table = []
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__getitem__</span><span class="hljs-params">(self,item)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">for</span> i <span class="hljs-keyword" style="font-weight: bold;">in</span> self.table:
<span class="hljs-keyword" style="font-weight: bold;">if</span> i.key == item:
<span class="hljs-keyword" style="font-weight: bold;">return</span> i.value
<span class="hljs-keyword" style="font-weight: bold;">raise</span> KeyError(<span class="hljs-string" style="color: #0048ab;">'Key Error: '</span>+ repr(item))
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__setitem__</span><span class="hljs-params">(self,value)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">for</span> i <span class="hljs-keyword" style="font-weight: bold;">in</span> self.table:
<span class="hljs-keyword" style="font-weight: bold;">if</span> i.key == key:
i.value = value
<span class="hljs-keyword" style="font-weight: bold;">return</span>
self.table.append(self.item(key,value))
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__delitem__</span><span class="hljs-params">(self,key)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">for</span> n,i <span class="hljs-keyword" style="font-weight: bold;">in</span> enumerate(self.table):
<span class="hljs-keyword" style="font-weight: bold;">if</span> i.key == key:
self.pop(n)
<span class="hljs-keyword" style="font-weight: bold;">return</span>
<span class="hljs-keyword" style="font-weight: bold;">raise</span> KeyError(<span class="hljs-string" style="color: #0048ab;">'Key Error: '</span>+ repr(key))
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__len__</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> len(self.table)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__iter__</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">for</span> i <span class="hljs-keyword" style="font-weight: bold;">in</span> self.table:
<span class="hljs-keyword" style="font-weight: bold;">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;">利用二进制位循环移位方式，如下面这个字符串循环移位哈希码计算的实现：
:
mask = ( << ) -
h =
character s:
h = (h << & mask) | (h >> )
h += ord(character)
h
>是右移，&是按位与，|是按位或，ord()函数返回一个字符的ascii码或unicode值
的特殊方法,在该函数中调用hash函数，并传入该对象的一些不可变属性组合，将值再返回，例如：
:
<span class="hljs-keyword" style="font-weight: bold;">return hash((self.red,self.green,self.blue))
<h3 id="2-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 20px; border-bottom: 1px solid #aaaaaa;">2.压缩函数
<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;">要把哈希码映射到[0,N-1]的区间中，最简单的方式就是进行求余数，例如f(i) = i modN
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">可是这样显然会有大量的冲突，一种稍微能够减小冲突的办法是将N改为一个素数
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">这样能够得到一些改善，但是pN+q类型的哈希码还是会被压缩成同一个数
<h6 id="mad-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: #777777; font-size: 16px;">MAD方法
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">MAD即Multiply-Add-and-Divide，这个方法通过下面这个式子进行映射
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">[(ai+b) mod p] mod N
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">N是区间的大小，p是比N大的素数，a和b是从区间[0,p-1]任意选择的整数且a>0
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">这个函数会尽可能的使映射均匀的分配到[0,N-1]中
<h3 id="3-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 20px; border-bottom: 1px solid #aaaaaa;">3.冲突处理
<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;">把列表中的每一项都存储为一个二级容器，将映射到该项的键值存入到二级容器中，查找键时先定位到二级容器，再在二级容器中寻找。这里的二级容器的效率要求就不是那么高了，可以使用上文中最开始定义的映射的简单实现来做这个二级容器。在整个哈希表中，我们希望存储的键值项的数量n小于N，也就是n/N<1,n/N叫做这个哈希表的负载因子。
<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;">这个简单说就是如果映射到这个地方已经有其他键值占上了，那么就向它的后一位放，如果后一位也有了，就继续向后放，知道找到一个空位，然后放进去。
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">查找的时候，映射到一个位置时要判断一下是不是要找的那个key，如果不是就向后一位找，知道找到是相同键了或者出现空位了，就停止
<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;">这种方法的缺点是每一对键值会连续的存储，这种聚集的现象会导致效率的问题。
<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;">为了改善线性探测聚集现象的发生，原先采用的(j+i)mod N（j为压缩函数得出的值，i为1,2,3….）探测方式改为(j+i^2)mod N
<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;">这种方式选择了再次进行哈希，如将探测方式改为(j+i*h(k))mod N,h()为一个哈希函数，k为键。
<h6 id="python-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: #777777; font-size: 16px;">Python字典所采用的方式
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">字典采用的是(j+f(i))mod N的方式，f(i)是一个基于伪随机数产生器的函数，它提供一个基于原始位的可重复的但是随机的，连续的地址探测序列。
<h1 id="-python-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">用Python具体实现
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">首先是一个哈希表的基类,采用MAD的压缩函数
:
<span class="hljs-class"><span class="hljs-keyword" style="font-weight: bold;">class</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">item</span><span class="hljs-params">()</span>:</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__init__</span><span class="hljs-params">(self,other)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.key != other.key
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__init__</span><span class="hljs-params">(self,cap=<span class="hljs-number">11</span>,p=<span class="hljs-number">109345121</span>)</span>:</span>
self._table = cap*[<span class="hljs-keyword" style="font-weight: bold;">None</span>]
self._n = <span class="hljs-number">0</span> <span class="hljs-comment" style="color: #738191;"># 元素数量</span>
self._prime = p <span class="hljs-comment" style="color: #738191;"># MAD中的参数</span>
self._scale = <span class="hljs-number">1</span> + random.randrange(p+<span class="hljs-number">1</span>) <span class="hljs-comment" style="color: #738191;"># MAD中的参数</span>
self._shift = random.randrange(p) <span class="hljs-comment" style="color: #738191;"># MAD中的参数</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">_hash_func</span><span class="hljs-params">(self,key)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> (hash(key)*self._scale+self._shift)%self._prime%len(self._table)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__len__</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> self._n
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__getitem__</span><span class="hljs-params">(self,k)</span>:</span>
j = self._hash_func(k)
<span class="hljs-keyword" style="font-weight: bold;">return</span> self._inner_getitem(j,k)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__setitem__</span><span class="hljs-params">(self,value)</span>:</span>
j = self._hash_func(key)
self._inner_setitem(j,value)
<span class="hljs-keyword" style="font-weight: bold;">if</span> self._n>len(self._table)//<span class="hljs-number">2</span>: <span class="hljs-comment" style="color: #738191;">#调整大小，使负载因子小于等于0.5</span>
self._resize(<span class="hljs-number">2</span>*len(self._table)-<span class="hljs-number">1</span>)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__delitem__</span><span class="hljs-params">(self,key)</span>:</span>
j = self._hash_func(key)
self._inner_delitem(j,key)
self._n -= <span class="hljs-number">1</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">_resize</span><span class="hljs-params">(self,cap)</span>:</span>
old = list(self.items())
self._table = cap*[<span class="hljs-keyword" style="font-weight: bold;">None</span>]
self._n = <span class="hljs-number">0</span>
<span class="hljs-keyword" style="font-weight: bold;">for</span> (k,v) <span class="hljs-keyword" style="font-weight: bold;">in</span> old:
self[k] = v
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">其中innergetitem，_inner_setitem，_inner_delitem的实现需要结合处理冲突的方式,猜测self.items()是内部调用了__iter方法实现的
<h3 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 20px; border-bottom: 1px solid #aaaaaa;">使用二级容器
:
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">_inner_getitem</span><span class="hljs-params">(self,j,k)</span>:</span>
bucket = self._table[j] <span class="hljs-comment" style="color: #738191;">#把二级容器叫做桶</span>
<span class="hljs-keyword" style="font-weight: bold;">if</span> bucket <span class="hljs-keyword" style="font-weight: bold;">is</span> <span class="hljs-keyword" style="font-weight: bold;">None</span>:
<span class="hljs-keyword" style="font-weight: bold;">raise</span> KeyError(<span class="hljs-string" style="color: #0048ab;">'Key Error: '</span>+ repr(k))
<span class="hljs-keyword" style="font-weight: bold;">return</span> bucket[k]
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">_inner_setitem</span><span class="hljs-params">(self,k,v)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">if</span> self._table[j] <span class="hljs-keyword" style="font-weight: bold;">is</span> <span class="hljs-keyword" style="font-weight: bold;">None</span>:
self._table[j] = MyMap()
oldsize = len(self._table[j])
self._table[j][k] = v
<span class="hljs-keyword" style="font-weight: bold;">if</span> len(self._table[j])>oldsize:
self._n += <span class="hljs-number">1</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">_inner_delitem</span><span class="hljs-params">(self,k)</span>:</span>
bucket = self._table[j]
<span class="hljs-keyword" style="font-weight: bold;">if</span> bucket <span class="hljs-keyword" style="font-weight: bold;">is</span> <span class="hljs-keyword" style="font-weight: bold;">None</span>:
<span class="hljs-keyword" style="font-weight: bold;">raise</span> KeyError(<span class="hljs-string" style="color: #0048ab;">'Key Error: '</span> + repr(k))
<span class="hljs-keyword" style="font-weight: bold;">del</span> bucket[k]
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__iter__</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">for</span> bucket <span class="hljs-keyword" style="font-weight: bold;">in</span> self._table:
<span class="hljs-keyword" style="font-weight: bold;">if</span> bucket <span class="hljs-keyword" style="font-weight: bold;">is</span> <span class="hljs-keyword" style="font-weight: bold;">not</span> <span class="hljs-keyword" style="font-weight: bold;">None</span>:
<span class="hljs-keyword" style="font-weight: bold;">for</span> key <span class="hljs-keyword" style="font-weight: bold;">in</span> bucket:
<span class="hljs-keyword" style="font-weight: bold;">yield</span> key
<h3 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 20px; border-bottom: 1px solid #aaaaaa;">使用线性探测
:
_AVAIL = object()
（编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
