python 哈希表实现简单python字典代码实例
这篇文章主要介绍了python哈希表实现简单python字典代码实例,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
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(self,_items):
self._items[i]=value
def__iter__(self):
foriteminself._items:
yielditem
classSlot(object):
"""
定义一个哈希表数组的槽
注意：一个槽有三种状态
1.从未被使用过，HashMap.UNUSED。此槽没有被使用和冲突过，查找时只要找到UNUSED就不用再继续探查了
2.使用过但是remove了，此时是HashMap.EMPTY，该谈差点后面的元素仍可能是有key
3.槽正在使用Slot节点
"""
def__init__(self,key,value):
self.key=key
self.value=value
classHashTable(object):
UNUSED=None#表示slot没有被使用过
EMPTY=Slot(None,None)#使用过被删除
def__init__(self):
self._table=Array(8,init=HashTable.UNUSED)#初始化，数组的每个元素都是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)#abs函数返回绝对值hash是内置函数_hash直接使用内置的哈希函数，对数组的长度取模
def_find_key(self,key):
index=self._hash(key)#先用_hash方法计算出槽的位置
_len=len(self._table)#现保存下来长度
whileself._table[index]isnotHashTable.UNUSED:#如果这个槽不是没有被使用过
ifself._table[index]isHashTable.EMPTY:#如果这个槽是，曾经有过值，不过被删除了
index=(index*5+1)%_len#cpython使用的一种解决哈希冲突的方式
continue
elifself._table[index].key==key:#正在使用，如果key值相同
returnindex
else:#这里就只剩最后一种可能，正在使用，但是key没有找到
index=(index*5+1)%_len
returnNone
def_slot_can_insert(self,index):#判断一个槽是否可以插入
return(self._table[index]isHashTable.EMPTYorself._table[index]isHashTable.UNUSED)
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__contains__(self,key):#实现一个in操作符
index=self._find_key(key)
returnindexisnotNone
defadd(self,key,value):
ifkeyinself:#上面实现的in操作符
index=self._find_key(key)
self._table[index].value=value
returnFalse#返回False表示没有执行插入操作，执行的是更新操作
else:
index=self._find_slot_for_insert(key)
self._table[index]=Slot(key,value)#这两部可能会调用_slot_can_insert函数，不管是哪种情况，EMPTY或是UNUSEZD，都将这个节点声明为Slot类
self.length+=1
ifself._load_factor>=0.8:
self._rehash()#当空间占用大于0.8的时候，进行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:#判断这个slot是有值的
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):#遍历操作，python字典默认遍历的是key，这里实现的也是遍历key
forslotinself._table:
ifslotnotin(HashTable.EMPTY,HashTable.UNUSED):
yieldslot.key
classDictADT(HashTable):
def__setitem__(self,key,value):#设定给定键的值
self.add(key,value)
def__getitem__(self,key):#返回给定键的值
ifkeynotinself:
raiseKeyError()
else:
returnself.get(key)
def_iter_slot(self):
forslotinself._table:
ifslotnotin(HashTable.EMPTY,HashTable.UNUSED):
yieldslot
defitems(self):
forslotinself._iter_slot():
yield(slot.key,slot.value)
defkeys(self):
forslotinself._iter_slot():
yieldslot.key
defvalues(self):
forslotinself._iter_slot():
yieldslot.value
deftest_dict():
importrandom
d=DictADT()
d['a']=1#这时候调用__setitem__方法
assertd['a']==1
d.remove('a')
l=list(range(30))
random.suffle(l)#打乱l
foriinl:
d.add(i,i)
foriinrange(30):
assertd.get(i)==i
assertsorted(list(d.keys()))==sorted(l)
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。