For my project, as others before have noted, I have to create a hashtable using chaining. I rewrote my Get and Put functions, but I do not know how to change the Locate Function. Here is the code
def hash_function( val, n ):
"""Compute a hash of the val string that is in range(0,n)."""
# return 0
# return len(val) % n
return hash( val ) % n
def keys( hTable ):
"""Return a list of keys in the given hashTable.
(It would be better to return a sequence, but that
is too advanced.)
result = 
for entry in hTable.table:
if entry != None:
result.append( entry.key )
#This needs assistance
def _locate( hTable, key ):
"""Find the entry in the hash table for the given key.
If the key is not found, find the first unused location in the table.
(This is called 'open addressing'.)
If the entry for the key is found, that entry is returned.
Otherwise the int index where the key would go in the table is returned.
Finally if the key is not found and no unusued locations are left,
the int -1 is returned.
This function is meant to only be called from within hashtable.
Callers of this function must be prepared to
deal with results of two different types, unless they
are absolutely sure whether the key is in the table
index = hash_function( key, len( hTable.table ) )
startIndex = index # We must make sure we don't go in circles.
while hTable.table[ index ] != None and hTable.table[ index ].key != key:
index = ( index + 1 ) % len( hTable.table )
if index == startIndex:
if hTable.table[ index ] == None:
return hTable.table[ index ]
def contains( hTable, key ):
"""Return True iff hTable has an entry with the given key."""
entry = _locate( hTable, key )
return isinstance( entry, _Entry )
def put( hTable, key, value ):
hashCode = hash(key)
entry = _locate(hTable,key)
hTable.table[entry] = _Entry(key,value)
if hTable.table[entry] == None:
hTable.table[entry] = list()
def get( hTable, key ):
"""Return the value associated with the given key in
the given hash table.
Precondition: contains(hTable, key)
hashCode = hash(key)
entry = hTable.table[entry]
for item in entry:
if item.key == key:
The essence of a chained hash table is that each key is located in exactly one slot, but the slot does not directly contain a value, rather it contains a list of values, all of which hash to that slot. To give you an idea, I'll write method contains which will look something like
def contains self,value):
h = self.hash(value)
for v in self.table[h]:
if v == value:
I am deliberately not using your code and not providing you directly with an answer to your question. Please stop and think, then write some of your own code. My code assumes the existence of class ChainingHashTable:... of which this is one method.