-
Notifications
You must be signed in to change notification settings - Fork 0
/
hash_table.py
188 lines (134 loc) · 4.85 KB
/
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
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
import ctypes
from linked_list import LinkedList
class HashTable:
"""
Implementaion of Hashtable by chaining with Linked list
"""
def __init__(self):
"""Initializing the hashtable with a capcity of '3' and load factor of '0.60'"""
self.DEFAULT_CAPACITY = 3
self.LOAD_FACTOR = 0.60
self.capacity = 0
self.size = 0
self.table = self.makearray(self.DEFAULT_CAPACITY)
def hashFunction(self, a, capacity):
"""A simple hash function. If int is passed in it mods the int value and if strings
are passed, it adds the ascii value of the each char and then mods it over capacity"""
if type(a) == str:
temp = a
a = 0
for i in temp:
a += ord(i)
return a % capacity
def add(self, key, value):
"""Adds the key value pair to the hash table"""
hash = self.hashFunction(key, self.capacity)
value = [key, value]
try:
liList = self.table[hash]
index = self.__containsKey(liList, key)
if index >= 0:
self.__removeFromLinkedList(liList, index)
liList.add(value)
except ValueError:
self.table[hash] = None
liList = LinkedList()
liList.add(value)
self.table[hash] = liList
self.size += 1
if self.size / self.capacity > self.LOAD_FACTOR:
self.__resizing()
return True
def remove(self, key):
"""Removes a particular element from the table if it exists"""
hash = self.hashFunction(key, self.capacity)
try:
liList = self.table[hash]
index = self.__containsKey(liList, key)
if index < 0:
return False
self.__removeFromLinkedList(liList, index)
except ValueError:
print("Key does not exist in the hash table")
return False
return True
def __containsKey(self, liList, key):
"""Private method that checks if the key is present in the table and returns the
position of the key in the linked list"""
current = liList.head
i = 0
while current:
if current.data[0] == key:
return i
i +=1
current = current.next
return -1
def __removeFromLinkedList(self, liList, index):
"""Private method that removes the element with the given position of the element
in the linked list"""
current = liList.head
self.size -= 1
if index == 0:
if current.next:
liList.head = current.next
return
liList.head = None
return
prev = None
while index != 0:
prev = current
current = current.next
index -= 1
prev.next = current.next
current.data = None
current = None
def __getitem__(self, key):
"""returns the value of the given key"""
hash = self.hashFunction(key, self.capacity)
try:
liList = self.table[hash]
current = liList.head
while current:
if key == current.data[0]:
return current.data[1]
current = current.next
except ValueError:
pass
print("Key does not exist in hash table")
def __resizing(self):
"""Private method that resizes the hastable when it reaches the threshold limit"""
self.capacity *= 2
oldArray = self.table
self.table = self.makearray(self.capacity)
self.size = 0
for i in range(len(oldArray)):
try:
item = oldArray[i].head
while item:
self.add(item.data[0], item.data[1])
item = item.next
except ValueError:
pass
def __repr__(self):
"""Returns the index and key value pair of all the elements in the hash table"""
tabledata = ''
for i in range(self.capacity):
try:
item = self.table[i].head
while item:
tabledata += "\tIndex: " + str(i) + "\tValues: " + str(item.data) + ",\n"
item = item.next
except ValueError:
pass
tabledata = "HashTable: { \n" + tabledata + "}"
return tabledata
def getSize(self):
"""Returns the size of the hash table"""
return self.size
def getCapacity(self):
"""Returns the capacity of the hash table"""
return self.capacity
def makearray(self, capacity):
"""Returns a new array with the capacity passed in"""
self.capacity = capacity
return (capacity * ctypes.py_object)()