Algoritmlarni loyihalashtirish va tahlil qilish

Operatsiyalar uchun psevdokod
chainedHashSearch(T, k)
return T[h(k)]
chainedHashInsert(T, x)
T[h(x.key)] = x //insert at the head
chainedHashDelete(T, x)
T[h(x.key)] = NIL

2. Adreslash-ni oching

Zanjirlashdan farqli o'laroq, ochiq manzillash bir nechta elementlarni bir xil uyaga saqlamaydi. Bu erda har bir slot bitta kalit bilan to'ldirilgan yoki chapda NIL.
Ochiq adreslashda qo'llaniladigan turli xil texnikalar:

i. Chiziqli zondlash

Chiziqli zondlashda to'qnashuv keyingi tirqishni tekshirish orqali hal qilinadi.
h(k, i) = (h′(k) + i) mod m
qayerda

• 
  i = {0, 1, ….}
  
• 
  h'(k)yangi xesh funksiyasi hisoblanadi
  

Agar to'qnashuv da sodir bo'lsa h(k, 0), u h(k, 1)holda tekshiriladi. Shu tarzda, qiymati ichiziqli ravishda oshiriladi.
Chiziqli probing bilan bog'liq muammo shundaki, qo'shni uyalar klasteri to'ldirilgan. Yangi elementni kiritishda butun klaster bo'ylab o'tish kerak. Bu xesh jadvalida operatsiyalarni bajarish uchun zarur bo'lgan vaqtni oshiradi.

ii. Kvadrat zondlash

U chiziqli probga o'xshash ishlaydi, lekin quyidagi munosabat yordamida tirqishlar orasidagi masofa oshiriladi (birdan kattaroq).
h(k, i) = (h′(k) + c₁i + c₂i²) mod m
qayerda,

• 
  c₁va c₂musbat yordamchi konstantalar,
  
• 
  i = {0, 1, ….}
  

iii. Ikki marta xeshlash

Agar xesh funktsiyasi qo'llanilgandan so'ng to'qnashuv sodir bo'lsa h(k), keyingi uyani topish uchun boshqa xesh funksiyasi hisoblanadi.
h(k, i) = (h₁(k) + ih₂(k)) mod m

Yaxshi xash funktsiyalari

Yaxshi xesh funktsiyasi to'qnashuvlarning to'liq oldini olishi mumkin emas, lekin u to'qnashuvlar sonini kamaytirishi mumkin.
Bu erda biz yaxshi hash funktsiyasini topishning turli usullarini ko'rib chiqamiz