Open Addressing to Chaining

[unrealj]

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 )
    return result


#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
       or not.
    """
    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:
            return -1
    if hTable.table[ index ] == None:
        index=index.next
        return index
    else:
        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()
        hTable.table[entry].append(value)
    else:
        hTable.table[entry].append(value)


    
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:
            return item
    return None

Any help or advice here would be appreciated.

[griswolf]

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:
       return True
  return False

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.

[unrealj]

Thank you for explaining that. I didn't think that chaining was similar to linked lists, but now I see that they are nearly two in the same.