# Questions: input type, range
# Optimizations: better hash function based on expected inputs (otherwise a big linked list)
class HashTable( object ):
""" of U possible values our hash function should map to K possible spaces
"""
def __init__( self ): # TODO: max? , chaining
self.MAX = 20 # whenever MAX items are inserted the load is 1 (n/k)
self.table = [None] * self.MAX
def put( self, key, value ): # TODO: hash function
hash = self.myhash( key )
chain = self.table[ hash ]
if chain:
chain.append( value ) # TODO: FIFO vs LIFO?
self.table[ hash ]= chain
else:
chain = list()
chain.append( value )
self.table[ hash ]= chain
def lookup( self, key ):
hash = self.myhash( key )
chain = self.table[ hash ]
if chain:
return chain[ 0 ]
else:
return None # raise an Exception?
def remove( self, key ):
hash = self.myhash( key )
chain = self.table[ hash ]
if chain:
chain.pop() # TODO: FIFO vs LIFO?
else:
return None # raise an Exception?
def myhash( self , key ):
sum = 0
for i in xrange( len( key ) ):
sum += ord( key[ i ] ) # chr( 97 ) returns 'a' # 256 value limit (extended ascii), unichr()
hash = sum % self.MAX
return hash
if __name__ == '__main__':
h = HashTable() # print h.table
retrieved = h.lookup( 'a' )
print retrieved, "FROM h.lookup( 'a' ) "
print "INSERTED 'a'"
h.put( 'a', 'a' )
retrieved = h.lookup( 'a' )
print retrieved, " FROM h.lookup( 'a' ) "
retrieved = h.lookup( 'z' )
print retrieved, " FROM h.lookup( 'z' ) "
h.remove( 'a' )
retrieved = h.lookup( 'a' )
print retrieved, " FROM h.lookup( 'a' ) AFTER h.remove('a')"
h.put( 'baza', 'baza' )
h.put( 'abaz', 'abaz' )
# print h.table
retrieved = h.lookup( 'zaab' )
print retrieved, "FROM h.lookup( 'zaab' ) AFTER INSERTED 'baza' , 'abaz' "
h.remove( 'baza' )
retrieved = h.lookup( 'baza' )
print retrieved, " FROM h.lookup( 'baza' ) AFTER h.remove( 'baza' ), (i.e. removed hash collision abaz)"
# print h.table
h.remove( 'aazb' )
retrieved = h.lookup( 'baza' )
print retrieved, " FROM h.lookup( 'baza' ) AFTER h.remove( 'aazb' ), (i.e. key that creates hash collision removes the last from the chain)"