This problem is long the entire question with the skeleton and test case files can be viewed at ctxt DOT io$/2/$AADwxZSpFA

class HashNode:

DO NOT MODIFY the following attributes$/$functions

Attributes

key: str: The key of the hash node $($this is what is used in

hashing$)$

value: T: Value being held in the node. Note that this may

be any type, such as a str$,$ int, float, dict, or a more

complex object

deleted: bool: Whether or not the node has been deleted

$\_\_$init$\_\_($self$,$ key: str$,$ value: T$,$ deleted: bool $=$ False$)->$ None

Constructs a hash node

key: str: The key of the hash node

value: T: Value being held in the node

deleted: bool: Whether or not the node has been deleted.

Defaults to false

Returns: None

Time Complexity: O$(1)$

$\_\_$str$\_\_($self$)->$ str and $\_\_$repr$\_\_($self$)->$ str

Represents the Node as a string

Returns: str representation of node

Time Complexity: O$(1)$

$\_\_$eq$\_\_($self$,$ other: HashNode$)->$ bool

Compares to see if two hash nodes are equal

other: HashNode: The HashNode we are comparing against

Returns: boolstating whether they are equal

Time Complexity: O$(1)$

class HashTable:

DO NOT MODIFY the following attributes$/$functions

Attributes $($you may edit the values of attributes but do not remove them$)$

capacity: int: Capacity of the hash table

size: int: Current number of nodes in the hash table

table: List: This is where the actual data for our hash

table is stored

prime$\_$index: int: Current index of the prime numbers we are

using in $\_$hash$\_2()$

primes

This is a list of all the prime numbers, from $2$ until $8000,$ used

for $\_$hash$\_2().$ This is a $**\_$class attribute$***,$ so it is

$**$accessed by HashTable.primes, NOT self.primes$()!**$

$\_\_$init$\_\_($self$,$ capacity: int $=8)->$ None

Construct an empty hash table, with the capacity as specified in

the input

capacity: int: Initial capacity of the hash table. Defaults to $8$

Returns: None

Time Complexity: O$(1)$

$\_\_$str$\_\_($self$)->$ str and $\_\_$repr$\_\_($self$)->$ str

Represents the HashTable as a string

Returns: str

Time Complexity: O$($N$)$

$\_\_$eq$\_\_($self$,$ other: HashTable$)->$ bool

Checks if two HashTables are equal

other: HashTable: the hashtable we are comparing against

Returns: boolstating whether or not they are equal

Time Complexity: O$($N$)$

$\_$hash$\_1($self$,$ key: str$)->$ int

The first of the two hash functions used to turn a key into a

bin number

Assume this is O$(1)$ time$/$space complexity

key: str: key we are hashing

Returns: int that is the bin number

Time Complexity: O$(1)($assume$)$

$\_$hash$\_2($self$,$ key: str$)->$ int

The second of the two hash functions used to turn a key into a

bin number. This hash function acts as the tie breaker.

Assume this is O$(1)$ time$/$space complexity

key: str: key we are hashing

Returns: int that is the bin number

Time Complexity: O$(1)($assume$)$

IMPLEMENT the following functions

$\_\_$len$\_\_($self$)->$ int

If you see a function prefixed and suffixed with two underscores, that means it is a magic method and should not

be called directly $($we will deduct points for using them directly$)!!$

For example, this function is called using the Python built$-$in len$()$ method and not $\_\_$len$\_\_().$

Getter for the size of $($the number of elements in$)$ the

HashTable

This function should be one line!

Time Complexity: O$(1)$

Returns: int that is size of hash table

$\_\_$setitem$\_\_($self$,$ key: str$,$ value: T$)->$ None

Sets the value with an associated key in the HashTable

This should be a short, ~$1$ line function. The

majority of the work should be done in the $\_$insert$()$

method!

Time Complexity: O$(1)$

key: str: The key we are hashing.

value: T: The associated value we are storing.

Returns: None

$\_\_$getitem$\_\_($self$,$ key: str$)->$ T

Looks up the value with an associated key in the HashTable

If the key does not exist in the table, raises a KeyError.

This should be a short, ~$3$ line function$-$ majority of the work should be done in the $\_$get$()$ method!

Time Complexity: O$(1)$

key: str: The key we are searching.

Returns: The value associated to the provided key.

$\_\_$delitem$\_\_($self$,$ key: str$)->$ None

Deletes the value with an associated key in the HashTable

If the key does not exist in the table, it raises a KeyError

This should be a short, ~$3$ line function$-$ majority of the work should be done in the $\_$get$()$ and

$\_$delete$()$ methods!

Time Complexity: O$(1)$

key: str: The key we are deleting the associated value of$.$

Returns: None

$\_\_$contains$\_\_($self$,$ key: str$)->$ bool

Determines if a node with the key denoted by the parameter exists in the table

This should be a short, ~$3$ line function$-$ majority of the work should be done in the $\_$get$()$ method!

Time Complexity: O$(1)$

key: str: The key we are checking to be a part of the hash table.

Returns: True if key is in the HashTable, False otherwise

$\_$hash$($self$,$ key: str$,$ inserting: bool $=$ False$)->$ int

Given a key string, return an index in the hash table.

Should implement probing with double hashing.