Hash Map Implementation with Separate Chaining

This problem requires you to implement a hash map that supports the basic operations: insert, delete, and search. The hash map uses separate chaining to resolve collisions. The hash function is defined as $$h(k)=\text{hash}(k)\mod n$$ where \(n\) is the table size.

You are given a sequence of operations. Each operation is one of the following commands:

• insert key value: Insert the key-value pair into the hash map. If the key already exists, update its value.
• delete key: Remove the key-value pair with the given key from the hash map. If the key does not exist, do nothing.
• search key: Search for the given key in the hash map and print its associated value. If the key does not exist, print None.

The input operations will be provided through stdin and the output should be printed to stdout. Only the search operations produce output.

inputFormat

The input begins with an integer t representing the number of operations. The following t tokens represent operations. Each operation is provided on a separate line and is one of the following forms:

• insert key value
• delete key
• search key

All inputs are read from stdin.

outputFormat

For each search operation, output the associated value if found; otherwise, output None. Each output should be printed on a new line to stdout.

## sample

6
insert key1 value1
insert key2 value2
search key1
insert key1 updated_value1
search key1
search key3

value1
updated_value1
None

</p>