Press "Enter" to skip to content

Effective Java Madde 11: equals() ile Birlikte Mutlaka hashCode() Metodunu da Geçersiz Kılın

Last updated on September 22, 2019

Önemli Not: Hash tabanlı veri yapılarının Java’da nasıl çalıştığını bilmiyorsanız bu yazıyı okumadan önce araştırmanızı şiddetle tavsiye ederim.

Object sınıfından gelen hashCode metodunu gerektiği yerde geçersiz kılmamak (override) birçok hatanın kaynağını oluşturur. equals metodunu geçersiz kıldığınız her sınıfta hashCode metodunu da geçersiz kılmanız gerekir. Bunu yapmamak Object.hashCode metodunun sözleşmesini ihlal etmek demektir, bu da sınıfınızın hash tabanlı HashMap, HashSet, HashTable gibi veri yapılarıyla birlikte kullandığında yanlış çalışmasına yol açar. Bunun sebebi ise Object sınıfından gelen hashCode metodunun hash kodunu hesaplarken nesnenin o anda bulunduğu bellek adresini kullanmasıdır. Her nesnenin bellek adresi farklı olacağı için hesaplanan hash kodu da farklı olacaktır. Object sınıfı belirtiminde tarif edildiği üzere sözleşme genel olarak şu şekildedir:

  • equals karşılaştırmasında kullanılan alanlar sabit kaldığı sürece, hashCode metodu aynı uygulama içerisinde üst üste çağrıldığında her zaman aynı sonucu üretmelidir.
  • Eğer iki nesne equals metoduna göre birbirine eşitse, bu iki nesnenin hashCode metotları da aynı integer değerini üretmelidir.
  • Eğer iki nesne equals metoduna göre eşit değilse, hashCode metodu bu iki nesne için farklı integer sonuçları üretmek zorunda değildir. Ancak yazılımcı bilmelidir ki eşit olmayan nesneler için farklı hash kodları üretmek hash table performansını artırabilir.

equals ile birlikte hashCode metodunu geçersiz kılmadığınız zaman 2. koşulu ihlal etmiş olursunuz: eşit nesneler eşit hash kodu üretmelidir. Bu durumda birbirinden farklı iki nesne equals metoduna göre eşit olsa da, hashCode metoduna göre aralarında pek de bir benzerlik olmayacaktır. Bu yüzden de hashCode metodu sözleşmenin aksine bu iki eşit nesne için çok farklı değerler üretecektir.

Aşağıda equals metodu sözleşmeye uygun bir biçimde yazılmış (Madde 10) PhoneNumber sınıfını düşünecek olursak:

 public final class PhoneNumber {

    private final short areaCode;
    private final short prefix;
    private final short lineNumber;

    public PhoneNumber(int areaCode, int prefix, int lineNumber) {
        rangeCheck(areaCode,    999, "area code");
        rangeCheck(prefix,      999, "prefix");
        rangeCheck(lineNumber, 9999, "line number");

        this.areaCode  = (short) areaCode;
        this.prefix  = (short) prefix;
        this.lineNumber = (short) lineNumber;
    }

    private static void rangeCheck(int arg, int max, String name) {
        if (arg < 0 || arg > max)
            throw new IllegalArgumentException(name + ": " + arg);
    }

    @Override
    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof PhoneNumber))
            return false;

        PhoneNumber pn = (PhoneNumber)o;
        return pn.lineNumber == lineNumber 
            && pn.prefix  == prefix 
            && pn.areaCode == areaCode;
    }

    // Bozuk - hashCode() metodu yok!
}

Şimdi bu sınıfı bir HashMap ile kullandığımızı düşünelim:

Map<PhoneNumber, String> m = new HashMap<>();
m.put(new PhoneNumber(707, 867, 5309), "Jenny");

Bu noktada m.get(new PhoneNumber(707, 867, 5309)) çağrısının “Jenny” değerini döndürmesini bekleyebilirsiniz ancak null dönecektir. Burada iki PhoneNumber nesnesinin olduğuna dikkat edin, bir tanesi HashMap içerisine eklenirken ikinci ve eşit olan nesne HashMap üzerinden değeri geri almak için kullanılıyor. PhoneNumber sınıfının hashCode metodunu geçersiz kılmaması, eşit iki nesnenin farklı hash kodları üretmesine neden olmaktadır. Bu yüzden de get() metodu, aradığımız değeri put() metodunun kullandığı hash bölmesinde (bucket) değil başka bir bölmede arayacaktır ve bulamayacaktır. Tesadüfen bu iki nesnenin hash kodları aynı bölmelere denk gelse bile yine de null değeri dönecektir çünkü Java’da hash tabanlı veri yapıları hash kodları farklı olan nesnelerin eşit olmadığını varsayar ve equals metoduna bakmadan null döndürürler.

Bu problemi çözmek için PhoneNumber sınıfı içerisine uygun bir hashCode metodu yazmak gereklidir. Peki hashCode metodu nasıl olmalıdır? Sözleşmeye uyan ama doğru olmayan bir hashCode metodu yazmak çok basittir. Aşağıdaki örnek hashCode sözleşmesine uysa da asla kullanılmamalıdır:

// Sözleşmeye uyarak yazılabilecek en kötü hashCode(), asla kullanmayın!
@Override
public int hashCode() {
    return 42;
}

Yukarıdaki metod hashCode sözleşmesine uygundur çünkü eşit nesneler için aynı değeri üretecektir. Ancak yine de çok kötü yazılmıştır çünkü sadece eşit nesneler için değil bütün nesneler için aynı değeri üretecektir. Bu yüzden de hash tabanlı veri yapılarıyla birlikte kullanıldığında bütün nesneler aynı hash bölmesine (bucket) eklenecek ve örneğin bir HashTable bağlı liste (linked list) gibi çalışacaktır. Bu da erişim performansını çok büyük oranda olumsuz etkileyecektir. Büyük veri yapıları için bu performans farkı hiç çalışmamakla eşdeğerdir.

İyi bir hashCode metodu eşit olmayan nesneler için büyük oranda farklı değerler üretmelidir. hashCode sözleşmesinde bulunan 3. madde ile anlatılmak istenen tam olarak budur. İdeal bir hash fonksiyonu, makul sayıdaki eşit olmayan bir nesne yığınını, mümkün olan bütün hash kod değerleri üzerinde eşit olarak dağıtabilmelidir. Bu ideal fonksiyonu yazabilmek çok zor olabilir ama yaklaşmak mümkündür. İşte sizlere bir yöntem:

  1. result adında bir int değişken tanımlayın ve ilk değer olarak sınıftaki ilk anlamlı alanın hash kodunu 2.a adımında belirdiği gibi hesaplayarak atayın. (Madde 10’dan hatırlayacağınız üzere, anlamlı alanlar equals hesaplamasında kullanılan, mantıksal eşitlik hesabında kullanılan alanlardır.)
  2. Geriye kalan her anlamlı f alanı için, aşağıdakileri yapın
    1. Bu alan için değeri c olacak şekilde hash kodunu hesaplayın
      1. Eğer anlamlı alan bir ilkel tür ise, IlkelTur.hashCode(f) kullanın, burada tür anlamlı alanın ilkel türüne göre değişecektir, örneğin Short.hashCode(f), Integer.hashCode(f)
      2. Alan bir nesne referansı ise ve sınıfın equals metodu bu alanı karşılaştırırken özyineli olarak referans üzerinden equals metodunu çağırıyorsa, siz de referans nesnenin hashCode metodunu çağırın. Eğer referans null ise 0 değerini döndürün.
      3. Eğer anlamlı alan bir dizi ise, dizinin her elemanı ayrı bir alanmış gibi hesaplama yapın. Yani, dizideki her anlamlı alan için yukarıdaki kuralları uygulayın ve 2.b’de anlatıldığı gibi bunları birleştirin. Eğer dizide anlamlı eleman yoksa 0 haricinde herhangi bir sabit değer, bütün alanları anlamlı ise, Arrays.hashCode() metotlarından birini kullananın.
    2. Yukarıda hesaplanan c hash kodunu, aşağıdaki formülü kullanarak result değişkenine ekleyin
      result = 31 * result + c;
  3. result değerini döndürün.

Yazmayı tamamladığınızda kendinize şu soruyu sorun: Eşit nesneler aynı hash kodunu üretiyor mu? Bunu doğrulamak için birim testler yazın. AutoValue kütüphanesini kullanarak equals ve hashCode metotlarını otomatik ürettiyseniz bu testlere gerek kalmayabilir. Eğer eşit nesneler farklı hash kodları üretiyorsa, problemi bulun ve giderin.

Eşitlik hesaplamasında kullanmadığınız anlamlı alanları hash kod hesabından da mutlaka çıkartmalısınız, aksi taktirde birbirine eşit nesnelerin farklı hash kodları üretmesine sebep olabilirsiniz. Değeri başka anlamlı alanlar kullanılarak hesaplanabilen alanları da isterseniz hash kod hesaplamasından çıkartabilirsiniz.

2.b’de yapılan çarpma işlemi ise anlamlı alanları sırasının da üretilen hash koduna etki etmesini sağlar, bu da eğer sınıf içerisinde çok sayıda benzer alan varsa hash metodunun çok daha iyi çalışmasını sağlar. Örneğin, bu çarpma işlemi String sınıfının hashCode metodunda olmasaydı, bütün anagramlar aynı hash koduna sahip olurlardı. Çarpma işleminde 31 sayısının kullanılmasının sebebi ise asal bir tek sayı olmasıdır. Çift bir sayı seçersek ve çarpma işleminin sonucu maksimum saklayabileceğimiz değeri geçerse veri kaybetmiş oluruz, çünkü sayıyı 2 ile çarpmak bitlerini kaydırmakla eşdeğerdir. Burada asal bir sayı kullanmanın avantajı çok belirgin olmasa da, geleneksel olarak asal tek sayılar kullanılır. 31 sayısının güzel bir özelliği ise, daha iyi performans alabilmek için kaydırma ve çıkarma işlemleri ile ifade edilebilmesidir: 31 * i == (i << 5) - i Bu dönüştürme işlemi çoğu zaman sanal makina tarafından otomatik olarak yapılmaktadır.

Şimdi yukarıdaki tarifi PhoneNumber sınıfına uygulayalım. Bu sınıfta 3 adet anlamlı alan var ve hepsi de short türünde:

@Override 
public int hashCode() {
    int result = Short.hashCode(areaCode);
    result = 31 * result + Short.hashCode(prefix);
    result = 31 * result + Short.hashCode(lineNum);
    return result;
}

Bu metod 3 anlamlı alanı da hesaba katarak basit bir hesaplama ile hash kodu ürettiği için, birbirine eşit PhoneNumber nesnelerinin aynı hash kodunu üreteceği de gayet açıktır. Aslına bakarsanız bu metod PhoneNumber sınıfı için harika bir hashCode metodudur. Basit, hızlı ve eşit olmayan nesneleri farklı hash bölmelerine atamak konusunda gayet başarılı bir iş çıkarmaktadır.

Bu yazıda tarif edilen yöntemle, çoğu durumda yeterli olacak çok iyi hash fonksiyonları yazılabilir, ancak her zaman kusursuz sonuçlar alamayabilirsiniz. Daha üst düzeyde hash fonksiyonları üretebilmek için Guava kütüphanesinin com.google.common.hash.Hashing sınıfına bakabilirsiniz.

Objects sınıfı, istediğiniz sayıda nesneyi geçip bir hash kodu üretebileceğiniz, statik Objects.hash() metodunu barındırmaktadır. Bu metodu kullanarak, tek satırdan oluşan ve bu yazıdaki önerileri uygulayan bir hashCode metodunu kolayca yazabilirsiniz. Dezavantajı ise, geçilen argümanları diziye çevirdiği için ve ilkel türler kullanıldığında boxing ve unboxing yaptığı için biraz daha yavaş çalışmasıdır. Eğer performans uygulamanız için çok kritik değilse bu yolu deneyebilirsiniz. Aşağıda, PhoneNumber sınıfı için bu yöntemle yazılmış bir hash metodu görebilirsiniz:

// Tek satırlık hashCode metodu, vasat performans
@Override 
public int hashCode() {
    return Objects.hash(lineNum, prefix, areaCode);
} 

Eğer bir sınıf değişmez (immutable) ise ve hash kodunu hesaplamak zaman alıyorsa, hash kodunu nesnenin içerisinde saklayıp her defasında hesaplamadan kolayca döndürebilirsiniz. Eğer bu türdeki nesnelerin hash anahtarı olarak kullanılacağını öngörüyorsanız, nesne yaratıldığında hash kodunu hesaplayın, aksi taktirde hashCode metodu ilk defa çağrıldığında hesaplayın. PhoneNumber sınıfı için bu çok gerekli değildir ancak nasıl yapılacağını göstermek için aşağıdaki kodu yazabiliriz:

// Tembel ilklendirme (lazy initialization), ön bellekte saklanan hashCode
private int hashCode;  // ilk değer 0 olacaktır

@Override
public int hashCode() {
    int result = hashCode;
    if (result == 0) {
        result = 17;
        result = 31 * result + areaCode;
        result = 31 * result + prefix;
        result = 31 * result + lineNumber;
        hashCode = result;
    }
    return result;
}

Performansı artırmak için sınıfınızdaki anlamlı alanları hash kod hesaplamasından çıkarmaya çalışmayın. Hash fonksiyonunun daha hızlı çalışmasını sağlayabilirsiniz ancak hash tabanlı veri yapılarınız kullanılamayacak kadar yavaş çalışabilir. Hash fonksiyonu, sizin ihmal ettiğiniz alanlarda farklılaşan nesnelerle karşı karşıya kalırsa, bütün bu nesneleri çok küçük bir hash kod kümesine eşleştirebilir ve bu da hash tabanlı veri yapılarının performansını kötü etkiler. Bu, teoride kalmış bir problem değildir. Java 1.2 öncesinde yazılmış olan String sınıfının hashCode metodu, ilk karakterden başlayıp eşit aralıklarla devam ederek en fazla 16 karakteri dikkate alıyordu. Bu hesaplama yöntemi URL gibi hiyerarşik yapıya sahip karakter dizilerinin için kullanıldığında tam olarak burada anlatılan probleme yol açmıştır.

Özet olarak, equals metodunu geçersiz kıldığınız her durumda hashCode metodunu da geçersiz kılmanız şarttır. Bunu yapmadığınız taktirde uygulamanız yanlış çalışacaktır. Bunu yaparken de, yukarıda anlatıldığı gibi belirtilen kurallara uymanız gerekmektedir. Ancak bunu kendimiz yazmaktansa, Madde 10‘da belirtildiği üzere AutoValue kütüphanesini veya IDE’lerin otomatik kod üretme özelliklerini kullanmak, iyi bir alternatif olacaktır.

Share

3 Comments

  1. Sarkhan
    Sarkhan January 5, 2017

    Merhaba.Bu kismi anlayamadim:”Tesadüfen bu iki nesnenin hash kodları aynı bölmelere denk gelse bile yine de null değeri dönecektir çünkü Java’da hash tabanlı veri yapıları hash kodları farklı olan nesnelerin eşit olmadığını varsayar ve equals metoduna bakmadan null döndürürler.”
    çünkü hashcode-lar tesadüfen aynı olursa demek ki, hashcode-lar eşit ve equals methodu çağırılmalı ve null dönmemesi lazım.

    • seckintozlu
      seckintozlu January 5, 2017

      Hash kodları aynı olsa dediğiniz doğru ancak yazıda söylenen hash kodlar aynı değil ancak aynı bölmelere denk geldiği taktirde null döndürecektir. Örnek vermek gerekirse, 16 bölmeli bir hash veri yapısında 1, 17, 33 gibi değerler aynı bölmeye düşecektir çünkü hepsini 16’ya bolunce 1 kalmaktadır.

Leave a Reply

%d bloggers like this: