少年，不知道你好记不记得第三篇文章讲python内建数据结构的方法及其时间复杂度时里面关于dict与set的时间复杂度[为何访问元素为O(1)]原理我说后面讲吗？其实就是这篇文章讲啦。
目录：
一：Hash的定义
二：dict与set的实现原理
三：常用构造hash函数的方法
四：hash碰撞及其解决方法
五：dict的实现
一：Hash的定义
Hash，一般翻译做“散列”，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。【不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值】
二：dict与set的实现原理
dict与set实现原理是一样的，都是将实际的值放到list中。唯一不同的在于hash函数操作的对象，对于dict，hash函数操作的是其key，而对于set是直接操作的它的元素，假设操作内容为x，其作为因变量，放入hash函数，通过运算后取list的余数，转化为一个list的下标，此下标位置对于set而言用来放其本身，而对于dict则是创建了两个list，一个list该下表放此key，另一个list中该下标方对应的value。
其中，我们把实现set的方式叫做Hash Set，实现dict的方式叫做Hash Map/Table(注：map指的就是通过key来寻找value的过程)
三：常用构造hash函数的方法
1：折叠法
将每个元素分为相等的几部分后相加后再除以list长度，e.g：如果项目是436-555-4601, 以2为分组，分成了 (43, 65, 55, 46, 01). 全部加起来：43 + 65 + 55 + 46 + 01 = 210. 假设list有11个元素, 则210%11 =1, 所以将436-555-4601放到list下标为1的地方。
2：取中法：
如元素44平方后得1936取中93再取list的余
注：对于string其所对应的数字可用其ASCII码来代替（还可与位数结合，见图5.7）ord('a')可返回'a'的ASCII码
注：此地就是为什么dict与set访问元素时间复杂度为O(1)的原因了，通过对元素的hash函数运算后能够直接知道其下标，所以为O(1)
四：hash碰撞及其解决方法
定义里面讲到过不同的输入可能会散列成相同的输出，所以就可能出现名为“哈希碰撞”的情况，也就是说两个不同的元素算出来的下标值一样，此时就有两种解决方法:
1:向后探测
架设一个元素算出来下标为5，另一个元素算出来下标也为5，从开头开始探测第0第1位是否为空，当看到为空的就放入，不过这样相邻探测的不好之处在于容易发生聚集，所以最好是跳跃着进行探测，定义一个skip的值，比如3，用方程rehash(pos) = (pos + skip)%sizeoftable，即使查看0，3，6这样跳跃着来
2：链式存储
原理图如下，其实就是将发生有冲突的元素放到同一位置，然后通过“指针“来串联起来
五：HashTable
下面将写一个hashTable，而实际中的dict就是由hashTable扩展而来的
class HashTable:
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size def hash_function(self, key, size):
return key % size
def rehash(self, old_hash, size):
return (old_hash + 1) % size
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, data):
self.put(key, data) def put(self, key, data):
hash_value = self.hash_function(key,len(self.slots))
if self.slots[hash_value] == None:
self.slots[hash_value] = key
self.data[hash_value] = data
elif self.slots[hash_value] == key:
self.data[hash_value] = data # replace
else:
next_slot = self.rehash(hash_value, len(self.slots))
while self.slots[next_slot] != None and self.slots[next_slot] != key:
next_slot = self.rehash(next_slot, len(self.slots))
if self.slots[next_slot] == None:
self.slots[next_slot] = key
self.data[next_slot] = data
else:
self.data[next_slot] = data #replace def get(self, key):
start_slot = self.hash_function(key, len(self.slots))
data = None
stop = False
found = False
position = start_slot
while self.slots[position] != None and not found and not stop:
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position=self.rehash(position, len(self.slots))
if position == start_slot:
stop = True
return data
HashTable