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
<<是左移，>>是右移，&是按位与，|是按位或，ord()函数返回一个字符的ascii码或unicode值
Python中的哈希码
Python中提供了hash()函数，传入对象x，返回一个整型值作为它的哈希码
在Python中只有不可变类型才可以使用hash，如果把我们自定义的对象作为参数传入则会报错。
若想让我们自定义的对象能够使用，可以在类中实现一个叫做hash的特殊方法,在该函数中调用hash函数，并传入该对象的一些不可变属性组合，将值再返回，例如：
def __hash__(self):
return hash((self.red,self.green,self.blue))
2.压缩函数
划分方法
要把哈希码映射到[0,N-1]的区间中，最简单的方式就是进行求余数，例如f(i) = i modN
可是这样显然会有大量的冲突，一种稍微能够减小冲突的办法是将N改为一个素数
这样能够得到一些改善，但是pN+q类型的哈希码还是会被压缩成同一个数
MAD方法
MAD即Multiply-Add-and-Divide，这个方法通过下面这个式子进行映射
[(ai+b) mod p] mod N
N是区间的大小，p是比N大的素数，a和b是从区间[0,p-1]任意选择的整数且a>0
这个函数会尽可能的使映射均匀的分配到[0,N-1]中
3.冲突处理
尽管在求哈希值与压缩函数的过程中我们尽可能避免发生冲突，但还是会有可能造成冲突的，为此还需要进行冲突的处理
使用二级容器
把列表中的每一项都存储为一个二级容器，将映射到该项的键值存入到二级容器中，查找键时先定位到二级容器，再在二级容器中寻找。这里的二级容器的效率要求就不是那么高了，可以使用上文中最开始定义的映射的简单实现来做这个二级容器。在整个哈希表中，我们希望存储的键值项的数量n小于N，也就是n/N<1,n/N叫做这个哈希表的负载因子。
线性探测
这个简单说就是如果映射到这个地方已经有其他键值占上了，那么就向它的后一位放，如果后一位也有了，就继续向后放，知道找到一个空位，然后放进去。
查找的时候，映射到一个位置时要判断一下是不是要找的那个key，如果不是就向后一位找，知道找到是相同键了或者出现空位了，就停止
删除的时候，一样是先找到，然后为了不影响查找，不能简单的将其设置为空，应该用一个标记的对象填住该位置，这时查找的方法也要进行一些改动使其能够跳过这种标记位置。
这种方法的缺点是每一对键值会连续的存储，这种聚集的现象会导致效率的问题。
二次探测
为了改善线性探测聚集现象的发生，原先采用的(j+i)mod N（j为压缩函数得出的值，i为1,2,3….）探测方式改为(j+i^2)mod N
但是当元素超过了哈希表的一半时，这种方式无法保证找到空闲的位置。而且这种方式的删除或其他操作也会更复杂
双哈希策略
这种方式选择了再次进行哈希，如将探测方式改为(j+i*h(k))mod N,h()为一个哈希函数，k为键。
Python字典所采用的方式
字典采用的是(j+f(i))mod N的方式，f(i)是一个基于伪随机数产生器的函数，它提供一个基于原始位的可重复的但是随机的，连续的地址探测序列。
用Python具体实现
首先是一个哈希表的基类,采用MAD的压缩函数
class HashMapBase(MutableMapping):
"""哈希表的基类，需要在子类中实现_inner_getitem,_inner_setitem,
_inner_delitem与__iter__"""
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,cap=11,p=109345121):
self._table = cap*[None]
self._n = 0 # 元素数量
self._prime = p # MAD中的参数
self._scale = 1 + random.randrange(p+1) # MAD中的参数
self._shift = random.randrange(p) # MAD中的参数
def _hash_func(self,key):
return (hash(key)*self._scale+self._shift)%self._prime%len(self._table)
def __len__(self):
return self._n
def __getitem__(self, k):
j = self._hash_func(k)
return self._inner_getitem(j,k)