Hash-table-lərin iş prinsipləri

6.1 Hash-table anlayışı və onun strukturu

Hash-table – bu, məlumatların saxlanılması strukturu olub, hash-funksiyanın köməyi ilə massivdə və ya siyahıda indeksləri hesablamaqla elementləri tez bir zamanda tapmağa, əlavə etməyə və silməyə imkan yaradır. Hash-table-lar adətən assosiativ massivlərin, digər adı ilə lüğətlərin (dictionary) həyata keçirilməsi üçün istifadə olunur.

Hash-table üçün vacib aspektlər

Massiv – hash-table-nın əsas komponentidir, elementlərin və ya element siyahılarının göstəricilərini saxlayır.

Hash-funksiya: Lüğətin açarlarını massiv indekslərinə çevirən funksiyadır.

Kolliziyalar: İki fərqli açarın eyni hash-dəyərə malik olduğu vəziyyət. Kolliziyaların həlli üçün chaining və ya open addressing kimi müxtəlif metodlar istifadə olunur.

Lüğət nümunəsi:

{
   "alma": 101,
   "banan": 102,
   "gilas": 103
}

Hash-table strukturunun nümunəsi:

6.2 Hash cədvəldə əsas əməliyyatlar

Hash cədvəldə əsas əməliyyatlar: əlavə etmə, axtarış, silmə

1. Əlavə etmə (Insertion): Hash cədvələ yeni elementin (açar-dəyər cütü) əlavə olunma prosesi.

Əlavə etmə addımları:

1. Açarın hash dəyərini hash function istifadə edərək hesabla.
2. Arraydə hash dəyərinə əsasən indeksi tap.
3. Əgər həmin indeksdə artıq element varsa (toqquşma), elementi siyahıya əlavə et (zəncirlər halında) və ya növbəti mövcud indeksə keç (açıq ünvanlandırma halında).

Zəncirlərdən istifadə edərək hash cədvələ əlavə etmə misalı:

class HashTable:
    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))

# İstifadə nümunəsi:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)

2. Axtarış (Search): Verilmiş açara görə dəyəri hash cədvəldə tapmaq prosesidir.

Axtarış addımları:

1. Açarın hash dəyərini hash function istifadə edərək hesabla.
2. Arraydə hash dəyərinə əsasən indeksi tap.
3. Açarın, siyahıda (zəncirlər halında) və ya indeksdə (açıq ünvanlandırma halında) mövcudluğunu yoxla.

Zəncirlərdən istifadə edərək hash cədvəldə axtarış misalı:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    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

# İstifadə nümunəsi:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Çıxış: 2
print(hash_table.search("grape"))   # Çıxış: None

3. Silmə (Deletion): Hash cədvəldən elementin (açar-dəyər cütü) silinməsi prosesi.

Silmə addımları:

1. Açarın hash dəyərini hash function istifadə edərək hesabla.
2. Arraydə hash dəyərinə əsasən indeksi tap.
3. Elementi siyahıdan sil (zəncirlər halında) və ya indeksdəki dəyəri None olaraq təyin et (açıq ünvanlandırma halında).

Zəncirlərdən istifadə edərək hash cədvəldə silmə misalı:

class HashTable:
    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 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 = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
hash_table.delete("banana")
print(hash_table.table)
print(hash_table.search("banana"))  # Çıxış: None

6.3 Hash Cədvəlinin Zaman Mürəkkəbliyi

Hash cədvəlində əməliyyatların zaman mürəkkəbliyi

Əlavə Etmə (Insertion):

• Orta hal: O(1)
• Ən pis hal: O(n) (çox sayda toqquşmalar baş verdikdə və ya bütün elementlər eyni hücrəyə düşdükdə)

Axtarış (Search):

• Orta hal: O(1)
• Ən pis hal: O(n) (çox sayda toqquşmalar baş verdikdə və ya bütün elementlər eyni hücrəyə düşdükdə)

Silinmə (Deletion):

• Orta hal: O(1)
• Ən pis hal: O(n) (çox sayda toqquşmalar baş verdikdə və ya bütün elementlər eyni hücrəyə düşdükdə)

İzah:

Orta hal: Orta halda, hash-funksiyası elementləri bərabər şəkildə cədvələ paylayır və hər bir element özünəməxsus hücrədə yerləşir ki, bu da sabit vaxtda giriş təmin edir O(1).

Ən pis hal: Ən pis halda, pis hash-funksiyası və ya çox sayda toqquşma nəticəsində bütün elementlər eyni hücrəyə düşür. Bu halda hash cədvəli əlaqəli siyahıya çevrilir və əməliyyatların zaman mürəkkəbliyi O(n) olur.

6.4 Hash cədvəllərin istifadə nümunələri

1. Lüğətin (assosiativ massiv) realizasiyası

Hash cədvəlləri tez-tez lüğətlərin realizasiyası üçün istifadə olunur, bu da açar-dəyər cütlərini saxlamağa və açar üzrə tez bir şəkildə daxil olmağa imkan verir.

Nümunə:

# Lüğətin yaradılması
dictionary = {}

# Elementlərin əlavə edilməsi
dictionary["apple"] = 1
dictionary["banana"] = 2
dictionary["cherry"] = 3

# Elementin axtarışı
print(dictionary["banana"])  # Nəticə: 2

# Elementin silinməsi
del dictionary["cherry"]

# Açarın mövcud olub-olmamasını yoxlamaq
if "apple" in dictionary:
    print("Açar 'apple' lüğətdə mövcuddur")  # Nəticə: Açar 'apple' lüğətdə mövcuddur

İndi Python-dakı lüğət haqqında bir az daha çox məlumatlısınız və bu necə işlədiyini bilirsiniz.

2. Hesablamaların nəticələrinin keşi

Hash cədvəlləri bahalı hesablamaların nəticələrinin keşlənməsi və sonrakı sorğuların sürətləndirilməsi üçün istifadə olunur.

Nümunə:

# Nəticələrin saxlanması üçün keş
cache = {}

def expensive_computation(x):
    if x in cache:
        return cache[x]
    result = x * x  # Bahalı hesablamanın nümunəsi
    cache[x] = result
    return result

# Keşdən istifadə
print(expensive_computation(10))  # Nəticə: 100 (hesablanır və keşlənir)
print(expensive_computation(10))  # Nəticə: 100 (keşdən)

3. Mətndə sözlərin tezliyinin hesablanması

Hash cədvəlləri hər bir sözün mətndə neçə dəfə göründüyünün hesablanması üçün istifadə olunur.

Nümunə:

from collections import defaultdict

text = "this is a simple text with some simple words this is simple"
word_count = defaultdict(int)

for word in text.split():
    word_count[word] += 1

# Nəticələrin çıxarılması
for word, count in word_count.items():
    print(f"Söz '{word}' {count} dəfə görünür")

4. Siyahıda dublikatların axtarışı

Hash cədvəlləri siyahıda dublikatların effektiv axtarışı üçün istifadə olunur.

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))  # Nəticə: [2, 4]