Project 07: Hash Tables Solution

Assignment Overview
A hash table is a useful data structure when storing and retreiving information. For this assignment, you will be implementing a Hash Table and resolving conflicts using quadratic probing( See D2L, Lecture14_15 for slides and sample code, also Zybooks)

 

 

After which, you will be solving a problem involving strings using your newly created Hash Tables. Test cases will be provided for you to test your code, along with a skeleton file for you to start with where a hash node class has been defined for you.

 
Assignment Deliverables
Be sure to submit your project as a folder named "Project7" and include in the folder:

HashTable.py, a Python3 file
readme.txt, a text file that includes:
Your name and feedback on the project
How long it took to complete
A list of any external resources that you used, especially websites (make sure to include the URLs) and which function(s) you used this information for.
 
Assignment Specifications
The hash node class is fully implemented and provided for you. Do not modify this class.

We have provided the __init__,  __eq__, and hash_function methods in the HashTable class, do not modify these methods. Your task will be to complete the methods listed below in the HashTable class that have not been completed for you. Make sure that you are adhering to the time complexity requirements. Do not modify function signatures in any way.

insert(self, key, value):
Inserts key(string) and value(string) into the HashTable using a HashNode
Resolves conflicts using quadratic probing
If a HashNode with the same key is already present, reassigns the value to the new value
If the load factor is strictly greater than 0.75, calls grow()
Does NOT allow insertion of empty string
Expected time complexity O(1), Worst case O(n) time complexity 
quadratic_probe(self, key):
Runs the quadratic hashing procedure 
Returns the table index of key if key is in the table
If key is not found in the table, returns the next available index
Formula follows that of as i increments:
bucket = (bucket + i*i) % capacity 
Returns -1 if key is empty string
find(self, key):
Takes in a key to search for in the Hash Table
Returns the node with the given key if found, if not found it returns False
Expected time complexity O(1), Worst case O(n) time complexity
lookup(self, key):
Takes in a key to search for in the Hash Table
Returns the value of the node with the given key if found, if not found it returns False
Expected time complexity O(1), Worst case O(n) time complexity
delete(self, key):
Takes in a key to delete in the Hash Table
Deletes by setting node to False
Expected time complexity O(1), O(n) time complexity
grow(self):
Doubles capacity
Rehashes all items in table
O(n) time complexity
rehash(self):
Rehashes all items inside of the table
O(n) time complexity
 

string_difference(string1, string2):
Takes in two strings, uses hash tables to get the difference of characters from the strings
Returns a set of the different characters, grouped by character
Example: string1 = "aabbcc", string2 = "ab"
The result would be a set containing {'a', 'b', 'cc'} - those are the differing characters between the 2 strings
Notice how the c's grouped together in the same string object
Lists and Dictionaries are NOT allowed within this function
O(n) time complexity
 

Assignment Specifications
You are required to add and complete docstrings for each function that you complete.
You are provided with skeleton code for the HashTable class and you must complete each empty function. You may use more functions if you'd like, but you must complete the ones given to you. If you do choose to make more functions, you are required to complete docstrings for those as well.
Make sure that you are adhering to all specifications for the functions, including time complexity.
The use of auxiliary containers, such as but not limited to Sets, Lists, and Dictionaries, are not prohibited in this project and may result in large percentage deductions. A list is allowed within rehash. A set can/must be used in string_difference and should be returned.
Due to the nature and intent of hidden test cases, limited help will be given regarding students failing hidden tests. Exceptions can be made for certain circumstances, but in general less help will be given to students requesting help on failing hidden test cases. The point of hidden cases is to think of edge cases and make sure you test it yourself, not have instructors tell you why you are failing.

 

Project authored by Conner Bean