Идентифиқатор жадвалини дарахт шаклида тузиш

Рехэшлаш усули.
Бу муаммани ечиш усуллардан бири рехэширлаш усулидир.
Бирор элемент А учун n=h(A) хисобланади, агар шу адрес бўйича хотира ячейкаси банд бўлса , n₁=h₁(A) функция қиймати хисобланади агар бу адрес хам банд бўлса элемент бўлса n₂=h₂(A) фукция хисобланади, ва хоказо қачанки бўш адрес топилмаса ёки n_i=n тенг бўлиб қолса, бу холда жадвал тўлган деб хисобланади ва хато беради. Бу усулда идентификаторлар жадвали бўш белгиси билан тўлдирилиши керак масалан “” ёки NULL билан.
H функция куйидаги формула билан ёзилиши мумкин h_i=( h(A) +p_i)mod N_m , бунда p_i – қандайдир формула билан хисобланадиган сон, N_m - идентификатор жадвалидаги элементлар максимал сони. Энг содда усули p_i=i
Шунда формуламиз куйидагича бўлади h_i=(h(A)+i)mod N_m. Бу холда хэш функцияни қиймати бир хил бўлса h(A) ўриндан бошлаб кетма кет ячейкалар бўшлиги текширилади. Танланган формула унча яхши эмас чунки элементлар бир жойга тўпланиб қолади.
М исол тарақасида кетмакет жойлашган n₁,n₂,n₃,n₄,n₅ жадвал ячейкаларни кўрайлик ва А₁,А₂,А₃,А₄,А₅ идентификаторларни жадвалга юклайлик. Функциялар h(A₁)=h(A₂)=h(A₅)=n₁, h(A₃)=n₂, h(A₄)=n₄ тенг бўлсин.
Натижада А₁ элементни қидириш учун факат битта солиштириш етарли, А₂ учун 2, А₃ учун 2, А₄ учун 1 ва А₅ учун 5 солиштириш керак бўлади. Бундан кўриниб турибдики солиштиришлар сони коллизияга боғлиқдир , канча коллизия кам бўлса шунчалик солиштиришлар хам кам бўлади. Ундан ташқари шундай р қиймат топиш керакки у коллизияни жадвал бўйича жипслаштирмасдан кенг тарқатиши керак. Шундай усулдан бири р тасодифий сонлар бўлиши. Кўпайтма кўринишдаги хэш функция h_i=(h(A)*i)mod N_m хам яхши натижа беради.