Hash Table

Xesh-jadval (Hash table) ma'lumotlar tuzilmasi elementlarni kalit-qiymat (key-value) juftliklari ko'rinishida saqlaydi:

• Kalit (Key) — qiymatlarni indekslash va tezkor topish uchun ishlatiladigan yagona identifikator (butun son yoki satr).
• Qiymat (Value) — berilgan kalitga biriktirilgan asosiy ma'lumot.

Xeshlash — Xesh-funksiya

Xesh-jadvalda yangi indeks kalitlar yordamida hisoblab chiqiladi. Ushbu kalitga mos keluvchi ma'lumot esa hisoblangan indeksda saqlanadi. Bu jarayon xeshlash (hashing) deb ataladi.

Aytaylik, k — kalit, h(x) esa xesh-funksiya bo'lsin. Bu yerda h(k) bizga k ga bog'langan elementni saqlash uchun yangi massiv indeksini hisoblab beradi.

Xesh to'qnashuvi

Xesh-funksiya bir nechta turli xil kalitlar uchun bir xil indeks qiymatini hosil qilganda ziddiyat yuzaga keladi (ya'ni o'sha bitta slotga qaysi element joylashtirilishi kerakligi muammosi). Bu holat xesh to'qnashuvi (hash collision) deb ataladi.

Biz xesh to'qnashuvlarini quyidagi usullardan biri orqali hal qilishimiz mumkin:

1. Zanjirlash usuli (Collision resolution by chaining)
2. Ochiq manzillash (Open Addressing): Chiziqli tekshirish (Linear Probing), Kvadratik tekshirish (Quadratic Probing) va Ikkilamchi xeshlash (Double Hashing)

1. Zanjirlash usuli orqali to'qnashuvni hal qilish

Zanjirlash (chaining) usulida, agar xesh-funksiya bir nechta turli elementlar uchun bir xil indeks ishlab chiqarsa, ushbu elementlar ikki tomonlama bog'langan ro'yxat yordamida o'sha indeksga zanjir ko'rinishida ulanadi.

Agar j sloti bir nechta elementlar uchun tayinlangan bo'lsa, u ro'yxatning birinchi tuguniga (head) ko'rsatkichni saqlaydi. Agar slotda hech qanday element bo'lmasa, j o'zida NIL (yoki Go tilida nil) qiymatini saqlaydi.

Zanjirlash amallarining psevdokodi:

chainedHashSearch(T, k)
  T[h(k)] ni qaytarish (qidirilgan element)

chainedHashInsert(T, x)
  T[h(x.key)] = x // elementni ro'yxat boshiga kiritish

chainedHashDelete(T, x)
  T[h(x.key)] = NIL // elementni o'chirish

2. Ochiq manzillash

Zanjirlash usulidan farqli o'laroq, ochiq manzillash (open addressing) bitta slotga bir nechta elementlarni joylashtirmaydi. Bu yerda har bir slot yo bitta kalit bilan band qilinadi yoki NIL qilib bo'sh qoldiriladi.

Ochiq manzillashda quyidagi texnikalardan foydalaniladi:

i. Chiziqli tekshirish

Chiziqli tekshirishda to'qnashuv yuz bersa, navbatdagi keyingi bo'sh slot tekshiriladi:

h(k, i) = (h'(k) + i) mod m

bunda:

• i = {0, 1, ...}
• h'(k) — asosiy xesh-funksiya

Agar h(k, 0) da to'qnashuv yuz bersa, h(k, 1) tekshiriladi. Shu tariqa i qiymati chiziqli tarzda 1 tadan oshirib boriladi.

Chiziqli tekshirishning asosiy muammosi shundaki, yonma-yon joylashgan slotlar to'lib, klasterlar hosil bo'ladi. Yangi element kiritishda butun klasterni aylanib chiqishga to'g'ri keladi, bu esa amallar tezligini pasaytiradi.

ii. Kvadratik tekshirish

Kvadratik tekshirish chiziqli tekshirishga o'xshash ishlaydi, ammo slotlar orasidagi masofa kvadratik tenglama orqali oshiriladi:

h(k, i) = (h'(k) + c1*i + c2*i^2) mod m

bunda:

• c1 va c2 — musbat yordamchi o'zgarmaslar
• i = {0, 1, ...}

iii. Ikkilamchi xeshlash

Agar asosiy h(k) xesh-funksiyasi qo'llanilgandan so'ng to'qnashuv sodir bo'lsa, keyingi bo'sh slotni hisoblash uchun ikkinchi xesh-funksiyadan foydalaniladi:

h(k, i) = (h1(k) + i*h2(k)) mod m

Yaxshi xesh-funksiyalar

Yaxshi xesh-funksiya to'qnashuvlarni butunlay bartaraf etolmasligi mumkin, biroq to'qnashuvlar ehtimolini minimal darajaga tushiradi.

Yaxshi xesh-funksiyani yaratishning mashhur usullari:

1. Bo'lish usuli

Agar k — kalit, m — xesh-jadvalning hajmi bo'lsa, xesh-funksiya quyidagicha hisoblanadi:

h(k) = k mod m

Masalan, agar xesh-jadval hajmi 10 va k = 112 bo'lsa, h(k) = 112 mod 10 = 2. Jadval o'lchami m sifatida odatda 2 ning darajasi tanlanmaydi, chunki ikkilik formatda 2 ning darajalari quyi tartibli bitlarga bog'lanib qoladi. Eng yaxshi natija uchun m sifatida tub son tanlanadi.

2. Ko'paytirish usuli

h(k) = floor(m * (k*A mod 1))

bunda:

• k*A mod 1 ifodasi k*A ko'paytmasining kasr qismini beradi
• floor — pastga yaxlitlash amali
• A — 0 va 1 oralig'idagi o'zgarmas son. Knuth tomonidan tavsiya etilgan optimal qiymat: A ≈ (√5 - 1) / 2 ≈ 0.6180339887...

3. Universal xeshlash

Universal xeshlashda xesh-funksiya oldindan belgilanmasdan, kalitlardan mustaqil ravishda tasodifiy (random) tarzda tanlanadi.

Xesh-jadvalning Go, Python, Java, C va C++ tillaridagi dasturiy kodi

// Hash Table implementation in Go
package main

import "fmt"

// Kalit-qiymat juftligi
type KeyValue struct {
	key  int
	data string
}

// Xesh-jadval strukturasi (Zanjirlash usuli bilan)
type HashTable struct {
	capacity int
	table    [][]KeyValue
}

// Tub sonni tekshirish
func checkPrime(n int) bool {
	if n <= 1 {
		return false
	}
	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

// Jadval sig'imi uchun eng yaqin tub sonni topish
func getPrime(n int) int {
	if n%2 == 0 {
		n++
	}
	for !checkPrime(n) {
		n += 2
	}
	return n
}

// Yangi xesh-jadval yaratish
func NewHashTable(capacity int) *HashTable {
	primeCap := getPrime(capacity)
	return &HashTable{
		capacity: primeCap,
		table:    make([][]KeyValue, primeCap),
	}
}

// Xesh-funksiya
func (ht *HashTable) hashFunction(key int) int {
	return key % ht.capacity
}

// Ma'lumot qo'shish yoki yangilash
func (ht *HashTable) insertData(key int, data string) {
	index := ht.hashFunction(key)

	// Agar kalit mavjud bo'lsa, qiymatini yangilaymiz
	for i, kv := range ht.table[index] {
		if kv.key == key {
			ht.table[index][i].data = data
			return
		}
	}

	// Aks holda yangi kalit-qiymat juftligini qo'shamiz
	ht.table[index] = append(ht.table[index], KeyValue{key: key, data: data})
}

// Ma'lumotni o'chirish
func (ht *HashTable) removeData(key int) {
	index := ht.hashFunction(key)
	for i, kv := range ht.table[index] {
		if kv.key == key {
			ht.table[index] = append(ht.table[index][:i], ht.table[index][i+1:]...)
			return
		}
	}
}

// Xesh-jadvalni chop etish
func (ht *HashTable) display() {
	for i := 0; i < ht.capacity; i++ {
		fmt.Printf("table[%d]", i)
		for _, kv := range ht.table[i] {
			fmt.Printf(" --> (%d: %s)", kv.key, kv.data)
		}
		fmt.Println()
	}
}

func main() {
	ht := NewHashTable(10)

	ht.insertData(123, "apple")
	ht.insertData(432, "mango")
	ht.insertData(213, "banana")
	ht.insertData(654, "guava")
	ht.insertData(213, "orange") // 213 kalitidagi qiymat yangilanadi

	fmt.Println("Hash Table:")
	ht.display()

	fmt.Println("\nAfter removing 123:")
	ht.removeData(123)
	ht.display()
}

Xesh-jadvalning qo'llanilishi

Xesh-jadvallar quyidagi sohalarda keng qo'llaniladi:

• O'zgarmas vaqtda qidirish va qo'shish (O(1) lookup and insertion) talab qilinadigan ma'lumotlar bazalari va tizimlarda
• Kriptografik ilovalar va xavfsizlik protokollarida
• Katta hajmdagi ma'lumotlarni indekslashda (indexing data)
• Kesh tizimlarida (cache)