映射与字典
映射（map）是更具一般性的数据类型，具体到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),我们希望这个映射的时间复杂度为O(1)或者是一个常数级别的，于是我们使用叫做哈希表的结构来实现
哈希表
首先先介绍一下哈希表的实现方式
1.对于一个键，我们需要计算出一个值来代表这个键，也就是将键映射到一个整数上，这个整数可以是正数也可以是负数，这一步就是求哈希值
2.这些哈希值有正有负，互相之间没有什么关系，并且位数也可能是好几位，我们想要把这些哈希值再次映射到一个区间[0,N-1]中，使得可以通过列表的整数索引去查找，这一步就是对哈希码的压缩，使用的函数叫做压缩函数
3.在经过压缩函数处理后，就可以得到原先的键对应的列表索引了，但是求哈希值与执行压缩函数的过程中，可能会有冲突发生，也就是得出的值不一定只是属于本键唯一的，可能一个其他的键也会得到同样的值。这时就要在最后把这种冲突处理掉，这一步就叫做冲突处理。
下面具体介绍一下这三个步骤
1.哈希码
求哈希码有很多种方式
将位作为整数处理
举个例子，Python中的哈希码是32位的，如果一个浮点数是64位，我们可以采取取其高32位为哈希码，或者低32位为哈希码，但这样极易出现冲突，所以可以采取高32位与低32位按位相加，或者按位异或
多项式哈希码
对于像是字符串这样的对象，如果按照求和或异或的方式，可能会产生更多的冲突，比如temp10与temp01就会得到相同的哈希码。在字符串中，字符的位置非常重要，所以需要采取一种与位置有关系的哈希码计算方法，如下面这个式子：
x0a^(n-1)+x1a^(n-2)+……+x(n-2)a+x(n-1)
(x0,x1,x2,……,xn-1)是一个32位整数的n元组，是对象x的二进制表示
采用这种计算方式就可以与位置有关联了
循环移位哈希码
利用二进制位循环移位方式，如下面这个字符串循环移位哈希码计算的实现：
def hash_code(s):
mask = (1 << 32) - 1
h = 0
for character in s:
h = (h << 5 & mask) | (h >> 27)
h += ord(character)
return h
<<是左移，>>是