Instructions
Requirements and Specifications
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()