Hello people, I have an assignment to do and I have no idea how to do it.

First: I have to modify this program to prompt the use for a word and display how many times that word appeared in the input file. When the user hits RETURN, the program should end.

I put in the obvious second input() function but cannot figure out how to implement it.

""" 
from hashtable import HashTable, get, keys, put, contains

def word_count( filename ):
    """Report on the frequency of different words in the
       file named by the argument.
    """
    hTable = HashTable( 19106 )

    # Read the words of the text file into the word count table.
    with open( filename ) as inFile:
        for line in inFile:
            for word in line.split():
                if contains( hTable, word ):
                    count = get( hTable, word )
                    put( hTable, word, count + 1 )
                else:
                    put( hTable, word, 1 )

    # Display the entire table!
    print( "Unique words:", hTable.size )

    # Find the most common word in the text file.
    total = 0
    maxWord = ""
    maxCount = 0
    for key in keys( hTable ):
        thisCount = get( hTable, key )
        total += thisCount
        if thisCount > maxCount:
            maxCount = thisCount
            maxWord = key

    print( "There are " + str( len( keys( hTable ) ) ) + " words." )
    print( "Total words:", total )
    print( '"' + maxWord + "\" appeared ", str( maxCount ),
          " times, more than any other word." )
    answer = input( "Do you want to see the entire table?(y/n) " )
    if answer == "y":
        printTable( hTable )

def printTable( hTable ):
    """Print the contents of the given hash table.
       Each key/value pair is displayed in parentheses, tuple-style.
       All pairs appear on a single line.
    """
    print( "Word Count Data\n---------------" )
    for key in keys( hTable ):
        print( "(" + key + "," + str( get( hTable, key ) ) + ")", end + "" )
    print( "\n" )

def main():
    filename = input( "Enter filename: " )
    wordname = input( "Enter word: ")
    word_count( filename )

main()

Second, I have to modify this hashtable code to use chaining, so basically, if a key hashes to the same location as another, it just gets appended to the list.

class HashTable( object ):
    """A data structure that contains a collection of values
       where each value is located by a hashable key.
       No two values may have the same key, but more than one
       key may have the same value.
    """

    __slots__ = ( "table", "size" )

    def __init__( self, capacity=100 ):
        """Create a hash table.
           The capacity parameter determines its initial size.
        """
        self.table = [ None ] * capacity
        self.size = 0

    def __str__( self ):
        """Return the entire contents of this hash table,
           one chain of entries per line.
        """
        result = ""
        for i in range( len( self.table ) ):
            result += str( i ) + ": "
            result += str( self.table[i] ) + "\n"
        return result

class _Entry( object ):
    """A private class used to hold key/value pairs"""

    __slots__ = ( "key", "value" )

    def __init__( self, entryKey, entryValue ):
        self.key = [entryKey]
        self.value = [entryValue]

    def __str__( self ):
        return "(" + str( self.key ) + ", " + str( self.value ) + ")"

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

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:
        return index
    else:
        return hTable.table[ index ]

def contains( hTable, key ):
    """Return True if hTable has an entry with the given key."""
    entry = _locate( hTable, key )
    return isinstance( entry, _Entry )

def put( hTable, key, value ):
    """Using the given hash table, set the given key to the
       given value. If the key already exists, the given value
       will replace the previous one already in the table.
       If the table is full, an Exception is raised.
    """
    entry = _locate( hTable, key )
    if isinstance( entry, int ): # It's the index of an unused position.
        if entry == -1:
            raise Exception( "Hash table is full." )
        hTable.table[ entry ] = _Entry( key, value )
        hTable.size += 1
    else: # pre-existing entry
        entry.value = value
    return True

def get( hTable, key ):
    """Return the value associated with the given key in
       the given hash table.
       Precondition: contains(hTable, key)
    """
    entry = _locate( hTable, key )
    return entry.value

Then, I have to design and implement a module called jumble. It takes a sequence of letters and forms anagrams from it.

Algorithm I have to use:

Create a hash table.
For each word in words.txt...
    Sort the letters in the word; use that as a key.
    Enter the (key,word) pair into the hash table.
Prompt the user for a string.
While the string is not empty...
    Look up the string in the hash table and print all words that use its letters.
    Prompt the user for a string.

I then have to edit hashtable.put to allow the table to grow when it gets too close to being full.

Rehashing algorithm:

Allocate the new hash table array
For each key in the old hash table
    Get the key's value from the old table
    Put (key,value) into the new table
Change the HashTable object so that it refers to the new array rather than the old one

It would be greatly appreciated if anyone can help me... I'm lost.

So I modified the hashtable code's put and get functions to the following:

def put( hTable, key, value ):
    hashCode = hash(key)
    if hTable[hashCode] == None:
        hTable[hashCode] = list()
        hTable[hashCode].append(value)
    else:
        hTable[hashcode].append(value)

def get( hTable, key ):
    hashCode = hash(key)
    entry = table[hashCode]
    for item in entry:
        if item.key == key:
            return item
    return None

Will this alone fix the hashtable?

Edited 5 Years Ago by da10x: n/a

My new get and put functions are:

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 ):
    hashCode = hash(key)
    entry = hTable.table[entry]
    for item in entry:
        if item.key == key:
            return item
    return None

I wrote a jumble() function as follows:

from hashtable import *

def sortLetters(word):
    chars = list(word)
    chars.sort()
    return "".join(chars)

def jumble():
    
    hTable = HashTable( 19106 )
    with open("words.txt") as inFile:
        for line in inFile:
            for word in line.split():
                key = hash(word)
                wordLetters = sortLetters(word)
                word = [word]
                word.append(wordLetters)
                put(hTable,key,word)

        userString = input("Enter a sequence of letters without spaces. ")
        while userString != ("" or None):
            sortLetters(userString)
            for key in hTable:
                current = get(hTable,key)
                if current.value[1] == sortLetters(userString):
                    print(current.value[0])
            return(str("There are no words that can be made from these letters."))
            
jumble()

It gives me the following error:

TypeError: 'HashTable' object does not support indexing

How can I fix this?

Edited 5 Years Ago by da10x: n/a

Are you missing some code? I copied what you have exactly and I'm getting;

AttributeError: '_Entry' object has no attribute 'append'

Anyways keep me posted I will keep trying, I find this interesting.

LOL on VCSS242 Lab on here last min, the hTable is a class so there is no index to the class, there is an index to the list that is contained in hTable.key, you can start there

This article has been dead for over six months. Start a new discussion instead.