python 下的数据结构与算法---8:哈希一下【dict与set的实现】

少年,不知道你好记不记得第三篇文章讲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码

    python 下的数据结构与算法---8:哈希一下【dict与set的实现】

  注:此地就是为什么dict与set访问元素时间复杂度为O(1)的原因了,通过对元素的hash函数运算后能够直接知道其下标,所以为O(1)

四:hash碰撞及其解决方法

  定义里面讲到过不同的输入可能会散列成相同的输出,所以就可能出现名为“哈希碰撞”的情况,也就是说两个不同的元素算出来的下标值一样,此时就有两种解决方法:

  1:向后探测

      架设一个元素算出来下标为5,另一个元素算出来下标也为5,从开头开始探测第0第1位是否为空,当看到为空的就放入,不过这样相邻探测的不好之处在于容易发生聚集,所以最好是跳跃着进行探测,定义一个skip的值,比如3,用方程rehash(pos) = (pos + skip)%sizeoftable,即使查看0,3,6这样跳跃着来

  2:链式存储

    原理图如下,其实就是将发生有冲突的元素放到同一位置,然后通过“指针“来串联起来

    python 下的数据结构与算法---8:哈希一下【dict与set的实现】

五: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

上一篇:commonjs模块和es6模块的区别


下一篇:android之模拟器访问外网设置