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

Ö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ış (Effective Java – Madde 8) 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<PhoneNumber, String>();
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. Değeri 0 olmayan bir sabit sayı belirleyin, mesela 17, ve bunu result isimli bir int değişkeninde saklayın.
  2. Nesnenizdeki her bir anlamlı alan (field) için (equals metodunda hesaba katılan alanlar) aşağıdakini uygulayın:
    1. Alan için int türünde bir hash kodu hesaplayın ve bunu c değişkeninde saklayın
      1. Alan boolean türünde ise c = (f ? 1 : 0);
      2. Alan byte, char, short, veya int türünde ise c = (int) f;
      3. Alan long türünde ise c = (int)(f ^ (f <<< 32));
      4. Alan float türünde ise c = Float.floatToIntBits(f);
      5. Alan double türünde ise Double.doubleToLongBits(f); değerini bulup daha sonra long değerine göre işlem yapın
      6. 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 daha karmaşık bir karşılaştırma yapılıyorsa, o zaman nesneyi standart bir biçimde sembolize edip bunun üzerinden hashCode metodunu çağırın. Eğer referans null ise 0 değerini döndürün.
      7. Alan bir dizi ise, dizinin her elemanı ayrı bir alanmış gibi hesaplama yapın. Yani, dizideki her anlamlı alan için yukarıdaki kuralları özyineli olarak uygulayın ve 2.b'de anlatıldığı gibi bunları birleştirin. Eğer dizinin bütün alanları anlamlı ise, Java 1.5 ile eklenen Arrays.hashCode() metotlarından birini kullanabilirsiniz.
    2. Hesapladığınız c değerini şu şekilde result değerine ekleyin: result = 31 * result + c;
  3. result değerini döndürün.
  4. 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. 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.

Yukarıda 1. adımda 0 olmayan bir sayı seçmemizin nedeni, ilk değer atanmamış anlamlı alanların da sonucu etkilemesini istememizdir. Eğer 0 seçmiş olmsaydık, ilk değer atanmamış alanlar 2. adımda yine 0 değerini üreteceği için hesaplamaya katılmamış olacaklardı ve dolayısıyla farklı nesneler için aynı hash kodunu üretme ihtimali artacaktı. 17 değeri keyfi olarak seçilmiştir, başka bir sayı da olabilirdi.

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 = 17;
    result = 31 * result + areaCode;
    result = 31 * result + prefix;
    result = 31 * result + lineNumber;
    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.

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ının bu duruma uyup uymadığı çok açık 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 volatile int hashCode;  // (Madde 71)
    @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;
   }


Burada anlattığımız hash kod hesaplama tarifi genel olarak iyi sonuçlar verse de mükemmel değildir, Java kütüphanelerinin kendi içinde bulunan hash hesaplama metotları da mükemmel değildir.
Böyle fonksiyonlar yazmak bir araştırma konusu olup matematikçilere ve bilgisayar bilimcilerine bırakılmalıdır. Belki de Java platformu gelecekte mükemmel hash fonksiyonları yazmamızı sağlayacak yardımcı araçları bizlere sunacaktır. Bu gerçekleşene kadar, bu yazıda anlatılan yöntemler çoğu uygulama için yeterli olacaktır.

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.

Share

2 Replies to “Effective Java Madde 9: equals() ile Birlikte Mutlaka hashCode() Metodunu da Geçersiz Kılın”

  1. 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.

    1. 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.

Bir Cevap Yazın