-
Notifications
You must be signed in to change notification settings - Fork 0
/
hashTable.py
168 lines (133 loc) · 5.62 KB
/
hashTable.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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#!python
from linkedlist import LinkedList, Node
class HashTable(object):
def __init__(self, init_size=8):
"""Initialize this hash table with the given initial size."""
# Create a new list (used as fixed-size array) of empty linked lists
self.buckets = [LinkedList() for _ in range(init_size)]
self.size = 0
def __str__(self):
"""Return a formatted string representation of this hash table."""
items = ['{!r}: {!r}'.format(key, val) for key, val in self.items()]
return '{' + ', '.join(items) + '}'
def __repr__(self):
"""Return a string representation of this hash table."""
return 'HashTable({!r})'.format(self.items())
def _bucket_index(self, key):
"""Return the bucket index where the given key would be stored."""
# Calculate the given key's hash code and transform into bucket index
return hash(key) % len(self.buckets)
def keys(self):
"""Return a list of all keys in this hash table.
TODO: Running time: O(???) Why and under what conditions?"""
# Collect all keys in each bucket
all_keys = []
for bucket in self.buckets:
for key, value in bucket.items():
all_keys.append(key)
return all_keys
def values(self):
"""Return a list of all values in this hash table.
TODO: Running time: O(???) Why and under what conditions?"""
# TODO: Loop through all buckets
# TODO: Collect all values in each bucket
all_values = []
for bucket in self.buckets:
for key, value in bucket.items():
all_values.append(value)
return all_values
def items(self):
"""Return a list of all items (key-value pairs) in this hash table.
TODO: Running time: O(???) Why and under what conditions?"""
# Collect all pairs of key-value entries in each bucket
all_items = []
for bucket in self.buckets:
all_items.extend(bucket.items())
return all_items
def length(self):
"""Return the number of key-value entries by traversing its buckets.
TODO: Running time: O(???) Why and under what conditions?"""
# TODO: Loop through all buckets
# TODO: Count number of key-value entries in each bucket
counter = 0
for bucket in self.buckets:
for item in bucket.items():
counter += 1
return self.size
def contains(self, key):
"""Return True if this hash table contains the given key, or False.
TODO: Running time: O(???) Why and under what conditions?"""
# TODO: Find bucket where given key belongs
# TODO: Check if key-value entry exists in bucket]
index = self._bucket_index(key)
bucket = self.buckets[index]
entry = bucket.find(lambda key_value: key_value[0] == key)
if entry:
return True
else:
return False
def get(self, key):
index = self._bucket_index(key)
bucket = self.buckets[index]
entry = bucket.find(lambda key_value: key_value[0] == key)
if entry:
return entry[1]
else:
raise KeyError('Key not found: {}'.format(key))
def set(self, key, value):
"""Insert or update the given key with its associated value.
TODO: Running time: O(???) Why and under what conditions?"""
# TODO: Find bucket where given key belongs
# TODO: Check if key-value entry exists in bucket
# TODO: If found, update value associated with given key
# TODO: Otherwise, insert given key-value entry into bucket
index = self._bucket_index(key)
bucket = self.buckets[index]
entry = bucket.find(lambda key_value: key_value[0] == key)
if entry:
bucket.delete(entry)
self.size -= 1
entry = (key,value)
bucket.append(entry)
self.size += 1
def delete(self, key):
"""Delete the given key from this hash table, or raise KeyError.
TODO: Running time: O(???) Why and under what conditions?"""
# TODO: Find bucket where given key belongs
# TODO: Check if key-value entry exists in bucket
# TODO: If found, delete entry associated with given key
# TODO: Otherwise, raise error to tell user delete failed
index = self._bucket_index(key)
bucket = self.buckets[index]
entry = bucket.find(lambda key_value: key_value[0] == key)
if entry:
bucket.delete(entry)
self.size -= 1
else:
raise KeyError('Key not found: {}'.format(key))
def test_hash_table():
ht = HashTable()
print('hash table: {}'.format(ht))
print('\nTesting set:')
for key, value in [('I', 1), ('V', 5), ('X', 10)]:
print('set({!r}, {!r})'.format(key, value))
ht.set(key, value)
print('hash table: {}'.format(ht))
print('\nTesting get:')
for key in ['I', 'V', 'X']:
value = ht.get(key)
print('get({!r}): {!r}'.format(key, value))
print('contains({!r}): {}'.format('X', ht.contains('X')))
print('length: {}'.format(ht.length()))
# Enable this after implementing delete method
delete_implemented = True
if delete_implemented:
print('\nTesting delete:')
for key in ['I', 'V', 'X']:
print('delete({!r})'.format(key))
ht.delete(key)
print('hash table: {}'.format(ht))
print('contains(X): {}'.format(ht.contains('X')))
print('length: {}'.format(ht.length()))
if __name__ == '__main__':
test_hash_table()