'''
PROJECT 7 - Hash Tables
Name:
PID:
'''
class HashNode:
"""
DO NOT EDIT
"""
__slots__ = ["key", "value", "deleted"]
def __init__(self, key, value, deleted=False):
self.key = key
self.value = value
self.deleted = deleted
def __repr__(self):
return f"HashNode({self.key}, {self.value})"
def __eq__(self, other):
return self.key == other.key and self.value == other.value
class HashTable:
"""
Hash Table Class
"""
__slots__ = ['capacity', 'size', 'table', 'collisions', 'prime_index']
primes = (
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277,
281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389,
397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617,
619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739,
743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859,
863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991,
997)
def __init__(self, capacity=8):
"""
DO NOT EDIT
Initializes hash table
:param capacity: capacity of the hash table
"""
self.capacity = capacity
self.size = 0
self.table = [None] * capacity
i = 0
while HashTable.primes[i] <= self.capacity:
i += 1
self.prime_index = i - 1
def __eq__(self, other):
"""
DO NOT EDIT
Equality operator
:param other: other hash table we are comparing with this one
:return: bool if equal or not
"""
if self.capacity != other.capacity or self.size != other.size:
return False
for i in range(self.capacity):
if self.table[i] != other.table[i]:
return False
return True
def __repr__(self):
"""
DO NOT EDIT
Represents the table as a string
:return: string representation of the hash table
"""
represent = ""
bin_no = 0
for item in self.table:
represent += "[" + str(bin_no) + "]: " + str(item) + '\n'
bin_no += 1
return represent
def __setitem__(self, key, value):
"""
DO NOT EDIT
Allows for the use of the set operator to insert into table
:param key: string key to insert
:param value: value to insert
:return: None
"""
return self.insert(key=key, value=value)
def __getitem__(self, item):
"""
DO NOT EDIT
Allows get operator to retrieve a value from the table
:param item: string key of item to retrieve from tabkle
:return: HashNode
"""
return self.get(item)
def __contains__(self, item):
"""
DO NOT EDIT
Checks whether a given key exists in the table
:param item: string key of item to retrieve
:return: Bool
"""
if self.get(item) is not None:
return True
return False
def _hash_1(self, key):
"""
---DO NOT EDIT---
Converts a string x into a bin number for our hash table
:param x: key to be hashed
:return: bin number to insert hash item at in our table, -1 if x is an empty string
"""
if not key:
return None
hashed_value = 0
for char in key:
hashed_value = 181 * hashed_value + ord(char)
return hashed_value % self.capacity
def _hash_2(self, key):
"""
---DO NOT EDIT---
Converts a string x into a hash
:param x: key to be hashed
:return: a hashed value
"""
if not key:
return None
hashed_value = 0
for char in key:
hashed_value = 181 * hashed_value + ord(char)
prime = HashTable.primes[self.prime_index]
hashed_value = prime - (hashed_value % prime)
if hashed_value % 2 == 0:
hashed_value += 1
return hashed_value
""" **************** Student Section Below ******************************"""
def hash(self, key, inserting=False):
"""
Given a key string return an index in the hash table.
Should implement double hashing.
If the key exists in the hash table, return the index of the
existing HashNode
If the key does not exist in the hash table, return the
index of the next available empty position in the hash table.
Collision resolution should implement double hashing with hash1 as
the initial hash and hash2 as the step size
Note - There are 2 possibilities when hashing for an index:
When inserting a node into the hash table we want to insert into the
next available bin.
When performing a lookup/deletion in the hash table we want to continue
until we either find the proper HashNode or until we reach a bin that
has never held a value. This is to preserve the collison resolution
methodology.
The inserting parameter should be used to differentiate between these
two cases.
Time Complexity: Θ(1)*
Space Complexity: O(1)
:param key:
:param inserting:
:return: type int
"""
pass
def insert(self, key, value):
"""
Use the key and value parameters to add a HashNode to the hash table.
In the event that inserting will exceed or equal a load factor of 0.5
you must grow the table to double the existing capacity.
Time Complexity: Θ(1)*
Space Complexity: O(1)*
:param key:
:param value:
:return: type None
"""
pass
def get(self, key):
"""
Find the HashNode with the given key in the hash table.
Time Complexity: Θ(1)*
Space Complexity: O(1)
:param key:
:return: type HashNode
"""
pass
def delete(self, key):
"""
Removes the HashNode with the given key from the hash table .
If the node is found assign its key and value to None,
and set the deleted flag to True
Time Complexity: Θ(1)*
Space Complexity: O(1)
:param key:
:return:type None
"""
pass
def grow(self):
"""
Double the capacity of the existing hash table.
Do NOT rehash deleted HashNodes
Must update self.prime_index, the value of self.prime_index
should be the index of the largest prime smaller than
self.capacity in the HashTable.primes tuple.
Time Complexity: O(N)
Space Complexity: O(N)
:return: type None
"""
pass
def word_frequency(string, lexicon, table):
"""
The table should contain all words in the lexicon along with their frequencies.
Time Complexity: O(L + N^2)
N is len(string)
L is the len(lexicon)
Space Complexity: O(L)
L is the number of words in the lexicon
Using a python dictionary will result in a 0.
Every string will have a guaranteed exact split.
All words in the string will appear in the lexicon.
No processing/validating should or needs to be done on the string, such as stripping for whitespace, etc.
:param string: type string
:param lexicon: type List[string]
:param table: type HashTable
:return: type HashTable[string: int]
"""
pass