-
Notifications
You must be signed in to change notification settings - Fork 1
/
ChainingHashTableProblema.py
269 lines (200 loc) · 7.72 KB
/
ChainingHashTableProblema.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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
# Implementação de HashTable com tratamento de colisão por encadeamento
# Autor: Alex Sandro
from typing import List
from ListaEncadeadaOrdenada import Lista
class AbsentKeyException(Exception):
def __init__(self,msg):
super().__init__(msg)
class Entry:
"""Uma classe privada utilizada para encapsular os pares chave/valor"""
def __init__( self, entryKey:any, entryValue:any):
self.key = entryKey
self.value = entryValue
def __eq__(self, outroObjeto):
'''Método que vai possibilitar comparar chaves quando a chave for um objeto de outra classe'''
return self.key == outroObjeto.key
def __ne__(self, outroObjeto):
'''Método que vai possibilitar comparar chaves quando a chave for um objeto de outra classe'''
return self.key != outroObjeto.key
def __lt__(self, outroObjeto):
'''Método que vai possibilitar comparar chaves quando a chave for um objeto de outra classe'''
return self.key < outroObjeto.key
def __gt__(self, outro_objeto):
'''Método que possibilita comparar chaves quando a chave for um objeto de outra classe'''
return self.key > outro_objeto.key
def __le__(self, outroObjeto):
'''Método que vai possibilitar comparar chaves quando a chave for um objeto de outra classe'''
return self.key <= outroObjeto.key
def __ge__(self, outroObjeto):
'''Método que vai possibilitar comparar chaves quando a chave for um objeto de outra classe'''
return self.key >= outroObjeto.key
def __str__( self )->str:
return "(" + str( self.key ) + ":" + str( self.value ) + ")"
class ChainingHashTable:
def __init__(self, size=10):
self.size = size
# inicializa a tabela de dispersão com uma série de lists vazios
self.table = list(Lista() for i in range(self.size))
def __hash(self, key:any):
''' Método que retorna a posição na tabela hashing conforme a chave.
Aplicação do cálculo do hash modular.
'''
return hash(key) % self.size
def put(self, key:any, value:any)->int:
'''
Adiciona um par chave/valor à tabela hash
Se a chave já existir, não insere, pois não é permitido chaves duplicadas
'''
slot = self.__hash( key )
# print(f'key {key} mapeada ao slot {slot}')
# varre as entradas da ht para ver se já existe a chave
if not self.table[slot].estaVazia():
if self.contains(key):
return "Chave já existente" #
entry = Entry(key,value)
self.table[slot].inserir(entry)
return slot
def get(self, key:any)->any:
'''
Obtem o valor armazenado na entrada referente à chave "key"
'''
try:
FoundedKey = self.__getObejctByKey(key)
return FoundedKey.value
except:
raise AbsentKeyException(f'Chave {key} inexistente na tabela hash')
def __str__(self)->str:
info = "{ "
for items in self.table:
# examina se o slot da tabela hash tem um list com elementos
if items == None:
continue
for entry in items:
info += str(entry)
info += " }"
return info
def __len__(self)->int:
count = 0
for i in self.table:
count += len(i)
return count
def keys(self)->List[any]:
"""Retorna uma lista com as chaves armazenadas na hashTable.
"""
result = []
for lst in self.table:
if not lst.estaVazia():
for entry in lst:
result.append( entry.key )
return result
def values(self)->List[any]:
"""Retorna uma lista com as chaves armazenadas na hashTable.
"""
result = []
for lst in self.table:
if not lst.estaVazia():
for entry in lst:
result.append( entry.value )
return result
def contains( self, key:any )->bool:
"""Return True se somente se a tabela hash tem uma entrada com a chave passada
como argumento.
"""
entry = self.__locate( key )
return isinstance( entry, Entry )
def __locate(self, key)->Entry:
'''
Método que verifica se uma chave está presente na tabela hash e devolve a
entrada correspondente quando a busca é realizada com sucesso
'''
try:
entry = self.__getObejctByKey(key)
return entry
except:
return None
def remove(self, key:any)->Entry:
'''
Método que remove a entrada correspondente à chave passada como argumento
'''
try:
slot = self.__hash(key)
entry = self.__getObejctByKey(key)
posicao = self.BinarySearch(self.table[slot], entry)
self.table[slot].remover(posicao)
return entry
except:
raise AbsentKeyException(f'Chave {key} não está presente na tabela hash')
def displayTable(self):
entrada = -1
for items in self.table:
entrada += 1
print(f'Entrada {entrada:2d}: ', end='')
if len(items) == 0:
print(' None')
continue
for entry in items:
print(f'[ {entry.key},{entry.value} ] ',end='')
print()
def BinarySearch(self, lista, chave):
inicio = 1
fim = len(lista)
# Enquanto houver distância entre inicio e fim
while (inicio <= fim ):
meio = (inicio + fim)//2
if ( chave < lista.elemento(meio) ):
fim = meio - 1 # Ajusta a pos. final
elif ( chave > lista.elemento(meio)):
inicio = meio + 1 # Ajusta a pos. inicial
else:
return meio # elemento foi encontrado!
# Se finalizar o laço, percorreu todo o lista e
# não encontrou
return -1
def __getObejctByKey(self, key):
"""_summary_
Args:
key (_any_): _description_
Returns:
_type_: _description_
"""
slot = self.__hash(key)
capsula = Entry(key, None)
try:
search = self.BinarySearch(self.table[slot], capsula)
FoundedKey = self.table[slot].elemento(search)
return FoundedKey
except:
raise AbsentKeyException(f"Chave {key} não está presente na tabela hash")
# size = int(input("Enter the Size of the hash table : "))
# table1 = ChainingHashTable(size)
# # storing elements in table
# table1.put("Alex",'Alex Objeto')
# table1.displayTable()
# table1.put("alex",'alex Obejto')
# table1.displayTable()
# table1.put("31",'nathan')
# table1.put("90",'alice')
# print('len',len(table1))
# table1.put("28",'matheus')
# table1.put("88",'duda')
# table1.put("17",'jessika')
# table1.put("22",'bruno')
# table1.put("13",'Devyd')
# table1.displayTable()
# print('get():', table1.get("Alex"))
# table1.displayTable()
# print(table1.keys())
# print(table1.values())
# print()
# print(table1)
# table1.put('ed-tsi','Estrutura de Dados')
# table1.displayTable()
# print(table1.remove("31"))
# print(table1.remove("90"))
# print(table1.remove("28"))
# print(table1.remove("88"))
# print(table1.remove("17"))
# print(table1.remove("22"))
# print(table1.contains("Alex"))
# print(table1.contains("alex"))
# print("Devyd é:", table1.contains("13"))