Hash Table daxili quruluşu

Hash table (JS-də Map/obyekt, Kotlin-də HashMap, Dart-da Map) açar–dəyər cütlərini saxlayır və orta halda O(1) axtarış verir. Bunun arxasında cəmi üç addım dayanır:

• Hash funksiyası açarı tam ədədə çevirir: hash("email") → 2938471
• Bucket indeksi həmin ədədi massivin ölçüsünə sıxır: index = hash % capacity
• Bucket — daxili massivin həmin xanası, cütün faktiki yazıldığı yer

Yəni hash table sehr deyil — o, adi massivdir. Bütün fərq ondadır ki, indeksi sən yox, açardan hesablanan hash verir. Massivdə element axtarmaq üçün gəzmək lazım gəlmir: indeksi bir dəfə hesablayıb birbaşa oraya baxırsan.

Yaxşı hash funksiyası nə deməkdir? Üç tələb:

• Deterministik — eyni açar həmişə eyni hash verir. Əks halda yazdığını heç vaxt tapa bilməzsən.
• Bərabər paylanma — açarlar bucket-lar arasında yayılmalıdır. Hamısı bir bucket-a düşürsə, hash table adi siyahıya çevrilir.
• Sürətli — hash hesablamaq axtarışın özündən baha olmamalıdır.

Diqqət: kriptoqrafik güc burada tələb DEYİL. SHA-256 hash map üçün lazımsız bahadır; real runtime-lar MurmurHash, SipHash və ya sadə 31 * h + char kimi ucuz funksiyalardan istifadə edir.

Bir də çox vacib qayda: hash dəyişməz olmalıdır. Açar kimi istifadə etdiyin obyektin hash-ə təsir edən sahəsini map-a qoyduqdan sonra dəyişsən, element "itir" — o, köhnə bucket-də qalır, sən isə yeni bucket-də axtarırsan.

Niyə orta halda O(1), pis halda O(n)?

Orta hal: hash bərabər paylanıbsa, hər bucket-də orta hesabla 1-ə yaxın element olur. İndeksi hesablamaq O(1), bucket-in içində axtarmaq O(1) — cəmi O(1).

Pis hal: bütün açarlar eyni bucket-a düşürsə (pis hash funksiyası və ya bilərəkdən qurulmuş açarlar), bucket bir zəncirə çevrilir və axtarış O(n) olur. Bu nəzəri qorxu deyil — hash flooding hücumları məhz bunu edir, ona görə də müasir runtime-lar hash-i təsadüfi seed ilə "duzlayır".

Resizing ayrı bir nüansdır: capacity 0.75 həddini keçəndə map ikiqat böyüyür və bütün elementləri yenidən hash-ləyir — o bir put O(n) çəkir. Amma bu n əməliyyata bir dəfə baş verdiyi üçün amortizə olunmuş dəyər yenə O(1) qalır. Ölçünü qabaqcadan bilirsənsə (new HashMap(expectedSize)), bu təkrar rehash-lardan tamam yaxa qurtarırsan.