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).

 Funtzionamendua 
Hash tauletatarako oinarrizko eragiketak hauek dira:

 Txertaketa 
Balio 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 
Indizea gakoarekin eta hash funtzioarekin kalkulatzen da, eta indize horretako taulako datua lortzen da.

 Talkak konpontzea 
Bi 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 
Talka eginez gero, gatazkan dauden balioekin zerrenda osatzen da (ikus 2. irudia)

 Hashing itxia 
Talka bat getatuz gero gero, taulako posizio huts bat betetzen da (ikus 3. irudia)

 Erreferentziak 

 Kanpo estekak 

Kategoria:Informatika
Kategoria:Algoritmoak
Kategoria:Datu-egitura