Hash taula
Hash taula, informatikan, datu-egitura bat da, taula edo array elkartu bat, hainbat balio beste hainbat gakorekin mapatzen dituen datu-egitura bat. Hash taula batek hash funtzio bat erabiltzen du array edo taula bat adierazten duen indizea kalkulatzeko, eta, hortik abiatuta, bilatutako balioa lor daiteke.
Idealki, hash funtzioak indize bakar bati esleituko dio gako bakoitza, baina hash taula gehienek hash funtzio ez-perfektu bat erabiltzen dute, hash funtzioak gako bat baino gehiagorentzat indize bera sortu ditzake, horrela talka bat sortuz (horrelako talka bat gertatzen denean jakin beharko da salbuespen hori kudeatzen).[1][2][3]
Funtzionamendua
aldatuHash tauletatarako oinarrizko eragiketak hauek dira:
Txertaketa
aldatuBalio bat taulan txertatzeko, indizea kalkulatu behar da gakoaren eta hash funtzioaren bidez. Balio hori indizea adierazten duen taulako posizioan gordetzen da. Posizioan aldez aurretik datu bat bazegoen, talka bat gertatu dela esaten da, eta arazo hori konpontzeko, taulako posizio bakoitzari balio bakar bat ez, zerrenda bat eslei dakioke.
Bilaketa
aldatuIndizea gakoarekin eta hash funtzioarekin kalkulatzen da, eta indize horretako taulako datua lortzen da.
Talkak konpontzea
aldatuBi gakok hash bat sortzen badute indize bera adieraziz, dagozkien erregistroak ezin dira posizio berean gorde. Horrelako hasuetan, erregistro berria gordetzeko beste kokaleku bat aurkitu behar da.
Talkak ebazteko teknika ezagunenak:
Hashing irekia
aldatuTalka eginez gero, gatazkan dauden balioekin zerrenda osatzen da (ikus 2. irudia)
Hashing itxia
aldatuTalka bat getatuz gero gero, taulako posizio huts bat betetzen da (ikus 3. irudia)