使用python实现哈希表、字典、集合操作
哈希表
哈希表（HashTable,又称为散列表），是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。哈希函数h(k)将元素关键字k作为自变量，返回元素的存储下标。
简单哈希函数：
除法哈希：h(k)=kmodm乘法哈希：h(k)=floor(m(kAmod1))0 假设有一个长度为7的数组，哈希函数h(k)=kmod7,元素集合{14,22,3,5}的存储方式如下图：
哈希冲突
由于哈希表的大小是有限的，而要存储的值的总数量是无限的，因此对于任何哈希函数，都会出现两个不同的元素映射到同一个位置上的情况，这种情况叫做哈希冲突。
比如：h(k)=kmod7,h(0)=h(7)=h(14)=...
解决哈希冲突--开放寻址法
开放寻址法：如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值
线性探查：如果位置i被占用，则探查i+1,i+2,...二次探查：如果位置i被占用，则探查i+12,i-12,i+22,i-22,...二度哈希：有n个哈希函数，当使用第一个哈希函数h1发生冲突时，则尝试使用h2,h3,...
解决哈希冲突--拉链法
拉链法：哈希表每一个位置都连接一个链表，当冲突发生时，冲突的元素将被加到该位置链表的最后。
哈希表的实现
classArray(object): def__init__(self,size=32,init=None): self._size=size self._items=[init]*size def__getitem__(self,index): returnself._items[index] def__setitem__(self,index,value): self._items[index]=value def__len__(self): returnself._size defclear(self,value=None): foriinrange(len(self._items)): self._items[i]=value def__iter__(self): foriteminself._items: yielditem classSlot(object): """ 定义一个hash表数组的槽(slot这里指的就是数组的一个位置) hashtable就是一个数组，每个数组的元素（也叫slot槽）是一个对象，对象包含两个属性key和value。 注意，一个槽有三种状态，看你能否想明白。相比链接法解决冲突，探查法删除一个key的操作稍微复杂。 1.从未使用HashMap.UNUSED。此槽没有被使用和冲突过，查找时只要找到UNUSED就不用再继续探查了 2.使用过但是remove了，此时是HashMap.EMPTY，该探查点后边的元素仍然可能是有key的，需要继续查找 3.槽正在使用Slot节点 """ def__init__(self,key,value): self.key,self.value=key,value classHashTable(object): UNUSED=None#没被使用过 EMPTY=Slot(None,None)#使用却被删除过 def__init__(self): self._table=Array(8,init=HashTable.UNUSED)#保持2*i次方 self.length=0 @property def_load_factor(self): #load_factor超过0.8重新分配 returnself.length/float(len(self._table)) def__len__(self): returnself.length #进行哈希 def_hash(self,key): returnabs(hash(key))%len(self._table) #查找key def_find_key(self,key): """ 解释一个slot为UNUSED和EMPTY的区别 因为使用的是二次探查的方式，假如有两个元素A，B冲突了， 首先Ahash得到是slot下标5，A放到了第5个槽，之后插入B因为冲突了，所以继续根据二次探查方式放到了slot下标8。 然后删除A，槽5被置为EMPTY。然后我去查找B， 第一次hash得到的是槽5，但是这个时候我还是需要第二次计算hash才能找到B。 但是如果槽是UNUSED我就不用继续找了，我认为B就是不存在的元素。这个就是UNUSED和EMPTY的区别。 """ origin_index=index=self._hash(key)#origin_index判断是否又走到了起点，如果查找一圈了都找不到则无此元素 _len=len(self._table) whileself._table[index]isnotHashTable.UNUSED: ifself._table[index]isHashTable.EMPTY:#注意如果是EMPTY，继续寻找下一个槽 index=(index*5+1)%_len ifindex==origin_index: break continue ifself._table[index].key==key:#找到了key returnindex else: index=(index*5+1)%_len#没有找到继续找下一个位置 ifindex==origin_index: break returnNone #找能插入的槽 def_find_slot_for_insert(self,key): index=self._hash(key) _len=len(self._table) whilenotself._slot_can_insert(index):#直到找到一个可以用的槽 index=(index*5+1)%_len returnindex #槽是否能插入 def_slot_can_insert(self,index): returnself._table[index]isHashTable.EMPTYorself._table[index]isHashTable.UNUSED #inoperator，实现之后可以使用in操作符判断 def__contains__(self,key): index=self._find_key(key) returnindexisnotNone #添加元素 defadd(self,key,value): ifkeyinself:#update index=self._find_key(key) self._table[index].value=value returnFalse else: index=self._find_slot_for_insert(key) self._table[index]=Slot(key,value) self.length+=1 ifself._load_factor>=0.8: self._rehash() returnTrue #槽不够时，重哈希 def_rehash(self): old_table=self._table newsize=len(self._table)*2 self._table=Array(newsize,HashTable.UNUSED) self.length=0 forslotinold_table: ifslotisnotHashTable.UNUSEDandslotisnotHashTable.EMPTY: index=self._find_slot_for_insert(slot.key) self._table[index]=slot self.length+=1 #获取值 defget(self,key,default=None): index=self._find_key(key) ifindexisNone: returndefault else: returnself._table[index].value #移除 defremove(self,key): index=self._find_key(key) ifindexisNone: raiseKeyError() value=self._table[index].value self.length-=1 self._table[index]=HashTable.EMPTY returnvalue #遍历 def__iter__(self): forslotinself._table: ifslotnotin(HashTable.EMPTY,HashTable.UNUSED): yieldslot.key
哈希表的使用
h=HashTable()
h.add('a',0)
h.add('b',1)
h.add('c',2)
print(len(h))#3
print(h.get('a'))#0
print(h.get('b'))#1
print(h.get('hehe'))#None
h.remove('a')
print(h.get('a'))#None
print(sorted(list(h)))#['b','c']
字典
字典是另一种可变容器模型，且可存储任意类型对象。
字典的每个键值key=>value对用冒号:分割，每个键值对之间用逗号,分割，整个字典包括在花括号{}中,格式如下所示：
d ={key1:value1,key2:value2}
基于哈希表实现字典
classArray(object): def__init__(self,size=32,init=None): self._size=size self._items=[init]*size def__getitem__(self,index): returnself._items[index] def__setitem__(self,index,value): self._items[index]=value def__len__(self): returnself._size defclear(self,value=None): foriinrange(len(self._items)): self._items[i]=value def__iter__(self): foriteminself._items: yielditem classSlot(object): """ 定义一个hash表数组的槽(slot这里指的就是数组的一个位置) hashtable就是一个数组，每个数组的元素（也叫slot槽）是一个对象，对象包含两个属性key和value。 注意，一个槽有三种状态，看你能否想明白。相比链接法解决冲突，探查法删除一个key的操作稍微复杂。 1.从未使用HashMap.UNUSED。此槽没有被使用和冲突过，查找时只要找到UNUSED就不用再继续探查了 2.使用过但是remove了，此时是HashMap.EMPTY，该探查点后边的元素仍然可能是有key的，需要继续查找 3.槽正在使用Slot节点 """ def__init__(self,key,value): self.key,self.value=key,value classHashTable(object): UNUSED=None#没被使用过 EMPTY=Slot(None,None)#使用却被删除过 def__init__(self): self._table=Array(8,init=HashTable.UNUSED)#保持2*i次方 self.length=0 @property def_load_factor(self): #load_factor超过0.8重新分配 returnself.length/float(len(self._table)) def__len__(self): returnself.length #进行哈希 def_hash(self,key): returnabs(hash(key))%len(self._table) #查找key def_find_key(self,key): """ 解释一个slot为UNUSED和EMPTY的区别 因为使用的是二次探查的方式，假如有两个元素A，B冲突了， 首先Ahash得到是slot下标5，A放到了第5个槽，之后插入B因为冲突了，所以继续根据二次探查方式放到了slot下标8。 然后删除A，槽5被置为EMPTY。然后我去查找B， 第一次hash得到的是槽5，但是这个时候我还是需要第二次计算hash才能找到B。 但是如果槽是UNUSED我就不用继续找了，我认为B就是不存在的元素。这个就是UNUSED和EMPTY的区别。 """ origin_index=index=self._hash(key)#origin_index判断是否又走到了起点，如果查找一圈了都找不到则无此元素 _len=len(self._table) whileself._table[index]isnotHashTable.UNUSED: ifself._table[index]isHashTable.EMPTY:#注意如果是EMPTY，继续寻找下一个槽 index=(index*5+1)%_len ifindex==origin_index: break continue ifself._table[index].key==key:#找到了key returnindex else: index=(index*5+1)%_len#没有找到继续找下一个位置 ifindex==origin_index: break returnNone #找能插入的槽 def_find_slot_for_insert(self,key): index=self._hash(key) _len=len(self._table) whilenotself._slot_can_insert(index):#直到找到一个可以用的槽 index=(index*5+1)%_len returnindex #槽是否能插入 def_slot_can_insert(self,index): returnself._table[index]isHashTable.EMPTYorself._table[index]isHashTable.UNUSED #inoperator，实现之后可以使用in操作符判断 def__contains__(self,key): index=self._find_key(key) returnindexisnotNone #添加元素 defadd(self,key,value): ifkeyinself:#update index=self._find_key(key) self._table[index].value=value returnFalse else: index=self._find_slot_for_insert(key) self._table[index]=Slot(key,value) self.length+=1 ifself._load_factor>=0.8: self._rehash() returnTrue #槽不够时，重哈希 def_rehash(self): old_table=self._table newsize=len(self._table)*2 self._table=Array(newsize,HashTable.UNUSED) self.length=0 forslotinold_table: ifslotisnotHashTable.UNUSEDandslotisnotHashTable.EMPTY: index=self._find_slot_for_insert(slot.key) self._table[index]=slot self.length+=1 #获取值 defget(self,key,default=None): index=self._find_key(key) ifindexisNone: returndefault else: returnself._table[index].value #移除 defremove(self,key): index=self._find_key(key) ifindexisNone: raiseKeyError() value=self._table[index].value self.length-=1 self._table[index]=HashTable.EMPTY returnvalue #遍历 def__iter__(self): forslotinself._table: ifslotnotin(HashTable.EMPTY,HashTable.UNUSED): yieldslot.key classDictADT(HashTable): #执行dict[key]=value时执行 def__setitem__(self,key,value): self.add(key,value) #执行dict[key]时执行 def__getitem__(self,key,default=None): ifkeynotinself: raiseKeyError() returnself.get(key,default) #遍历时执行 def_iter_slot(self): forslotinself._table: ifslotnotin(self.UNUSED,self.EMPTY): yieldslot #实现items方法 defitems(self): forslotinself._iter_slot(): yield(slot.key,slot.value) #实现keys方法 defkeys(self): forslotinself._iter_slot(): yieldslot.key #实现values方法 defvalues(self): forslotinself._iter_slot(): yieldslot.value
字典的使用
d=DictADT() d['a']=1 print(d['a'])#1
集合
集合是一种不包含重复元素的数据结构，经常用来判断是否重复这种操作，或者集合中是否存在一个元素。
集合可能最常用的就是去重，判断是否存在一个元素等，但是set相比dict有更丰富的操作，主要是数学概念上的。
如果你学过《离散数学》中集合相关的概念，基本上是一致的。python的set提供了如下基本的集合操作，假设有两个集合A，B，有以下操作
- 交集:A&B，表示同时在A和B中的元素。python中重载__and__实现
- 并集:A|B，表示在A或者B中的元素，两个集合相加。python中重载__or__实现
- 差集:A-B，表示在A中但是不在B中的元素。python中重载__sub__实现
基于哈希表实现集合
classArray(object): def__init__(self,size=32,init=None): self._size=size self._items=[init]*size def__getitem__(self,index): returnself._items[index] def__setitem__(self,index,value): self._items[index]=value def__len__(self): returnself._size defclear(self,value=None): foriinrange(len(self._items)): self._items[i]=value def__iter__(self): foriteminself._items: yielditem classSlot(object): """ 定义一个hash表数组的槽(slot这里指的就是数组的一个位置) hashtable就是一个数组，每个数组的元素（也叫slot槽）是一个对象，对象包含两个属性key和value。 注意，一个槽有三种状态，看你能否想明白。相比链接法解决冲突，探查法删除一个key的操作稍微复杂。 1.从未使用HashMap.UNUSED。此槽没有被使用和冲突过，查找时只要找到UNUSED就不用再继续探查了 2.使用过但是remove了，此时是HashMap.EMPTY，该探查点后边的元素仍然可能是有key的，需要继续查找 3.槽正在使用Slot节点 """ def__init__(self,key,value): self.key,self.value=key,value classHashTable(object): UNUSED=None#没被使用过 EMPTY=Slot(None,None)#使用却被删除过 def__init__(self): self._table=Array(8,init=HashTable.UNUSED)#保持2*i次方 self.length=0 @property def_load_factor(self): #load_factor超过0.8重新分配 returnself.length/float(len(self._table)) def__len__(self): returnself.length #进行哈希 def_hash(self,key): returnabs(hash(key))%len(self._table) #查找key def_find_key(self,key): """ 解释一个slot为UNUSED和EMPTY的区别 因为使用的是二次探查的方式，假如有两个元素A，B冲突了， 首先Ahash得到是slot下标5，A放到了第5个槽，之后插入B因为冲突了，所以继续根据二次探查方式放到了slot下标8。 然后删除A，槽5被置为EMPTY。然后我去查找B， 第一次hash得到的是槽5，但是这个时候我还是需要第二次计算hash才能找到B。 但是如果槽是UNUSED我就不用继续找了，我认为B就是不存在的元素。这个就是UNUSED和EMPTY的区别。 """ origin_index=index=self._hash(key)#origin_index判断是否又走到了起点，如果查找一圈了都找不到则无此元素 _len=len(self._table) whileself._table[index]isnotHashTable.UNUSED: ifself._table[index]isHashTable.EMPTY:#注意如果是EMPTY，继续寻找下一个槽 index=(index*5+1)%_len ifindex==origin_index: break continue ifself._table[index].key==key:#找到了key returnindex else: index=(index*5+1)%_len#没有找到继续找下一个位置 ifindex==origin_index: break returnNone #找能插入的槽 def_find_slot_for_insert(self,key): index=self._hash(key) _len=len(self._table) whilenotself._slot_can_insert(index):#直到找到一个可以用的槽 index=(index*5+1)%_len returnindex #槽是否能插入 def_slot_can_insert(self,index): returnself._table[index]isHashTable.EMPTYorself._table[index]isHashTable.UNUSED #inoperator，实现之后可以使用in操作符判断 def__contains__(self,key): index=self._find_key(key) returnindexisnotNone #添加元素 defadd(self,key,value): ifkeyinself:#update index=self._find_key(key) self._table[index].value=value returnFalse else: index=self._find_slot_for_insert(key) self._table[index]=Slot(key,value) self.length+=1 ifself._load_factor>=0.8: self._rehash() returnTrue #槽不够时，重哈希 def_rehash(self): old_table=self._table newsize=len(self._table)*2 self._table=Array(newsize,HashTable.UNUSED) self.length=0 forslotinold_table: ifslotisnotHashTable.UNUSEDandslotisnotHashTable.EMPTY: index=self._find_slot_for_insert(slot.key) self._table[index]=slot self.length+=1 #获取值 defget(self,key,default=None): index=self._find_key(key) ifindexisNone: returndefault else: returnself._table[index].value #移除 defremove(self,key): index=self._find_key(key) ifindexisNone: raiseKeyError() value=self._table[index].value self.length-=1 self._table[index]=HashTable.EMPTY returnvalue #遍历 def__iter__(self): forslotinself._table: ifslotnotin(HashTable.EMPTY,HashTable.UNUSED): yieldslot.key classSetADT(HashTable): #添加元素 defadd(self,key): super().add(key,True) def__and__(self,other_set): """交集A&B""" new_set=SetADT() forelement_ainself: ifelement_ainother_set: new_set.add(element_a) returnnew_set def__sub__(self,other_set): """差集A-B""" new_set=SetADT() forelement_ainself: ifelement_anotinother_set: new_set.add(element_a) returnnew_set def__or__(self,other_set): """并集A|B""" new_set=SetADT() forelement_ainself: new_set.add(element_a) forelement_binother_set: new_set.add(element_b) returnnew_set
集合的使用
sa=SetADT() sa.add(1) sa.add(2) sa.add(3) sb=SetADT() sb.add(3) sb.add(4) sb.add(5) print(sorted(list(sa&sb)))#[3] print(sorted(list(sa-sb)))#[1,2] print(sorted(list(sa|sb)))#[1,2,3,4,5]
总结
以上所述是小编给大家介绍的使用python实现哈希表、字典、集合操作，希望对大家有所帮助！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。