unordered_map konteynerində hash cədvəli necə qurulub?

C++-də unordered_map hash cədvəli kimi həyata keçirilir.

İş prinsipi:

1. Hashing: Açar tam ədədə — hash kodu — çevrilir və hash funksiyası vasitəsilə alınır.
2. İndeksləmə: Hash kodu, göstəricilər və ya siyahılar massivində indeks (kova və ya bucket) müəyyən etmək üçün istifadə olunur.
3. Yadda saxlanılması: Hər bir kovada açar-dəyər cütləri saxlanılır.

Xüsusiyyətlər:

• Kovalar: Hash cədvəli göstəricilər və ya siyahılardan ibarət massivdən ibarətdir. Kovaların sayı dinamik olaraq dəyişə bilər (rehashing) müəyyən yükləmə faktoruna çatdıqda.
• Çəkilmələr: Müxtəlif açarlar eyni hash kodunu verə bilər. Bu, çəkmə adlanır. Çəkilmələri həll etmək üçün unordered_map zəncirləmə metodundan istifadə edir: eyni hash-ə malik elementlər müvafiq kovada əlaqəli siyahıya (və ya başqa məlumat strukturu) əlavə olunur.
• Hash funksiyası və müqayisə funksiyası: Doğru işləmək üçün iki şey lazımdır:
  • Açarları kovalar arasında bərabər paylayan yaxşı bir hash funksiyası, çəkmələri minimuma endirmək üçün.
  • == operatoru ilə eyni hash koduna malik açarları ayırd etmək üçün bərabərlik funksiyası.
• Performans: Orta hesabla, əlavə etmə, silmə və axtarış əməliyyatlarının vaxt mürəkkəbliyi O(1)-dir. Ən pis halda (məsələn, çox sayda çəkmə və ya pis seçilmiş hash funksiyası ilə) performans O(n)-ə qədər pisləşə bilər, burada n elementlərin sayıdır.

Element əlavə etmə prosesi:

1. Açarın hash kodu hesablanır.
2. Kovadakı indeks müəyyən edilir: bucket_index = hash(key) % num_buckets.
3. Açar-dəyər cütü həmin kovadakı siyahıya əlavə olunur. Əgər açar artıq mövcuddursa, dəyər yenilənir.

Element axtarış prosesi:

1. Açarın hash kodu hesablanır.
2. Kovadakı indeks müəyyən edilir.
3. Bu kovadakı siyahı keçilir, açarlar == operatoru ilə müqayisə edilir.

Rehashing, elementlərin sayı kovaların sayına nisbətən müəyyən bir həddi (yük faktoru) aşdıqda baş verir. Rehash zamanı, daha böyük yeni kovalar massiv yaradılır və köhnə kovalardakı bütün elementlər yenidən hash edilərək yeni yerlərə köçürülür.