7.1 Hash cədvəlində kolliziyaların müəyyən edilməsi
Hash cədvəlində kolliziya o zaman baş verir ki, iki müxtəlif açar eyni array-in indeksinə hash-lənir. Bu, eyni hücrəni hash cədvəlində birdən artıq elementin tutmağa çalışmasına gətirib çıxarır.
Kolliziya nümunəsi:
Təsəvvür edin, bizdə sadə bir hash-funksiya var, hansı ki, açarın cədvəlin ölçüsünə bölünməsindən alınan qalığı qaytarır. 5 və 15 açarları üçün, əgər cədvəl ölçüsü 10-dursa, hər iki açar eyni indeks verəcək: 5 % 10 = 5 və 15 % 10 = 5. Bu kolliziyadır.
Daha bir misal:
Fərz edin ki, siz adlardan ibarət bir sözlük (dictionary) qurursunuz və sadə bir hash-funksiya var, hansı ki, adın ilk hərfini qaytarır. Amma məlum olur ki, adların 80%-i «A» hərfi ilə başlayır. Bu təkcə kolliziya deyil, bu problemdir.
7.2 Toqquşma həlli metodları – zəncirlər
Hash-table-larda toqquşmaların həlli üçün bir neçə metod mövcuddur. Ən çox istifadə olunan iki metod zəncirlər (chaining) və açıq ünvanlama (open addressing) metodlarıdır.
Zəncirlər (Chaining)
Üstünlüklər:
- İcrası sadədir.
- Az sayda toqquşma olduqda effektivdir.
- Hash-table-ın dolma sıxlığından asılılığı azdır.
Mənfi cəhətlər:
- Bağlı siyahılarda göstəricilər üçün əlavə yaddaş tələb edir.
- Uzun zəncirlər səbəbindən çox sayda toqquşma olduqda performans azala bilər.
Zəncir metodunun tətbiq nümunəsi:
insert funksiyasının iş xüsusiyyətini öyrənə bilərsiniz, amma mən rahatlıq üçün tam kodu qeyd etmək qərarına gəldim.
class HashTableChaining:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
if self.table[index] is None:
self.table[index] = [(key, value)]
else:
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
def search(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return None
for k, v in self.table[index]:
if k == key:
return v
return None
def delete(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
del self.table[index][i]
return
# İstifadə nümunəsi:
hash_table = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # Giriş: 2
hash_table.delete("banana")
print(hash_table.search("banana")) # Giriş: None
7.3 İkinci metod – açıq adresasiya
Açıq adresasiya metodu koliziya baş verdikdə massivdə növbəti mövcud hüceyrəni axtarmaqdan ibarətdir. Yeni hüceyrənin axtarışı üçün müxtəlif strategiyalar mövcuddur: xətti probasiya, kvadratik probasiya və ikiqat hashing.
Üstünlüklər:
- Pointer-ləri saxlamaq üçün əlavə yaddaş tələb etmir.
- Dataların daha kompakt təqdimatı.
Mənfi cəhətlər:
- Cədvəl doluluq sıxlığı yüksək olduqda performans əhəmiyyətli dərəcədə azala bilər.
- Koliziya həlli üçün daha çox hesablama resursları tələb edir.
Açıq adresasiya strategiyalarına nümunələr
Xətti probasiya (Linear Probing):
- Addım 1 ilə probasiya:
index = (index + 1) % size. - Sadədir, amma "klasterizasiya"ya səbəb ola bilər.
Kvadratik probasiya (Quadratic Probing):
- Addım kvadrata artır:
index = (index + i^2) % size. - Klasterizasiya problemini azaldır, amma reallaşdırması çətindir.
İkiqat hashing (Double Hashing):
- Addımı hesablamaq üçün ikinci hash-funksiya istifadə olunur:
index = (index + i * hash2(key)) % size. - Klasterizasiya problemi daha azdır, amma reallaşdırması çətindir.
Açıq adresasiya metodunun reallaşdırmasına nümunə (xətti probasiya): Mən tam işlək kod təqdim edəcəyəm, sadəlik üçün insert funksiyasının işini analiz edə bilərsiniz
class HashTableOpenAddressing:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.size
if index == original_index:
raise Exception("Hash cədvəli doludur")
self.table[index] = (key, value)
def search(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % self.size
if index == original_index:
break
return None
def delete(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = None
return
index = (index + 1) % self.size
if index == original_index:
break
# İstifadə nümunəsi:
hash_table = HashTableOpenAddressing(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # Çıxış: 2
hash_table.delete("banana")
print(hash_table.search("banana")) # Çıxış: None
7.4 Toqquşmaların hash-cədvələ təsiri
Toqquşmaların performansa təsiri.
Orta müraciət zamanı:
- İdeal şərtlərdə (toqquşma olmadıqda) hash-cədvəldəki elementlərə müraciət üçün orta zaman
O(1)olur. - Toqquşmalar müraciət zamanını artırır, çünki zəncirlər və ya hüceyrələr üzrə probing emalı tələb olunur və bu da əməliyyatların sayını artırır.
Zəncirlərin uzunluğunun artması:
- Zəncir metodu zamanı çoxlu toqquşmalar zamanı zəncirlərin uzunluğu artır və bu da axtarış, əlavə etmə və çıxarma əməliyyatları üçün xətti müraciət zamanına
O(n)səbəb ola bilər. - Uzun zəncirlər elementin axtarışı və ya əlavə edilməsi üçün tələb olunan müqayisələrin sayını artırır.
Yaddaşın mürəkkəbliyi:
- Zəncir metodu zamanı qoşulan siyahılar üçün göstəriciləri saxlamaq üçün əlavə yaddaş tələb olunur.
- Açıq adresasiya metodunda cədvəlin müəyyən səviyyədən üstün (adətən təxminən 70-80%) doldurulması toqquşmaların sayını və buna bağlı olaraq müraciət zamanı əhəmiyyətli dərəcədə artırır.
Klasterləşmə: Açıq adresasiya metodunda (xüsusilə xətti probing istifadə edilən zaman) klasterləşmə baş verir, bir neçə ardıcıl hüceyrə dolur, bu isə toqquşmaların ehtimalını artırır və performansı pisləşdirir.
Toqquşmaların performansa təsirinin analiz nümunəsi:
Bu, məhz daha dərindən araşdırmaq istəyənlər üçündür
import time
import random
# Xətti probing
class HashTableOpenAddressing:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.size
if index == original_index:
raise Exception("Hash table is full")
self.table[index] = (key, value)
def search(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % self.size
if index == original_index:
break
return None
# Əlavə üçün çoxlu məlumatların yaradılması
hash_table = HashTableOpenAddressing(1000)
keys = [random.randint(1, 10000) for _ in range(800)]
# Məlumatların daxil edilməsi və zamanın ölçülməsi
start_time = time.time()
for key in keys:
hash_table.insert(key, key)
print(f"Əlavə vaxtı: {time.time() - start_time:.6f} saniyə")
# Məlumatların axtarışı və zamanın ölçülməsi
start_time = time.time()
for key in keys:
hash_table.search(key)
print(f"Axtarış vaxtı: {time.time() - start_time:.6f} saniyə")
GO TO FULL VERSION