Hakettabelo

From Wikipedia, the free encyclopedia

Hakettabelo
Remove ads

Hakettabelo estas datumstrukturo, realiganta asocian tabelon uzante haketfunkcion.

Thumb
Telefonlibro realigita per hakettabelo.

La principo

Kiel ĉia asocia tabelo, hakettabelo estas aro da datumoj atingeblaj per rultempe komutata ŝlosilo (plej ofte, signoĉeno). Haketfunkcio transformas ajnan ŝlosilon en entjeron uzeblan kiel indico de ordinara unudimensia paŝtabelo.

Kolizioj

Thumb
Solvo de kolizio («John Smith» kaj «Sandra Dee») per penda ligillisto.

Ĉar la nombro de ŝlosiloj estas pli granda ol la nombro de haketaĵoj — kaj, sekve, ol la nombro de lokoj en la indicata paŝtabelo — oni devas antaŭvidi koliziojn, okazojn kiam la loko (indico, haketaĵo) por ĵusveninta ŝlosilo estas okupita de aliŝlosila paro. Estas pluraj strategioj por solvi koliziojn, interalie per la metodo de pendaj ligillistoj.

Remove ads
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads