Hash jadvali qanday komponentlardan iborat?

Hash jadvali ikki asosiy komponentdan iborat:

1. Array (yoki ro'yxat) qutilar (kublar): Bu asosiy saqlash tuzilmasi. Har bir quti bitta yoki bir nechta ma'lumot elementlarini (kalit-qiymat juftliklari) saqlashi mumkin.

2. Hash funktsiyasi: Kirish kalitini raqamli indeksga aylantiradigan algoritm, bu indeksdan foydalanib, mos keladigan ma'lumot elementining saqlanadigan yoki topiladigan qutisi aniqlanadi.

Shuningdek, koliziyalarni hal qilish uchun (turli kalitlar bir xil indeksga hashlangan hollarda) quyidagi mexanizmlar qo'llaniladi:

• Zanjir usuli: Har bir qutida, bu indeksga hashlangan elementlarning ro'yxati (masalan, bog'langan ro'yxat) saqlanadi.
• Ochiq manzillash usuli: Koliziya yuzaga kelganda, algoritm belgilangan strategiya bo'yicha (chiziqli qidirish, kvadrat qidirish, juft hashlash) keyingi bo'sh qutini qidiradi.

# Oddiy hash funktsiyasi misoli
def simple_hash(kalit, array_oyligi):
    # Kalitni raqamga aylantirish
    if isinstance(kalit, str):
        hash_qiymat = sum(ord(harf) for harf in kalit)
    elif isinstance(kalit, int):
        hash_qiymat = kalit
    else:
        raise TypeError("Qo'llab-quvvatlanmaydigan kalit turi")

    # Indeksni array o'lchamida qaytarish
    return hash_qiymat % array_oyligi

# Zanjir usuli uchun qutilar komponenti misoli
class HashTable:
    def __init__(self, array_oyligi):
        self.array_oyligi = array_oyligi
        self.array = [[] for _ in range(self.array_oyligi)] # Ro'yxatlar arrayi (zanjirlar)

    def joylash(self, kalit, qiymat):
        indeks = simple_hash(kalit, self.array_oyligi)
        self.array[indeks].append((kalit, qiymat)) # Kalit-qiymat juftligini ro'yxatga qo'shish

    def qidir(self, kalit):
        indeks = simple_hash(kalit, self.array_oyligi)
        for k, v in self.array[indeks]:
            if k == kalit:
                return v
        return None # Kalit topilmadi