#🔒 Implementing a Double key Table
upbeat vortex
For this first data structure, we'll be 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). Note there are custom hash functions used in the test cases, which are also illustrated in the image above. (The same example is used for test_double_hash.py in test_example.)
Your DoubleKeyTable should implement the following methods:
_linear_probe(self, key1: K1, key2: K2 | None, is_insert: bool) -> tuple[int, int] | int, return the:
if key2 = None, the Index to access the item in the top-level table
is key2 != None, a tuple containing the Index to access the item in the top-level table and the Index to access the item in the bottom-level table
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. In the case that the key isn't found, raise KeyError.
values(self, key:K1|None = None) -> list[V]
If key = None, return all values in all entries in the entire double key hash table (including both the top level and bottom levels)
If key != None, restrict to all values in the sub-table of top-level key. In the case that the key isn't found, raise KeyError.
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 your code use hash1 and hash2 from the DoubleKeyTable that is already defined.
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)
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.)
SCAFFOLD PROVIDED
Can Someone help with this??|?
twilit oceanBOT
@upbeat vortex
Python help channel closed