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.

1. irudia. Hash taula baten adibidea: telefono-aurkibidea

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

2. irudia. Hash funtzio bateko talkaren adibidea: 873 indize bereko bi gako daude. Kasu horretan, Hashing irekiarekin konpontzen da.

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

3. irudia. Hash funtzio bateko talkaren adibidea: 873 indize bereko bi gako daude. Kasu horretan, Hashing itxita konpontzen da.

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

Kanpo estekak

• Datuak: Q207440
• Multimedia: Hash tables / Q207440