Emlékezz vissza az Algoritmusok és gráfok tárgyban tanult hash táblákra! Azon belül is most konkrétan a vödrös hash-re. Ennek lényege az volt, hogy ütközések esetén az ütköző elemeket egy listába tesszük:
Implementálj egy ilyen hash táblát! Az egyszerűség és a szemléletesség kedvéért a megvalósítás működjön a következőképp:
- A hash tábla tároljon sztringeket. Tételezd fel, hogy a sztringekben csak ékezet nélküli, kisbetűs szavak vannak, például „alma”, „korte” és „barack”.
- A hash függvény legyen a szó első betűjének ábécébeli sorszáma: a=0, b=1, c=2 és így tovább. Emlékezz vissza a karakterkódok kezelésére, ilyesmivel már találkoztál.
- Az ütközéseket könnyű elképzelni: minden ugyanolyan betűvel kezdődő szó ütközés lesz (pl. „alma”, „ananasz” és „avokado”). De ez nem baj, ennek kezelésére valók a vödrök.
A táblát halmazként fogjuk használni: be lehet tenni, ki lehet venni egy szót, és megnézni, hogy épp benne van-e a szó a táblában. Valósítsd meg az alábbi függvényeket:
hash_tabla_letrehoz(): létrehoz és visszaad egy hash táblát, ahol maga a táblázat létre van már hozva, és üres elemeket tartalmaz. (Vagyis egy olyan listát kell csinálnod, ami üres listákat tartalmaz. Hasonló lesz ez a kétdimenziós listához, de itt a belsők kezdetben üresek.) Vajon hány elemű lesz a tábla, ha a fenti hash függvényt használod?hash_tabla_betesz(tabla, szo): betesz egy szót a táblába. Ha már benne van, nem csinál semmit.hash_tabla_debug(tabla): kiírja a hash tábla tartalmát a kimenetre olyan formában, hogy az segítse a hibakeresést.hash_tabla_benne_van(tabla, szo): megadja, hogy egy szó benne van-e a táblában. Ügyelj arra, hogy az ütközések miatt a vödrökben keresni kell majd.hash_tabla_kivesz(tabla, szo): kivesz egy szót a hash táblából. Ha nincs benne, nem csinál semmit.hash_tabla_listaz(tabla): kiírja a táblában tárolt összes szót ömlesztve.
Ha a kapott sztring alkalmatlan a hasheléshez (nem az „a...z” karakterek valamelyikével kezdődik), dobj kivételt! Ügyelj arra, hogy ne duplikáld a hash számító kódot, inkább írj egy függvényt hozzá!
Teszteld a kapott programod, ellenőrizd a helyes működését! Tegyél a hash tábládba azonos betűvel, és eltérő betűvel kezdődő szavakat is!
Megoldás
def hash_fuggveny(szo):
if ord(szo[0]) < ord('a') or ord(szo[0]) > ord('z'):
raise ValueError("Ékezet nélküli kisbetűvel kezdődjenek a szavak")
return ord(szo[0])-ord('a')
def hash_tabla_letrehoz():
tabla = []
for _ in range(ord('z') - ord('a') + 1):
tabla.append([])
return tabla
def hash_tabla_betesz(tabla, szo):
idx = hash_fuggveny(szo)
if szo not in tabla[idx]:
tabla[idx].append(szo)
def hash_tabla_debug(tabla):
for i in range(len(tabla)):
print(chr(i+ord('a')), end=": ")
for j in range(len(tabla[i])):
print(tabla[i][j], end=" ")
print()
def hash_tabla_benne_van(tabla, szo):
idx = hash_fuggveny(szo)
return szo in tabla[idx]
def hash_tabla_kivesz(tabla, szo):
idx = hash_fuggveny(szo)
tabla[idx].remove(szo)
def hash_tabla_listaz(tabla):
for vodor in tabla:
for szo in vodor:
print(szo, end=" ")
print()
def main():
tabla = hash_tabla_letrehoz()
hash_tabla_betesz(tabla, "alma")
hash_tabla_betesz(tabla, "korte")
hash_tabla_betesz(tabla, "szilva")
hash_tabla_betesz(tabla, "barack")
hash_tabla_betesz(tabla, "banan")
hash_tabla_betesz(tabla, "ananasz")
hash_tabla_betesz(tabla, "bodza")
hash_tabla_betesz(tabla, "zeller")
hash_tabla_debug(tabla)
print("alma: {}".format("benne van" if hash_tabla_benne_van(tabla, "alma") else "nincs benne"))
print("citrom: {}".format("benne van" if hash_tabla_benne_van(tabla, "citrom") else "nincs benne"))
hash_tabla_kivesz(tabla, "zeller")
hash_tabla_listaz(tabla)
main()