Fan Ma’lumotlar tuzilmasi mustaqil ish mavzu: Kalitlarni akslantirish (Heshlashtirish) usuli, samaradorligi xamda reheshlash usuli Guruh: 216-20 Bajardi: Valijonov n tekshirdi: Akbarova M

Xash funktsiyasini tekshirish: h (k, i) bu erda k - kiritilishi kerak bo'lgan asosiy qiymat. Va men bu element bilan to'qnashuv soni.

Misol: Agar biz 2 ni qo'shsak, uning xash qiymatini h (2, 0) yordamida topamiz, chunki bu birinchi to'qnashuv. Deylik, ushbu funktsiya indeksiga javob (indeks) allaqachon ishg'ol qilingan bo'lsa, biz yana h (2, 1) xash funktsiyasiga murojaat qilishimiz kerak.

Lineer zondlash

Xash funktsiyasi h ga teng, xash jadvali 0 dan n-1 gacha bo'lgan bo'shliqlarni o'z ichiga oladi.

Endi biz k elementini kiritmoqchimiz. H (k) ni qo'llang. Agar u "x" ga olib kelsa va "x" indeksida allaqachon qiymat mavjud bo'lsa, biz yana
h (k, 1) ning (h (k) + 1) mod n ga teng bo'lgan xash funktsiyasini qo'llaymiz.

Umumiy shakli: h1 (k, j) = (h (k) + j) mod n

Masalan: funktsiyasi 5 bo'lgan 5 o'lchamdagi xash jadvali 0, 2, 3 pozitsiyalarida to'ldirilgan bo'lsin.

Endi yangi 10-element kiritishga harakat qiladi. 10 mod 5 = 0. Ammo indeks 0 allaqachon egallab olingan. Shunday qilib, keyingi (indeks 1) holatini tekshiradi (problar). Shunday qilib, 10 indeks 1 ga qo'shiladi.

Endi 11-element kiritishga harakat qiladi. 11 mod 5 = 1. Ammo indeks 1 allaqachon ishg'ol qilingan, u ham egallagan 2-indeksni tekshiring (ma'lumotlar berilgan), 3-band ham mavjud. Shunday qilib, u bo'sh 4 indeksiga qo'shiladi.

Keyingi bo'sh joyni chiziqli ravishda tekshirayotganini kuzatishimiz mumkin. Shunday qilib, bu chiziqli probing deb ataladi.

Lineer probirovka bilan bog'liq muammolar: Boshlang'ich klasterlash: doimiy hujayralarni egallash imkoniyati mavjud, keyin yangi element kiritish ehtimoli kamayadi. Ushbu muammo birlamchi klasterlash deb nomlanadi
Ikkilamchi klasterlash: Agar ikkita xash funktsiyasida ikkita element bir xil qiymatga ega bo'lsa, ular bir xil problar ketma-ketligini bajaradilar.