-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathinfinite_hash_table.py
92 lines (70 loc) · 2.32 KB
/
infinite_hash_table.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
from __future__ import annotations
from typing import Generic, TypeVar
from data_structures.referential_array import ArrayR
K = TypeVar("K")
V = TypeVar("V")
class InfiniteHashTable(Generic[K, V]):
"""
Infinite Hash Table.
Type Arguments:
- K: Key Type. In most cases should be string.
Otherwise `hash` should be overwritten.
- V: Value Type.
Unless stated otherwise, all methods have O(1) complexity.
"""
TABLE_SIZE = 27
def __init__(self, level: int = 0) -> None:
self.array: ArrayR[tuple[K, V] | None] = ArrayR(self.TABLE_SIZE)
self.count = 0
self.level = level
def hash(self, key: K) -> int:
if self.level < len(key):
return ord(key[self.level]) % (self.TABLE_SIZE-1)
return self.TABLE_SIZE-1
def __getitem__(self, key: K) -> V:
"""
Get the value at a certain key
:raises KeyError: when the key doesn't exist.
"""
raise NotImplementedError()
def __setitem__(self, key: K, value: V) -> None:
"""
Set an (key, value) pair in our hash table.
"""
raise NotImplementedError()
def __delitem__(self, key: K) -> None:
"""
Deletes a (key, value) pair in our hash table.
:raises KeyError: when the key doesn't exist.
"""
raise NotImplementedError()
def __len__(self) -> int:
raise NotImplementedError()
def __str__(self) -> str:
"""
String representation.
Not required but may be a good testing tool.
"""
raise NotImplementedError()
def get_location(self, key) -> list[int]:
"""
Get the sequence of positions required to access this key.
:raises KeyError: when the key doesn't exist.
"""
raise NotImplementedError()
def __contains__(self, key: K) -> 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 sort_keys(self, current=None) -> list[str]:
"""
Returns all keys currently in the table in lexicographically sorted order.
"""
raise NotImplementedError()