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.

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 $($i$.$e$.$ HashNode is None at the key$),$ return the index of the next available empty position in the hash table.

Collision resolution should implement double hashing with hash$1$ as the initial hash and hash$2$ as the step