## Question

# This data structure, working on a Hash Table that takes two keys rather than one. In terms of storage, this can be thought of as

This data structure, working on a Hash Table that takes two keys rather than one. In terms of storage, this can be thought of as a hash table of hash tables, where a top-level key is used to determine the first position (which hashtable to insert into) and a bottom-level key is used to determine where in this selected hashtable to insert into:

Here, both the top-level and lower level hash tables use Linear Probing to resolve collisions (Note that Het probes from 0->1->2 and "May, Jim" probes from 4->0->1).

`DoubleKeyTable`

should implement the following methods:

`__init__(self, sizes=None, internal_sizes=None)`

, create the underlying array. If `sizes`

is not None, the provided array should replace the existing `TABLE_SIZES`

to decide the size of the top-level hash table. If `internal_sizes`

is not None, the provided array should replace the existing `TABLE_SIZES`

for the internal hash tables (See `hash_table.py`

for an example)).

`_linear_probe(self, key1: K1, key2: K2, is_insert: bool) -> tuple[int, int]`

, return the:

Index to access in the top-level table, followed by

Index to access in the low-level table

In a tuple.

Your linear probe method should create the internal hash table if `is_insert`

is true and this is the first pair with `key1`

.

`keys(self, key:K1|None = None) -> list[K1|K2]`

If key = None, return all top-level keys in the hash table

If key != None, return all low-level keys in the sub-table of top-level `key`

`values(self, key:K1|None = None) -> list[V]`

If key = None, return all values in all entries of the hash table

If key != None, restrict to all values in the sub-table of top-level `key`

`iter_keys`

and `iter_values`

: The same functionality as above, but this should return an iterator that yields the keys/values one by one rather than searching the entire table at the start. You should NOT get all the keys/values at the start and just iterate through those. That won't be very efficient. Your iterator should only get the next item when it's needed.

Have code use `hash1`

and `hash2`

from the `DoubleKeyTable`

that is already defined.When creating a new internal hash table, set `table.hash = lambda k: self.hash2(k, table)`

. This ensures any internal table uses `hash2`

for hashing keys.

Have both your top-level table and internal tables resize when the load factor of that table increases past 0.5 (See `hash_table.py`

for an example of this logic) These resizes should occur independently (One internal table may be a different size to another, and the top level table should resize when the number of internal tables exceeds 0.5 irrespective of the resizing of the internal tables)

`__getitem__`

, `__setitem__`

, and `__delitem__`

. When deleting, if the key1,key2 pair was the only key1 element in the table, you should clear out the entirety of that internal table so that a new `key1`

with the same hash can be inserted in that position. (See `test_delete`

for more info.)

`table_size(self)`

. Returns the current size of our table.

i have provided the basic structure of code, replace raise with logic.

**the ****sorted**** function and ****dict**** inbuilt type should not be used**

`from _future_ import annotations from typing import Generic, TypeVar, Iterator from data_structures.hash_table import LinearProbeTable, FullError from data_structures.referential_array import ArrayR K1 = TypeVar('K1') K2 = TypeVar('K2') V = TypeVar('V') class DoubleKeyTable(Generic[K1, K2, V]): """ Double Hash Table. Type Arguments: - K1: 1st Key Type. In most cases should be string. Otherwise `hash1` should be overwritten. - K2: 2nd Key Type. In most cases should be string. Otherwise `hash2` should be overwritten. - V: Value Type. Unless stated otherwise, all methods have O(1) complexity. """ # No test case should exceed 1 million entries. TABLE_SIZES = [5, 13, 29, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869] HASH_BASE = 31 def _init_(self, sizes:list|None=None, internal_sizes:list|None=None) -> None: raise NotImplementedError() def hash1(self, key: K1) -> int: """ Hash the 1st key for insert/retrieve/update into the hashtable. :complexity: O(len(key)) """ value = 0 a = 31415 for char in key: value = (ord(char) + a * value) % self.table_size a = a * self.HASH_BASE % (self.table_size - 1) return value def hash2(self, key: K2, sub_table: LinearProbeTable[K2, V]) -> int: """ Hash the 2nd key for insert/retrieve/update into the hashtable. :complexity: O(len(key)) """ value = 0 a = 31415 for char in key: value = (ord(char) + a * value) % sub_table.table_size a = a * self.HASH_BASE % (sub_table.table_size - 1) return value def _linear_probe(self, key1: K1, key2: K2, is_insert: bool) -> tuple[int, int]: """ Find the correct position for this key in the hash table using linear probing. :raises KeyError: When the key pair is not in the table, but is_insert is False. :raises FullError: When a table is full and cannot be inserted. """ raise NotImplementedError() def iter_keys(self, key:K1|None=None) -> Iterator[K1|K2]: """ key = None: Returns an iterator of all top-level keys in hash table key = k: Returns an iterator of all keys in the bottom-hash-table for k. """ raise NotImplementedError() def keys(self, key:K1|None=None) -> list[K1|K2]: """ key = None: returns all top-level keys in the table. key = x: returns all bottom-level keys for top-level key x. """ raise NotImplementedError() def iter_values(self, key:K1|None=None) -> Iterator[V]: """ key = None: Returns an iterator of all values in hash table key = k: Returns an iterator of all values in the bottom-hash-table for k. """ raise NotImplementedError() def values(self, key:K1|None=None) -> list[V]: """ key = None: returns all values in the table. key = x: returns all values for top-level key x. """ raise NotImplementedError() def _contains_(self, key: tuple[K1, K2]) -> bool: """ Checks to see if the given key is in the Hash Table :complexity: See linear probe. """ try: _ = self[key] except KeyError: return False else: return True def _getitem_(self, key: tuple[K1, K2]) -> V: """ Get the value at a certain key :raises KeyError: when the key doesn't exist. """ raise NotImplementedError() def _setitem_(self, key: tuple[K1, K2], data: V) -> None: """ Set an (key, value) pair in our hash table. """ raise NotImplementedError() def _delitem_(self, key: tuple[K1, K2]) -> None: """ Deletes a (key, value) pair in our hash table. :raises KeyError: when the key doesn't exist. """ raise NotImplementedError() def _rehash(self) -> None: """ Need to resize table and reinsert all values :complexity best: O(N*hash(K)) No probing. :complexity worst: O(N*hash(K) + N^2*comp(K)) Lots of probing. Where N is len(self) """ raise NotImplementedError() @property def table_size(self) -> int: """ Return the current size of the table (different from the length) """ raise NotImplementedError() def _len_(self) -> int: """ Returns number of elements in the hash table """ raise NotImplementedError() def _str_(self) -> str: """ String representation. Not required but may be a good testing tool. """ raise NotImplementedError()`

## Tim Jen Ivy Jen Het Liz Bob def hash1(self, key): return ord(key[0]) % 12 def hash2(self, key): return ord(key [-1]) % 5 Key hash1 hash2 Tim, Jen 0 0 Amy, Ben 5 0 May, Ben 5 0 Ivy, Jen 1 0 Amy Ben May, Tom 5 4 Tim, Bob 0 3 May Ben Jim Tom May, Jim 5 4 Het, Liz 0 2

## Step by Step Solution

There are 3 Steps involved in it

### Step: 1

To implement the DoubleKeyTable class as described we can start by setting up the basic structure and methods Below is an implementation that addresses the functionality and constraints provided in th...### Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

### Step: 2

### Step: 3

## Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started