(Translated by https://www.hiragana.jp/)
Hash taula - Wikipedia, entziklopedia askea. Edukira joan

Hash taula

Wikipedia, Entziklopedia askea
1. irudia. Hash taula baten adibidea: telefono-aurkibidea

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

[aldatu | aldatu iturburu kodea]

Hash tauletatarako oinarrizko eragiketak hauek dira:

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.

Indizea gakoarekin eta hash funtzioarekin kalkulatzen da, eta indize horretako taulako datua lortzen da.

Talkak konpontzea

[aldatu | aldatu iturburu kodea]
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

[aldatu | aldatu iturburu kodea]

Talka eginez gero, gatazkan dauden balioekin zerrenda osatzen da (ikus 2. irudia)

Hashing itxia

[aldatu | aldatu iturburu kodea]
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)

Erreferentziak

[aldatu | aldatu iturburu kodea]

Kanpo estekak

[aldatu | aldatu iturburu kodea]