python通过什么实现映射

映射（map）是更具一般性的数据类型，具体到Python中就是字典。（推荐学习：Python视频教程）

在使用字典的同时我们一定会有一个疑问，它是怎样通过键去映射到值的呢，它怎么知道这个键的值是谁？

于是我们有了一个这样的想法：

使用列表来存储一项一项的键值对象，寻找的时候就遍历一遍列表，找到当键是你所要找的键时，取出该对象中的值value。

这个想法很简单，我们可以很快的实现一下：

这里先介绍一些相关的抽象基类，Mapping与MutableMapping，它们在collections模块中，供我们实现自定义的map类。Mapping包含dict中的所有不变方法，MutableMapping扩展包含了所有可变方法，但它们两个都不包含那五大核心特殊方法：getitem、setitem、delitem、len、iter。也就是说我们的目标就是实现这五大核心方法使该数据结构能够使用。

from collections import MutableMapping

class MyMap(MutableMapping):

 class item():

 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 self.key != other.key

 def __init__(self):
 self.table = []

 def __getitem__(self, item):
 for i in self.table:
 if i.key == item:
 return i.value
 raise KeyError('Key Error: '+ repr(item))

 def __setitem__(self, key, value):
 for i in self.table:
 if i.key == key:
 i.value = value
 return
 self.table.append(self.item(key,value))

 def __delitem__(self, key):
 for n,i in enumerate(self.table):
 if i.key == key:
 self.pop(n)
 return
 raise KeyError('Key Error: '+ repr(key))

 def __len__(self):
 return len(self.table)

 def __iter__(self):
 for i in self.table:
 yield i.key

上面这个办法很简单，但是却不是很有效率，我们每次都需要遍历一遍列表才能找到该键的索引，所以时间复杂的为O(n)。

更多Python相关技术文章，请访问Python教程栏目进行学习！