#-*- coding: utf-8 -*-

classArray(object):def __init__(self, size=32, init=None):

self._size=size

self._items= [init] *sizedef __getitem__(self, index):returnself._items[index]def __setitem__(self, index, value):

self._items[index]=valuedef __len__(self):returnself._sizedef clear(self, value=None):for i inrange(len(self._items)):

self._items[i]=valuedef __iter__(self):for item inself._items:yielditemclassSlot(object):def __init__(self, key, value):

self.key, self.value=key, valueclassHashTable(object):

UNUSED= None #没被使用过

EMPTY = Slot(None, None) #使用却被删除过

def __init__(self):

self._table= Array(8, init=HashTable.UNUSED) #保持 2*i 次方

self.length =0

@propertydef_load_factor(self):#load_factor 超过 0.8 重新分配

return self.length /float(len(self._table))def __len__(self):returnself.lengthdef_hash(self, key):return abs(hash(key)) %len(self._table)def_find_key(self, key):

index=self._hash(key)

_len=len(self._table)while self._table[index] is notHashTable.UNUSED:if self._table[index] isHashTable.EMPTY:

index= (index*5 + 1) %_lencontinue

elif self._table[index].key ==key:returnindexelse:

index= (index*5 + 1) %_lenreturnNonedef_find_slot_for_insert(self, key):

index=self._hash(key)

_len=len(self._table)while notself._slot_can_insert(index):

index= (index*5 + 1) %_lenreturnindexdef_slot_can_insert(self, index):return (self._table[index] is HashTable.EMPTY or self._table[index] isHashTable.UNUSED)def __contains__(self, key): #in operator

index =self._find_key(key)return index is notNonedefadd(self, key, value):if key inself:

index=self._find_key(key)

self._table[index].value=valuereturnFalseelse:

index=self._find_slot_for_insert(key)

self._table[index]=Slot(key, value)

self.length+= 1

if self._load_factor >= 0.8:

self._rehash()returnTruedef_rehash(self):

old_table=self._table

newsize= len(self._table) * 2self._table=Array(newsize, HashTable.UNUSED)

self.length=0for slot inold_table:if slot is not HashTable.UNUSED and slot is notHashTable.EMPTY:

index=self._find_slot_for_insert(slot.key)

self._table[index]=slot

self.length+= 1

def get(self, key, default=None):

index=self._find_key(key)if index isNone:returndefaultelse:returnself._table[index].valuedefremove(self, key):

index=self._find_key(key)if index isNone:raiseKeyError()

value=self._table[index].value

self.length-= 1self._table[index]=HashTable.EMPTYreturnvaluedef __iter__(self):for slot inself._table:if slot not in(HashTable.EMPTY, HashTable.UNUSED):yieldslot.keydeftest_hash_table():

h=HashTable()

h.add('a', 0)

h.add('b', 1)

h.add('c', 2)assert len(h) == 3

assert h.get('a') ==0assert h.get('b') == 1

assert h.get('hehe') isNone

h.remove('a')assert h.get('a') isNoneassert sorted(list(h)) == ['b', 'c']

n= 50

for i inrange(n):

h.add(i, i)for i inrange(n):assert h.get(i) ==iif __name__ == '__main__':print('beg',

test_hash_table(),'end',

)