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()
 

Transcribed Image Text:

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 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