数据结构子目录//www.greatytc.com/p/a344fa483655
哈希表
在了解哈希表之前，我们要先认识一下直接寻址表。
什么是直接寻址表
我们确定key值就在某个范围之内，那么直接寻址就是一个很有效的办法。
这个图确定了key值只能在0--9之内，就可以建立一个0--9的列表，用来存储相应的key与value的指针。
直接寻址表的缺点
当U很大时，会消耗很大的内存，不实际。
当U很大，key很小时，很大的空间将会被浪费。
无法处理key不是数字的情况。
改进直接寻址表
将直接寻址表的key通过函数h()处理后放在h(key)的位置上，他将域映射在了表T上面。
这种处理就是哈希处理，哈希处理后的表，就是哈希表。
什么是哈希表
哈希表是一个通过哈希函数计算数据存储位置的数据结构。
哈希表，又称散列表，是一种线性数据结构，哈希表是由一个直接寻址表和一个哈希函数组成的，哈希函数h(k)将key作为自变量，返回元素的存储下标。
简单的例子
除法哈希：h(k)=k mod m
乘法哈希：h(k)=floor（m(kA mod 1)）
假设有一个长度为7的列表，哈希函数是h(k)=k mod 7，那么列表[5,3,22,14]的存储方式是：
[14,22,3,,5,,_]
然后现在思考一个问题，我们再把7存进去， 7 mod 7 该把他放在0这个位置，但是0这个位置已经有元素了。这就是哈希冲突。
哈希冲突
为了解决哈希冲突，引入了一个方法：开放寻址法。
如果哈希函数返回到位置已经有值了，则可以向后探查新的位置来存储这个值。
线性探查：如果i被占用，则探查i+1，i+2...
二度探查：如果i被占用，则探查i+12，i-12,i+22，i-22...
二度哈希：有n个哈希函数，当h1哈希后有冲突，则尝试h2，h3.
但是开放寻址之后，那么哈希表的作用就被无限弱化了，如果我要存的元素经过哈希后都在一个位置上呢？
这就有了第二个方法：拉链法。
哈希表的每一个位置都连接着一个链表，当冲突发生时，冲突的元素将被放到链表的最后。
代码
class HashMap(object):
def __init__(self):
# 初始化总表为，容量为2的表格（含两个子表）
self.maps = BetterMap(2)
self.num = 0 # 表中数据个数
def get(self,k):
return self.maps.get(k)
def add(self, k, v):
# 若当前元素数量达到临界值（子表总数）时，进行重排操作
# 对总表进行扩张，增加子表的个数为当前元素个数的两倍！
if self.num == len(self.maps.maps):
self.resize()
# 往重排过后的 self.map 添加新的元素
self.maps.add(k, v)
self.num += 1
def resize(self):
#重排操作，添加新表, 注意重排需要线性的时间
# 先建立一个新的表,子表数 = 2 * 元素个数
new_maps = BetterMap(self.num * 2)
for m in self.maps.maps: # 检索每个旧的子表
for k,v in m.items: # 将子表的元素复制到新子表
new_maps.add(k, v)
self.maps = new_maps # 令当前的表为新表
