HashMap, equals ve hashCode

Anahtarla bir şey koydun, aynı anahtarla istedin ve null geldi. Suçlu çoğu zaman HashMap değil, iki küçük metodun iş bölümünü bozan kendi sınıfındır.

İş bölümü

hashCode()?Terimin tanımını açhashCodeNesneyi bir tamsayıya indiren metot. Eşit nesneler aynı sayıyı vermek zorundadır; farklı nesnelerin aynı sayıyı vermesi serbesttir.Sözlükte gör → hangi bucket’a?Terimin tanımını açbucketHashMap'in içindeki dizi gözlerinden biri. Bir anahtar hangi göze düşeceğini hashCode'undan öğrenir.Aynı göze düşen anahtarlar bir zincir (Java 8'den beri kalabalıklaşınca ağaç) oluşturur; equals onların arasından doğrusunu seçer.Sözlükte gör → bakılacağını belirler. equals() ise o bucket’ın içinde hangi girdinin doğru girdi olduğunu.

İkisi birbirinin yerine geçmez: hashCode bir adres, equals bir kimlik kontrolüdür.

Bu yüzden sözleşme tek yönlüdür:

a.equals(b) ise a.hashCode() == b.hashCode() olmak zorundadır. Tersi zorunlu değildir: aynı hashCode’a sahip iki nesne eşit olmayabilir — buna çakışma?Terimin tanımını açhash collisionİki farklı anahtarın aynı bucket'a düşmesi. Hata değil, normaldir — HashMap bunu zincirleyerek çözer.Sözlükte gör → denir ve normaldir.

Satır satır: anahtar kaybolduğunda

En tehlikeli HashMap hatası burada. Girdi silinmez, taşınmaz, hata da vermez — sadece bir daha bulunamaz.

Kural: HashMap anahtarları değişmez?Terimin tanımını açimmutableOluşturulduktan sonra içi değişmeyen nesne. Anahtar olarak güvenlidir, çünkü hashCode'u hiç değişmez.Sözlükte gör → olmalıdır. String, Integer ve record’ların iyi anahtar olmasının sebebi budur.

1
// equals ve hashCode otomatik, alanlar final
2
public record UserId(String value) {}

Kendin gör

Simülatör her adımda bir anahtar ekliyor. Önce varsayılan (iyi hashCode) ile izle, sonra kaliteyi düşür.

1. Berbat — return 42. Bütün anahtarlar tek bucket’a düşüyor. Rastgele anahtar ara düğmesine bas ve equals çağrı sayısına bak — arama artık O(n).
2. Kapasiteyi 64 yap, hashCode’u berbat bırak. Zincir 8’e ulaşınca bucket ağaca dönüşüyor. Aynı testi kapasite 8 ile yap: bu kez treeify yerine resize oluyor.
3. Yük faktörünü %100 yap. Resize sayısı düşüyor ama zincirler uzuyor — yük faktörü tam olarak bu takası ayarlar.
4. Bir anahtarı mutasyona uğrat. Girdi kırmızıya dönüyor ve üstü çiziliyor: az önce satır satır izlediğin hatanın görsel hâli.

Kutuların içinde ne var?

HashMap aslında numaralı kutulardan oluşan bir dolaptır. Kutular doldukça iki şey olur: dolap büyütülür ya da kalabalık bir kutu kendi içini düzenler.

Dolap büyüyünce. Girdiler kutu sayısının dörtte üçünü geçince (yük faktörü 0.75) kutu sayısı ikiye katlanır ve her girdi yeni yerine taşınır. Bu taşıma pahalıdır; kaç eleman koyacağını biliyorsan dolabı baştan büyük aç:

1
// 1000 eleman koyacaksan: 1000 / 0.75 = 1334 → bir üst ikinin kuvveti
2
var map = new HashMap<String, User>(2048);

Kalabalık kutu. Bir kutuda 8 girdi birikirse Java onları daha hızlı aranan bir ağaca çevirir. Buna treeify denir.

1
// capacity = 16 → 16 - 1 = 1111 (binary) → hash'in son 4 biti
2
int index = hash & (capacity - 1);

1
static int hash(Object key) {
2
    int h = key.hashCode();
3
    return h ^ (h >>> 16);   // yüksek 16 biti düşük 16 bitin üstüne XOR'la
4
}

Tuzaklar

== ile equals farkı.

1
Integer a = 127, b = 127;
2
a == b;        // true  — Integer cache -128..127 arasını paylaşır
3

4
Integer c = 128, d = 128;
5
c == d;        // false — cache dışında, farklı nesneler
6
c.equals(d);   // true  — değer karşılaştırması

== referans karşılaştırır, equals değer. Integer cache’i bu farkı 127’ye kadar gizler, sonra açığa çıkarır.

Aşağıdaki program bir bankanın üç HashMap’ine üç farklı anahtar koyuyor: doğru yazılmış bir IBAN record’u, hashCode’u unutulmuş bir döviz çifti ve eklendikten sonra değişen bir ücret anahtarı.

1
// equals, hashCode and toString generated from the component; the value cannot change.
2
public record Iban(String value) {
3

4
    // Normalise once, in the constructor: "TR33 0006 1005 …" and "TR330006100…"
5
    // become the same value, so they are the same map key.
6
    public Iban {
7
        value = value.replace(" ", "").toUpperCase(Locale.ROOT);
8
        if (!value.matches("[A-Z]{2}\\d{2}[A-Z0-9]{11,30}")) {
9
            throw new IllegalArgumentException("not an IBAN: " + value);
10
        }
11
    }
12
}

1
// BUG: equals without hashCode. Two equal pairs get Object's identity hash.
2
public final class CurrencyPair {
3

4
    private final String base;
5
    private final String quote;
6

7
    public CurrencyPair(String base, String quote) {
8
        this.base = base;
9
        this.quote = quote;
10
    }
11

12
    @Override
13
    public boolean equals(Object o) {
14
        return o instanceof CurrencyPair other && base.equals(other.base) && quote.equals(other.quote);
15
    }
16
    // hashCode() missing: the contract "equal objects have equal hash codes" is broken.
17
    // Fix: make it a record, or add `return Objects.hash(base, quote);`
18
}

1
// BUG: a key whose hash depends on a field that can change.
2
public final class FeeKey {
3

4
    private String segment;          // "STANDARD", "PREMIUM", …
5

6
    public FeeKey(String segment) {
7
        this.segment = segment;
8
    }
9

10
    // Called when the customer is upgraded: convenient, and the source of the bug.
11
    public void upgradeTo(String segment) {
12
        this.segment = segment;
13
    }
14

15
    @Override
16
    public boolean equals(Object o) {
17
        return o instanceof FeeKey other && segment.equals(other.segment);
18
    }
19

20
    @Override
21
    public int hashCode() {
22
        return segment.hashCode();
23
    }
24
}

1
public class Main {
2

3
    public static void main(String[] args) {
4
        Map<Iban, String> owners = new HashMap<>();
5
        owners.put(new Iban("TR33 0006 1005 1978 6457 8413 26"), "Ayşe Yılmaz");
6
        System.out.println(owners.get(new Iban("TR330006100519786457841326")));   // Ayşe Yılmaz
7

8
        Map<CurrencyPair, BigDecimal> rates = new HashMap<>();
9
        rates.put(new CurrencyPair("EUR", "TRY"), new BigDecimal("38.4200"));
10
        System.out.println(new CurrencyPair("EUR", "TRY").equals(new CurrencyPair("EUR", "TRY")));  // true
11
        System.out.println(rates.get(new CurrencyPair("EUR", "TRY")));   // null — searched the wrong bucket
12

13
        Map<FeeKey, BigDecimal> transferFees = new HashMap<>();
14
        FeeKey key = new FeeKey("STANDARD");
15
        transferFees.put(key, new BigDecimal("6.50"));
16
        key.upgradeTo("PREMIUM");                                         // hash changes while inside the map
17
        System.out.println(transferFees.get(key));                        // null — same object, lost
18
        System.out.println(transferFees.size());                          // 1    — still there, unreachable
19
    }
20
}

Kendini sına

Önce hızlı bir ısınma: puan yok, kayıt yok.