Python 实现集合Set的示例
Python的集合set原理
集合（set）是一个无序的不重复元素序列。
可以使用大括号{}或者set()函数创建集合，注意：创建一个空集合必须用set()而不是{}，因为{}是用来创建一个空字典。
classArray(object): def__init__(self,size=32,init=None): self._size=size self._items=[init]*self._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表数组的槽 注意，一个槽有三种状态，看你能否想明白 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) self.length=0 #负载因子 @property def_load_factor(self): returnself.length/float(len(self._table)) def__len__(self): returnself.length #哈希函数用内置的哈希哈数进行哈希一下，然后对数组长度取模 def_hash(self,key): returnabs(hash(key))%len(self._table) def_find_key(self,key): #得到第一个值的位置 index=self._hash(key) _len=len(self._table) #当这个槽不是未使用过的，才接着往下找；如果是未使用过的，这个key肯定不存在 whileself._table[index]isnotHashTable.UNUSED: #槽使用过，但是被删除了 ifself._table[index]isHashTable.EMPTY: #cpython解决哈希冲突的一种方式 index=(index*5+1)%_len continue elifself._table[index]==key: returnindex else: index=(index*5+1)%_len returnNone #检测槽是否能被插入 def_slot_can_insert(self,index): return(self._table[index]isHashTable.EMPTYorself._table[index]isHashTable.UNUSED) #找到能被插入的槽的index def_find_slot_insert(self,key): #得到第一个值的位置 index=self._hash(key) _len=len(self._table) whilenotself._slot_can_insert(index): index=(index*5+1)%_len returnindex #in操作符 def__contains__(self,key): index=self._find_key(key) returnindexisnotNone defadd(self,key,value): ifkeyinself: index=self._find_key(key) #更新值 self._table[index].value=value returnFalse else: index=self._find_slot_insert(key) self._table[index]=Slot(key,value) self.length+=1 ifself._load_factor>0.8: returnself._rehash() returnTrue def_rehash(self): oldtable=self._table newsize=len(self._table)*2 #新的table self._table=Array(newsize,HashTable.UNUSED) self.length=0 forslotinoldtable: ifslotisnotHashTable.UNUSEDandslotisnotHashTable.EMPTY: index=self._find_slot_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.UNUSED,HashTable.EMPTY): yieldslot.value classSetADT(HashTable): defadd(self,key): returnsuper(SetADT,self).add(key,True) def__and__(self,other_set): #求交集 new_set=SetADT() forelement_ainself: ifelement_ainother_set: new_set.add(element_a) returnnew_set def__sub__(self,other_set): #求差集 new_set=SetADT() forelement_ainself: ifelement_anotinother_set: new_set.add(element_a) returnnew_set def__or__(self,other_set): #求交集 new_set=SetADT() forelement_ainself: new_set.add(element_a) forelement_binother_set: new_set.add(element_b) returnnew_set
以上就是Python实现集合Set的示例的详细内容，更多关于Python实现集合Set的资料请关注毛票票其它相关文章！