Python Hash Tables!

Use the sample code below and take this solution as far as you can.

****Do not use the "print" from the HashTable to display the final table, but rather implement your own which should list each of the words and its frequency separated by a dash like so, "to - 3, be - 9, the - 18, ..."

HashTable_SeparateChaining.py

# Implement a hash table usnig separate chaining # This implementation makes use of the KeyValueList class to store # the key-value pairs in each table cell from Hashing import * from KeyValueList import * import sys def simpleHash(key): # A simple hashing function if isinstance(key, int): # Integers hash to themselves return key elif isinstance(key, str): # Strings are hashed by letters return sum( # Multiply the code for each letter by 256 ** i * ord(key[i]) # 256 to the power of its position for i in range(len(key))) # in the string elif isinstance(key, (list, tuple)): # For sequences, return sum( # Multiply the simpleHash of each element 256 ** i * simpleHash(key[i]) # by 256 to the power of its for i in range(len(key))) # position in the sequence raise Exception( # Otherwise it's an unknown type 'Unable to hash key of type ' + str(type(key))) class HashTable(object): # A hash table using separate chaining def __init__( # The constructor takes the initial self, size=7, # size of the table, hash=simpleHash, # a hashing function, and maxLoadFactor=1.0): # the max load factor before growing self.__table = [None] * size # Allocate empty hash table self.__nItems = 0 # Track the count of items in the table self.__hash = hash # Store given hash function, and max self.__maxLoadFactor = maxLoadFactor # load factor def __len__(self): # The length of the hash table is the return self.__nItems # number of cells that have items def cells(self): # Get the size of the hash table in return len(self.__table) # terms of the number of cells def hash(self, key): # Use the hashing function to get the return self.__hash(key) % self.cells() # default cell index def search(self, # Get the value associated with a key key): # in the hash table, if any i = self.hash(key) # Get cell index by hashing key return (None if self.__table[i] is None else # If list exists, self.__table[i].search(key)) # search it, else None def insert(self, # Insert or update the value associated key, value): # with a given key i = self.hash(key) # Get cell index by hashing key if self.__table[i] is None: # If the cell is empty, self.__table[i] = KeyValueList() # Create empty linked list flag = self.__table[i].insert(key, value) # Insert item in list if flag: # If a node was added, self.__nItems += 1 # increment item count if self.loadFactor() > self.__maxLoadFactor: # When load self.__growTable() # factor exceeds limit, grow table return flag # Return flag to indicate update def __growTable(self): # Grow the table to accommodate more items oldTable = self.__table # Save old table size = len(oldTable) * 2 + 1 # Make new table at least 2 times while not is_prime(size): # bigger and a prime number of cells size += 2 # Only consider odd sizes self.__table = [None] * size # Allocate new table self.__nItems = 0 # Note that it is empty for i in range(len(oldTable)): # Loop through old cells and if oldTable[i]: # if they contain a list, loop over for item in oldTable[i].traverse(): # all items self.insert(*item) # Re-hash the (key, value) tuple def loadFactor(self): # Get the load factor for the hash table return self.__nItems / len(self.__table) def traverse(self): # Traverse the key, value pairs in table for i in range(len(self.__table)): # Loop through all cells if self.__table[i]: # For those cells containing lists, for item in self.__table[i].traverse(): # traverse yield item # the list yielding items def delete(self, # Delete an item identified by its key key, # from the hash table. Raise an exception ignoreMissing=False): # if not ignoring missing keys i = self.hash(key) # Get cell index by hashing key if self.__table[i] is not None: # If cell i is not empty, try if self.__table[i].delete(key): # deleting item in list and self.__nItems -= 1 # if found, reduce count of items return True # Return flag showing item was deleted if ignoreMissing: # Otherwise, no deletion. If we ignore return False # missing items, return flag raise Exception( # Otherwise raise an exception 'Cannot delete key {} not found in hash table'.format(key)) def __str__(self): # Convert table to a string representaion N = len(self.__table) out = ' 2 * show: out += ' ...' for i in range(max(N - show, show), N): # Last cells up to N - 1 out += ' {:4d}-'.format(i) if self.__table[i]: out += str(self.__table[i]) out += ' >' return out def tableString(self): # Show the keys of all table cells as return '[{}]'.format(','.join( # a string ' ' if cell is None else # Empty cells are spaces, '[{}]'.format( # Lists are square braces enclosing ', '.join( # a list of keys separated by commas repr(key) for key, val in cell.traverse()) for cell in self.__table))) def peek(self, i): # Peek at contents of cell i return self.__table[i]

HashTable_SeparateChainingClient.py

from HashTable_SeparateChaining import * from collections import * # Allocate a hash table hTable = HashTable() testKeys = [x for x in range(0, 500, 5)] sizes = [] size = hTable.cells() while size

Sample text:

To be, or not to be: that is the question: Whether tis nobler in the mind to suffer The slings and arrows of outrageous fortune, Or to take arms against a sea of troubles, And by opposing end them? To die: to sleep; No more; and by a sleep to say we end The heart-ache and the thousand natural shocks That flesh is heir to, tis a consummation Devoutly to be wishd. To die, to sleep; To sleep: perchance to dream: ay, theres the rub; For in that sleep of death what dreams may come When we have shuffled off this mortal coil, Must give us pause: theres the respect That makes calamity of so long life; For who would bear the whips and scorns of time, The oppressors wrong, the proud mans contumely, The pangs of despised love, the laws delay, The insolence of office and the spurns That patient merit of the unworthy takes, When he himself might his quietus make With a bare bodkin? who would fardels bear, To grunt and sweat under a weary life, But that the dread of something after death, The undiscoverd country from whose bourn No traveller returns, puzzles the will And makes us rather bear those ills we have Than fly to others that we know not of? Thus conscience does make cowards of us all; And thus the native hue of resolution Is sicklied oer with the pale cast of thought, And enterprises of great pith and moment With this regard their currents turn awry, And lose the name of action.Soft you now! The fair Ophelia! Nymph, in thy orisons Be all my sins rememberd.

11.5 Hash tables are perfectly suited to the task of counting things like the number of times words are used in a text. By going through the text a word at a time, you can check a hash table to see whether the word has already been seen before. If it hasn't, the word is inserted as a key in the hash able with a value of 1 . If it has been seen, the table is updated to hold the incremented count. Traversing the completed hash table gets the overall word counts. Write a program that reads a text file, extracts the individual words, counts the number of times they occur using a hash table, and then prints out a list of all the distinct words and their counts. To get the lines of a text file in Python, you can use a loop like for line in open('myfile.text', ' r '). To get the words from the line, you can use a loop like for word in line.split(), which splits the string at whitespace characters. To trim off leading and trailing punctuation from a word, you can use the strip() method of strings, as in word.strip(' ()[ ]\{\}-_, .?! : ; ' '). This would convert ' (open-addressing! ) to 'open-addressing", for example. For case-insensitive word counting, you can use the lower () method for strings to make all the characters lowercase. Show the output of your program running on a short text file