10.1 Heş funksiyalara və heş cədvəllərə giriş
Gəlin heş funksiyaları və cədvəllər haqqında anlayışımızı genişləndirək. Heş funksiyası — müxtəlif ölçülü giriş məlumatlarını sabit uzunluqda sətirə çevirən alqoritmdir. Heş funksiyaların əsas xüsusiyyətləri:
- Deterministik: eyni giriş məlumatları həmişə eyni nəticəni verir.
- Tez hesablanma: heş kifayət qədər sürətli hesablanmalıdır.
- Geriyə çevirilməzlik (kriptografi heş funksiyalar üçün): heşdən giriş məlumatlarını bərpa etmək mümkün deyil (və ya çox çətindir).
- Bərabər paylama: giriş məlumatlarındakı kiçik dəyişikliklər heşdə böyük dəyişikliklərə səbəb olur.
Sadələşdirsək, eyni obyektlərin funksiyası mütləq üst-üstə düşür, lakin iki obyektin heş funksiyası eyni olsa belə, bu obyektlər mütləq bərabər deyil. Riyaziyyatda buna lazım, lakin kifayət qədər şərt deyilir.
Heş cədvəl — məlumatların səmərəli saxlanması və axtarışı üçün heş funksiyasından istifadə edən məlumat strukturu. O, aşağıdakılardan ibarətdir:
- Məlumatları saxlamaq üçün "səbətlərdən" ibarət massiv.
- Məlumatların hansı səbətə yerləşdiriləcəyini müəyyən edən heş funksiyası.
Heş cədvəllər məlumatlara tez çıxış imkanı verir, adətən orta halda O(1) mürəkkəbliklə.
Heş funksiyaların real həyatda tətbiqi
Misal: Blockchain texnologiyaları
Blockchain-də heş funksiyalar unikal blok identifikatorlarının yaradılması və məlumatların bütövlüyünün təmin edilməsi üçün istifadə olunur. Hər bir blok əvvəlki blokun heşini ehtiva edir, bu da zəncir yaradır və sistemi dəyişikliklərə davamlı edir.
import hashlib
import time
class Block:
def __init__(self, data, previous_hash):
self.timestamp = time.time()
self.data = data
self.previous_hash = previous_hash
self.hash = self.calculate_hash()
def calculate_hash(self):
hash_string = str(self.timestamp) + str(self.data) + str(self.previous_hash)
return hashlib.sha256(hash_string.encode()).hexdigest()
# İstifadə nümunəsi
block1 = Block("Əməliyyat 1", "0")
block2 = Block("Əməliyyat 2", block1.hash)
print(f"Blok 1-in heşi: {block1.hash}")
print(f"Blok 2-in heşi: {block2.hash}")
Performansın müqayisəsi
Massivdə təkrarlanan elementlərin axtarışı məsələsini nəzərdən keçirək. Heş cədvəli ilə və onsuz həlləri müqayisə edək:
import time
def find_duplicates_with_hash(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
def find_duplicates_without_hash(arr):
duplicates = []
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] == arr[j] and arr[i] not in duplicates:
duplicates.append(arr[i])
return duplicates
# Performans testi
arr = list(range(10000)) + list(range(5000)) # Təkrarlanan elementləri olan massiv
start = time.time()
find_duplicates_with_hash(arr)
end = time.time()
print(f"Heş cədvəli ilə icra vaxtı: {end - start} saniyə")
start = time.time()
find_duplicates_without_hash(arr)
end = time.time()
print(f"Heş cədvəli olmadan icra vaxtı: {end - start} saniyə")
Proqramı işə salın və heş cədvəlinin təkrarlanan elementlərin axtarışını nə qədər sürətləndirdiyini görün. Xüsusilə böyük məlumat massivləri üzərində.
10.2 Hash-funksiyaların real problemlərdə tətbiqlərinə nümunələr
1. Parolların hash-edilməsi
Hash-funksiyalar parolların təhlükəsiz saxlanılması üçün istifadə olunur. Parolları açıq şəkildə saxlamaq əvəzinə, sistemlər onların hash-lərini saxlayır. İstifadəçi parol daxil etdikdə, sistem daxil edilən parolu hash edir və onu məlumat bazasında olan hash ilə müqayisə edir.
Tətbiq nümunəsi:
import hashlib
def hash_password(password):
return hashlib.sha256(password.encode()).hexdigest()
# İstifadə nümunəsi:
password = "securepassword"
hashed_password = hash_password(password)
print(f"Parolun hash-i: {hashed_password}")
2. Məlumatların bütövlüyünün yoxlanması
Hash-funksiyalar faylların və məlumatların bütövlüyünü yoxlamaq üçün istifadə edilir. Məsələn, fayl ötürülərkən dəyişdirilib və ya korlanıb-korlanmadığını yoxlamaq üçün.
Tətbiq nümunəsi:
import hashlib
def get_file_hash(file_path):
hasher = hashlib.sha256()
with open(file_path, 'rb') as file:
buf = file.read()
hasher.update(buf)
return hasher.hexdigest()
# İstifadə nümunəsi:
file_hash = get_file_hash('example.txt')
print(f"Faylın SHA-256 hash-i: {file_hash}")
3. Axtarış sistemləri və indeksasiya
Axtarış sistemləri indekslər yaratmaq və məlumatların tez tapılması üçün hash-funksiyalardan istifadə edir. Hər bir sənəd açar sözlərə görə indekslənir və hash-funksiyalar verilən sözləri ehtiva edən sənədləri tez tapmağa kömək edir.
Tətbiq nümunəsi:
def create_index(text):
index = {}
words = text.split()
for word in words:
word_hash = hash(word)
if word_hash not in index:
index[word_hash] = []
index[word_hash].append(word)
return index
# İstifadə nümunəsi:
text = "This is an example text for indexing"
index = create_index(text)
print(f"İndeks: {index}")
10.3 Axtarışın optimallaşdırılması hash-funksiyalar vasitəsilə
1. Dublikatların axtarışı üçün hash-cədvəllərin istifadəsi
Hash-cədvəllər elementlərin hash-dəyərlərini müqayisə edərək massivdə dublikatları tez bir zamanda tapmağa imkan verir.
Reallaşdırma nümunəsi:
def find_duplicates(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
# İstifadə nümunəsi:
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr)) # Çıxış: [2, 4]
2. Verilmiş cəmlə olan cütlərin axtarışının optimallaşdırılması
Hash-cədvəllər massivdə cəmləri verilmiş dəyərə bərabər olan cüt rəqəmləri səmərəli şəkildə tapmağa imkan verir.
Reallaşdırma nümunəsi:
def find_pairs_with_sum(arr, target_sum):
seen = set()
pairs = []
for num in arr:
complement = target_sum - num
if complement in seen:
pairs.append((complement, num))
seen.add(num)
return pairs
# İstifadə nümunəsi:
arr = [2, 4, 3, 7, 8, -2, 10, -1]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum)) # Çıxış: [(4, 2), (8, -2)]
10.4 Hash-funksiyaların müxtəlif alqoritmlərdə istifadəsinə misallar
1. Mətndə sözlərin sayının hesablanması
Mətnin hər bir sözünün daxilolma sayını hesablamaq üçün hash-cədvəl istifadə edin.
Reallaşdırma nümunəsi:
def count_words(text):
word_count = {}
words = text.split()
for word in words:
if word in word_count:
word_count[word] += 1
else:
word_count[word] = 1
return word_count
# İstifadə nümunəsi:
text = "this is a test this is only a test"
print(count_words(text)) # Çıxış: {'this': 2, 'is': 2, 'a': 2, 'test': 2, 'only': 1}
2. İki massiv arasında kəsişmənin yoxlanması
İki massiv kəsişirmi (ən azı bir ümumi elementləri varmı) yoxlayın.
Reallaşdırma nümunəsi:
def has_intersection(arr1, arr2):
set1 = set(arr1)
for item in arr2:
if item in set1:
return True
return False
# İstifadə nümunəsi:
arr1 = [1, 2, 3, 4]
arr2 = [3, 5, 6, 7]
arr3 = [8, 9, 10]
print(has_intersection(arr1, arr2)) # Çıxış: True
print(has_intersection(arr1, arr3)) # Çıxış: False
3. Massivdə elementlərin unikallığının yoxlanması
Massivdə yalnız unikal elementlərin olub-olmadığını yoxlayın.
Reallaşdırma nümunəsi:
def all_unique(arr):
seen = set()
for item in arr:
if item in seen:
return False
seen.add(item)
return True
# İstifadə nümunəsi:
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 2, 3, 4, 5, 3]
print(all_unique(arr1)) # Çıxış: True
print(all_unique(arr2)) # Çıxış: False
GO TO FULL VERSION