Create A Program to Implement a Hash Table in A Python Assignment Solution

Instructions

Objective

Write a python assignment program to implement a hash table.

Requirements and Specifications

Override Python len() function to work with HashTable in a specific way - Using def __len__ will override the Python len() function. The way this is implemented should be to return the number of items stored in the hash table (note: this is *not* the same as HashTable's "size" field). 2. Override Python in operator - This will be done using def __contains__ and should be implemented so this operator will then return a boolean when used in statements of the form 54 in myhashtable. For this example, the function should return True if 54 is an existing key in the HashTable instance myhashtable, and False if it is not. 3. Override Python del operator - This is done by using def __delitem__ and should allow for a key/value pair to be removed from an instance of HashTable (e.g. del h[54]). Think about how you want to handle cases when deleting a key that was involved with collisions. Be sure to include in the documentation for this method any assumptions/restrictions on how this can be used. 4. Modify exiting put method to resize an instance as needed - The current HashTable implementation is limited in that it is not able to gracefully handle the case when an item is added to already full HashTable instance. This method should be modified to deal with this= more gracefully, and should resize the instance for the user. Be sure to include documentation here describing exactly when you choose to resize and how you select an appropriate new size (remember that prime numbers are preferred for sizes, in order to avoid clustering, or an even more severe but subtle issue). 5) All of those methods should be clearly documented to describe how and why the implementation is defined as it is. You will also want to use unittest on this assignment. One good use case for unittest will be to add a few items (and maybe even delete) one, and then to use unittest to verify that the slots and data fields are equal to what you expect. All of the extensions that you've added should be tested as well.

Screenshots of output

Source Code

import unittest class HashTable: """ A class to represent a basic HashTable, which is essentially a crude implementation of Python's dict(tionary) class Attributes/Fields ----------------- size : int size of hashtable instance representing total capacity slots: list list object to store keys after hashing - at location: hash(key) data: list list object to store data after hashing - at location: hash(key) Methods ------- put(key, data) ... YOU CAN LIST YOUR CLASS METHODS HERE AND DOCUMENT/DESCRIBE THEM MORE BELOW ... """ def __init__(self, size): """ insert comments (in your words) """ self.size = size self.slots = [None] * self.size self.data = [None] * self.size # using deleted list to mark slot as deleted ("lazy-deletion") self.deleted = [None] * self.size # we will store current number of elements as an member field self.len = 0 def __len__(self): # return corresponding member field return self.len def __contains__(self, item): hashvalue = HashTable.hashfunction(item, self.size) # we don't want to make more steps than a full cycle over slots, # so we count steps. The same idea everywhere, where probing is considered counter = 0 while counter < self.size: # if current slot is empty and this slot was not deleted before, # it means, that there is no such key in hashtable if self.slots[hashvalue] is None and self.deleted[hashvalue] is None: return False # if current slot content is equal to item, it means we found given key if self.slots[hashvalue] == item: return True # moving further along the slot list hashvalue = HashTable.rehash(hashvalue, self.size) counter += 1 # if nothing was found during a full cycle, there is no given element in the hashtable return False def __getitem__(self, key): # return result of inner get method return self.get(key) def __setitem__(self, key, data): # return result of given put method self.put(key, data) def __delitem__(self, key): hashvalue = HashTable.hashfunction(key, self.size) counter = 0 while counter < self.size: # if current slot is empty and this slot was not deleted before, # it means, that there is no such key in hashtable # so, we have nothing to delete if self.slots[hashvalue] is None and self.deleted[hashvalue] is None: return # if current slot content is equal to item, we have to delete it # setting None to corresponding slot and data cell # also marking this slot as deleted, for not to lose elements which were put after # this one because of probing # reducing hashtable length if self.slots[hashvalue] == key: self.slots[hashvalue] = None self.data[hashvalue] = None self.deleted[hashvalue] = True self.len -= 1 return # moving further along the slot list hashvalue = HashTable.rehash(hashvalue, self.size) counter += 1 def put(self, key, data): # if hash table size is equal to number of elements, which are in the hashtable, # we have to increase hashtable size if self.len == self.size: self.resize() hashvalue = self.hashfunction(key, self.size) # trying to put data at first calcukated place if self.slots[hashvalue] is None: # setting key and data, # unmark deleted flag for current slot # increasing hashtable length self.slots[hashvalue] = key self.data[hashvalue] = data self.deleted[hashvalue] = None self.len += 1 else: if self.slots[hashvalue] == key: # if current slot already contains given key # just update data self.data[hashvalue] = data else: # iterating over slots to find the same key or empty slot nextslot = HashTable.rehash(hashvalue, self.size) counter = 0 while self.slots[nextslot] is not None and self.slots[nextslot] != key and counter < self.size: nextslot = HashTable.rehash(nextslot, self.size) counter += 1 # if current slot as empty, putting element here if self.slots[nextslot] is None: self.slots[nextslot] = key self.data[nextslot] = data self.deleted[nextslot] = None self.len += 1 else: # here we found the given key. Just updating data self.data[nextslot] = data self.deleted[nextslot] = None def get(self, key): hashvalue = self.hashfunction(key, len(self.slots)) counter = 0 while counter < self.size: # if current slot contains given key, return its data if self.slots[hashvalue] == key: return self.data[hashvalue] # if current slot is empty, and it was not deleted, breaking the cycle if self.slots[hashvalue] is None and self.deleted[hashvalue] is None: break # moving further along the slot list hashvalue = self.hashfunction(key, len(self.slots)) counter += 1 # no key was found, return None return None def resize(self): # method for resizing size of hashtable # copying old table lists old_slots = self.slots old_data = self.data old_size = self.size # calculating new hashtable size self.size = HashTable.nextsize(self.size) # creating new lists of new sizes self.slots = [None] * self.size self.data = [None] * self.size self.deleted = [None] * self.size # setting length to 0 self.len = 0 # putting all elements from all lists to new empty hashtable for i in range(old_size): if self.slots is not None: self.put(old_slots[i], old_data[i]) @staticmethod def hashfunction(key, size): # static method for calculating key has return key % size @staticmethod def rehash(oldhash, size): # static method for calculating next hash, based on old hash return (oldhash + 1) % size @staticmethod def nextsize(size): # method to find next relevant size of hashtable # 1. New size must be prime # 2. New size must be at least 2 times bigger, than previous # starting with first appropriate odd numbet start = 2 * size + 1 while True: # checking if start is prime or not # starting to find divisors, beginning from 2 i = 2 is_prime = True # keep checking until i is less than sqrt(start) while i * i < start: # if i divides start, then start is not prime if start % i == 0: is_prime = False break # incrementing candidate divisor i += 1 # if start, is prime, return it if is_prime: return start # current start is not prime, taking next odd value start += 2 class TestHashTable(unittest.TestCase): def testPutMethod(self): h = HashTable(7) h[6] = 'cat' h[11] = 'dog' h[21] = 'bird' h[27] = 'horse' print("-" * 10, " data check ", "-" * 10) expected = [21, 27, None, None, 11, None, 6] self.assertEqual(h.slots, expected) expected = ['bird', 'horse', None, None, 'dog', None, 'cat'] self.assertEqual(h.data, expected) self.assertEqual(4, len(h)) h[34] = 'pig' h[41] = 'frog' h[48] = 'cow' h[55] = 'snake' expected = [34, None, None, None, 21, 55, 6, 41, None, None, 27, 11, None, None, 48, None, None] self.assertEqual(h.slots, expected) expected = ['pig', None, None, None, 'bird', 'snake', 'cat', 'frog', None, None, 'horse', 'dog', None, None, 'cow', None, None] self.assertEqual(h.data, expected) self.assertEqual(8, len(h)) print(" + HashTable 'put' all items in correctly") print() def testInMethod(self): h = HashTable(7) keys = [] h[6] = 'cat' keys.append(6) h[11] = 'dog' keys.append(11) h[21] = 'bird' keys.append(21) h[27] = 'horse' keys.append(27) print("-" * 10, " in operator ", "-" * 10) for i in range(100): self.assertEqual(i in h, i in keys) h[34] = 'pig' keys.append(34) h[41] = 'frog' keys.append(41) h[48] = 'cow' keys.append(48) h[55] = 'snake' keys.append(55) for i in range(100): self.assertEqual(i in h, i in keys) print(" + 'in' operator correctly implemented") print() def testLenMethod(self): print("-" * 10, " len() function ", "-" * 10) h = HashTable(7) keys = [] self.assertEqual(len(h), 0) h[6] = 'cat' self.assertEqual(len(h), 1) h[11] = 'dog' self.assertEqual(len(h), 2) h[21] = 'bird' self.assertEqual(len(h), 3) h[27] = 'horse' self.assertEqual(len(h), 4) h[34] = 'pig' self.assertEqual(len(h), 5) h[41] = 'frog' self.assertEqual(len(h), 6) h[48] = 'cow' self.assertEqual(len(h), 7) h[55] = 'snake' self.assertEqual(len(h), 8) print(" + 'len' function works properly") print() def testLenAfterMethod(self): print("-" * 10, " len() after deletion ", "-" * 10) h = HashTable(7) keys = [] h[6] = 'cat' keys.append(6) h[11] = 'dog' h[21] = 'bird' keys.append(21) h[27] = 'horse' keys.append(27) del h[11] for i in range(100): self.assertEqual(i in h, i in keys) self.assertEqual(len(h), 3) print(" + 'in' operator works correctly after 11 was removed") print() def testDelMethod(self): h = HashTable(7) keys = [] h[6] = 'cat' keys.append(6) h[11] = 'dog' keys.append(11) h[21] = 'bird' keys.append(21) h[27] = 'horse' keys.append(27) h[34] = 'pig' keys.append(34) h[41] = 'frog' keys.append(41) h[48] = 'cow' keys.append(48) h[55] = 'snake' keys.append(55) print("-" * 10, " data after deletion ", "-" * 10) for i in range(100): if i in keys: keys.remove(i) del h[i] self.assertEqual(len(h), len(keys)) for j in range(100): self.assertEqual(j in h, j in keys) print(" + data is correct after deletion") print() def main(): h = HashTable(7) h[6] = 'cat' h[11] = 'dog' h[21] = 'bird' h[27] = 'horse' print("-" * 10, " keys and values ", "-" * 10) print(h.slots) print(h.data) print() # unittest_main() - run unittest's main, which will run TestHashTable's methods def unittest_main(): unittest.main() # evaluates to true if run as standalone program (e.g. $ python hashtable.py) if __name__ == '__main__': main() unittest_main()