Hash table (hashtable, hash, hash map) – key’larni value juftlarini bog’laydigan ma’lumot tuzilmasi. Kodda ko’pincha assotsiativ array (Javascriptda object) ko’rinishida ifodalanadi. Hash table’ning dictionary‘dan farqi – array indekslari integer bo’lib, hash funksiya yordamida generatsiya qilinadi va indekslar unikal bo’ladi.
Hash table amallari ikkiga bo’linadi:
- Hash funksiyada key’dan integer index yasaladi.
- Index ma’lumotning qayerda turishini aniqlaydi.
Hash funksiyaga to’xtalishdan avval, tree‘larga qaytamiz. 
Biz Red-Black tree ma’lumot tuzilmasida ko’rib chiqqanimiz – ma’lumot qo’shish, qidirish, o’chirish amallarini time complexity O(1.00 log N) gacha tushirgan edik. Qo’shish va o’chirishni O(1) gacha tushirishga imkon beradigan ma’lumot tuzilmasi bormi?
Hash table bizga qo’shish/o’chirishdagi tezkorlikni – O(1) ni taqdim etadi. Biz indeksni berilgan ma’lumot asosida generatsiya qilishimiz bois, uning qaysi indeksda turishini aniq bilamiz. Sababi, istalgan paytda ma’lumot asosida indeksni hash funksiyadan generatsiya qila olamiz. Generatsiya qilishda bir xil ma’lumot uchun bir xil integer kod qaytariladi.
Nima uchun integer kod? Ok, to’g’ri, integer bo’lishi shartmas. Chunki Javascriptda Object {} bor. Javascriptning osonligi – object va array ma’lumot saqlashda bir xil ishlatilaveradi. Biz hash funksiyani integer kod generatsiya qiladigan holda ko’ramiz, ammo amaliyotda string kod generatsiya qilishingiz, tayyor bibliotekalardan (masalan string-hash) foydalanishingiz mumkin. Shuni qayd etish kerakki, katta ma’lumotlar bilan ishlaganda hash kodni generatsiya qilish tezligi muhim rol o’ynaydi.
Hash funksiya
Hash funksiya nima qilishini bilamiz. U qanday yasaladi?
Hash kod generatsiyasining asosiy sharti – har xil ma’lumot (string) uchun har xil kod generatsiya qilishi kerak. Aks holda ma’lumotlarni o’qishda chalkashlik (collision) yuzaga keladi.
Biz. Horner metodini ko’rib chiqamiz. Unga ko’ra hash generatsiya qilish uchun matnning har bir harfining (belgisining) ASCII sonini 31 ning L – (index + 1) darajasiga oshirish va har bir harfning yig’indisini qo’shib chiqish kerak bo’ladi. L bu yerda matndagi belgilar soni:
h = s[0] * 31L–1 + … + s[L – 3] * 312 + s[L – 2] * 311 + s[L – 1] * 310
Nima uchun 31? Izlanishlar natijasida, 31, 33, 37, 39 va 41 sonlari bilan hisoblash hash funksiya uchun kam chalkashlik (collision) yaratishi ma’lum bo’lgan.
* * *
Hash table mavzusi Leetcode masalalarida ko’p uchraydi. Masalaga qarab, hash kod generatsiyasiga turlicha yondashish mumkin. Biz permutation masalasini ko’rib chiqamiz.
Masala. Ikki matn berilgan. Ularni solishtirib, bir matn ikkinchisining harflari o’zgargan varianti (permutation) ekanligini tekshirish kerak. Stringdagi belgilar 8 bitli va maksimum 256 xil elementlardan tashkil topgan bo’ladi.
Masalani berilishiga ko’ra, permutation bo’lishi uchun ikki matnning uzunligi bir xil va undagi harflar bir xil bo’lishi kerak. Faqat harflarning o’rni almashgan bo’lishi mumkin. Masalan, «asdfg» va «gsdfa» – permutation matnlar.
Maksimum 256 xil elementlardan bo’lgani uchun 256 uzunlikdagi hashmap (array) yasab olamiz va birinchi matnning elementlarini hashmap’ga yig’amiz. Element indeksi – harfning (belgining) ASCII kodi bo’ladi, qiymatini esa harf qaytarilganda bittaga oshirib boramiz. Shunday qilib bizda birinchi matndagi elementlar va ularning matndagi soni bo’lgan hashmap paydo bo’ladi.
Ikkinchi bosqichda, siklda biz ikkinchi matnning har bir elementini hashmapda bor-yo’qligiga tekshiramiz. Agar yo’q bo’lsa, ikkinchi matn birinchi matnning permutation’i emas. Funksiya ishini to’xtatadi. Sikl tugagach, true qaytaramiz – ikkinchi matndagi barcha elementlar birinchi matnda bor.