Xesh-jadval (Hash Table)

kitob = [("Husanboy", "901234567"), ("Sardor", "912345678"), ("Malika", "935678901")]

def raqamni_top(kitob, ism):
    for saqlangan_ism, raqam in kitob:      # har birini tekshiramiz
        if saqlangan_ism == ism:
            return raqam
    return None

def oddiy_xesh(kalit, hajm):
    """Juda sodda xesh: belgilar kodlari yig'indisi."""
    yigindi = 0
    for belgi in str(kalit):
        yigindi += ord(belgi)
    return yigindi % hajm


for ism in ["Husanboy", "Sardor", "Malika", "Bekzod"]:
    print(f"{ism:<10} -> indeks {oddiy_xesh(ism, 8)}")

class XeshJadval:
    """Zanjirlash usuli bilan ishlaydigan xesh-jadval."""

    def __init__(self, hajm=8):
        self._hajm = hajm
        self._backetlar = [[] for _ in range(hajm)]
        self._soni = 0

    def _indeks(self, kalit):
        """Kalitni backet indeksiga aylantiradi."""
        return hash(kalit) % self._hajm

    def qoy(self, kalit, qiymat):
        """Qiymat qo'yadi yoki yangilaydi. O'rtacha O(1)."""
        backet = self._backetlar[self._indeks(kalit)]

        for i, (saqlangan_kalit, _) in enumerate(backet):
            if saqlangan_kalit == kalit:
                backet[i] = (kalit, qiymat)      # mavjudini yangilaymiz
                return

        backet.append((kalit, qiymat))
        self._soni += 1

        if self.yuk_koeffitsienti() > 0.75:
            self._kengaytir()

    def ol(self, kalit, standart=None):
        """Qiymatni qaytaradi. O'rtacha O(1)."""
        backet = self._backetlar[self._indeks(kalit)]
        for saqlangan_kalit, qiymat in backet:
            if saqlangan_kalit == kalit:
                return qiymat
        return standart

    def ochir(self, kalit):
        """Kalitni o'chiradi."""
        backet = self._backetlar[self._indeks(kalit)]
        for i, (saqlangan_kalit, _) in enumerate(backet):
            if saqlangan_kalit == kalit:
                del backet[i]
                self._soni -= 1
                return True
        return False

    def yuk_koeffitsienti(self):
        """Elementlar soni / backetlar soni."""
        return self._soni / self._hajm

    def _kengaytir(self):
        """Hajmni ikki barobar oshiradi va hammasini qayta joylashtiradi. O(n)."""
        eski_backetlar = self._backetlar
        self._hajm *= 2
        self._backetlar = [[] for _ in range(self._hajm)]
        self._soni = 0

        for backet in eski_backetlar:
            for kalit, qiymat in backet:
                self.qoy(kalit, qiymat)

    def __len__(self):
        return self._soni

    def __contains__(self, kalit):
        backet = self._backetlar[self._indeks(kalit)]
        return any(saqlangan == kalit for saqlangan, _ in backet)

    def holat(self):
        """Backetlarning to'lish holatini ko'rsatadi."""
        for i, backet in enumerate(self._backetlar):
            if backet:
                kalitlar = ", ".join(str(k) for k, _ in backet)
                belgi = "#" * len(backet)
                print(f"  [{i}] {belgi:<6} {kalitlar}")

kitob = XeshJadval()

kitob.qoy("Husanboy", "901234567")
kitob.qoy("Sardor", "912345678")
kitob.qoy("Malika", "935678901")
kitob.qoy("Bekzod", "946789012")

print("Backetlar holati:")
kitob.holat()

print(f"\nSardor raqami: {kitob.ol('Sardor')}")
print(f"Yuk koeffitsienti: {kitob.yuk_koeffitsienti():.2f}")

kitob.ochir("Sardor")
print(f"O'chirgandan keyin: {kitob.ol('Sardor', 'topilmadi')}")

# Buni o'zingiz sinab ko'ring - har safar boshqa natija chiqadi
print(hash("salom"))

# dict - kalit/qiymat
narxlar = {"olma": 12000, "anor": 25000}
print(narxlar["olma"])          # O(1)
print("anor" in narxlar)        # O(1)

# set - faqat kalitlar
korilgan = {"Husanboy", "Sardor"}
print("Malika" in korilgan)     # O(1)

lugat = {}
lugat[(41.311, 69.240)] = "Toshkent"     # kortej - ishlaydi
print(lugat)

try:
    lugat[[1, 2]] = "xato"               # ro'yxat - ishlamaydi
except TypeError as xato:
    print(f"Xato: {xato}")

from collections import defaultdict


def anagrammalarni_guruhla(sozlar):
    """Harflari bir xil so'zlarni guruhlaydi. O(n * k log k)."""
    guruhlar = defaultdict(list)

    for soz in sozlar:
        kalit = "".join(sorted(soz.lower()))     # anagrammalar uchun bir xil
        guruhlar[kalit].append(soz)

    return list(guruhlar.values())


sozlar = ["olma", "malo", "amol", "kitob", "bitok", "daftar"]
for guruh in anagrammalarni_guruhla(sozlar):
    print(guruh)