Java HashMap: açardan dəyərə gedən yol

Eyni tələbəni ikinci dəfə əlavə etsək nə olar?

Tələbələrin balını nömrələrinə görə saxlayırıq. 42 → 85 yazısından sonra eyni açara 92 versək, map-də iki tələbə yaranmır. Mövcud dəyər yenilənir.

Map<Integer, Integer> scores = new HashMap<>();
scores.put(42, 85);
scores.put(42, 92);
System.out.println(scores.get(42)); // 92
System.out.println(scores.size());  // 1

Bəs minlərlə qeyd içindən 42 necə tapılır? HashMap hər dəfə bütün açarlara baxmır. Açarın hash dəyərindən cədvəldə başlanğıc ünvan seçir, sonra həmin yerdə uyğun açarı axtarır. Burada ünvanı tapmaq ilə açarın eyniliyini yoxlamaq ayrı işlərdir.

Hash dəyəri rəf nömrəsinə çevrilir

OpenJDK 21 implementasiyasında hashCode() nəticəsinin yüksək bitləri aşağı bitlərlə qarışdırılır. Cədvəlin ölçüsü ikinin qüvvəsi olduğundan indeks belə seçilə bilir:

int h = key.hashCode();
int hash = h ^ (h >>> 16);
int index = (capacity - 1) & hash;

Bu daxili mexanizmdir; tətbiq kodunda HashMap üçün öz indeks hesablayıcını yazmağa ehtiyac yoxdur. Vizualda kiçik müsbət tam ədədlərdən istifadə edirik: onların hash dəyəri özlərinə bərabərdir və bu nümunədə qarışdırma nəticəni dəyişmir.

8 bucket olduqda 1, 9 və 17 açarları eyni yerə - 1-ci bucket-ə düşür. Bu, məlumatın itməsi demək deyil. Bir bucket bir neçə fərqli açarı saxlaya bilər.

Eyni bucket, fərqli açarlar

get(9) üçün əvvəl 1-ci bucket seçilir. Sonra oradakı qeydlərin saxlanmış hash dəyəri və açarı yoxlanılır. İki açarın bərabərliyi üçün equals müqayisəsi vacibdir: eyni hash dəyəri eyni açar demək deyil.

Bucket qısa olduqda qeydlər zəncir şəklində saxlanılır. Uzun zəncir bəzi şərtlərlə ağaca çevrilə bilər. OpenJDK 21-də əlaqəli hədlər 8 və 64-dür: kiçik cədvəldə toqquşma artanda əvvəl cədvəli böyütmək üstün tutulur. “Səkkizinci elementdə mütləq ağac yaranır” kimi yadda saxlamaq düzgün deyil; əlavə etmə yolu və cədvəlin ölçüsü də rol oynayır.

Müsahibədə əvvəl problemi izah et: çox açar eyni yerə düşəndə zənciri gəzmək baha başa gəlir. Sonra implementasiya detalını əlavə et. Ağaclaşdırma yaxşı hash funksiyasına ehtiyacı aradan qaldırmır.

Açarın dəyişməsi niyə təhlükəlidir?

Təsəvvür et ki, Student obyektinin equals və hashCode metodları email sahəsinə əsaslanır. Obyekti map-ə qoyduqdan sonra email-i dəyişirsən. Növbəti axtarış yeni hash ilə başqa bucket-ə gedə bilər, halbuki qeyd köhnə yerdə qalıb.

Daha sadə seçim dəyişməyən identifikatordur:

record StudentId(long value) {}

Map<StudentId, Integer> scores = new HashMap<>();
scores.put(new StudentId(42), 92);
System.out.println(scores.get(new StudentId(42))); // 92

Burada iki ayrı obyekt eyni identifikatoru ifadə edir. record uyğun equals və hashCode yaradır. Sahə özü dəyişən kolleksiya olsaydı, təkcə record istifadə etmək dərin dəyişməzlik təmin etməzdi.

Qayda: a.equals(b) doğrudursa, onların hash kodları da eyni olmalıdır. Əksi tələb olunmur.

Ölçü böyüyəndə nə dəyişir?

Standart load factor 0.75-dir. 16 bucket üçün hədd 12 qeyd olur; yeni unikal qeyd sayı həddi keçəndə cədvəl böyüyür. Eyni açarın dəyərini yeniləmək ölçünü artırmır.

Cədvəl 8-dən 16-ya böyüsə, nümunəmizdə 1 və 17 1-ci bucket-də qalar, 9 isə 9-cu bucket-ə keçər. Vizualdakı “16 bucket” seçimi bunu göstərir. Dəyərlər dəyişmir, onların cədvəldəki yeri dəyişir.

Gözlənilən qeyd sayı məlumdursa, Java 21-də niyyəti açıq yazmaq olar:

Map<Long, String> users = HashMap.newHashMap(1_000);

Bu, min bucket istəməkdən fərqlidir: gözlənilən min qeyd üçün uyğun başlanğıc ölçüsünü seçir. Həddən artıq böyük ölçü də pulsuz deyil; yaddaş və bütün map-i gəzmək xərci artır.

Real kodda hansı map-i seçərdim?

HashMap özü paralel yazma üçün təhlükəsiz deyil. Sayğacı artırmaqda get və put cütünü “bir əməliyyat” hesab etmə. Uyğun paralel map-də merge kimi atomik əməliyyat seçmək lazımdır.

Yaxşı paylanma şəraitində get və put gözlənilən sabit vaxtda işləyir. Bu, hər giriş üçün dəyişməz zəmanət deyil. Özünü yoxla: 1 və 9 toqquşanda niyə hər ikisi qalır, 1 açarını yenidən yazanda isə niyə ölçü artmır?