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 nesneninhashCode
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:
result
adında birint
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.)- Geriye kalan her anlamlı
f
alanı için, aşağıdakileri yapın- Bu alan için değeri
c
olacak şekilde hash kodunu hesaplayın- 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ğinShort.hashCode(f)
,Integer.hashCode(f)
- Alan bir nesne referansı ise ve sınıfın
equals
metodu bu alanı karşılaştırırken özyineli olarak referans üzerindenequals
metodunu çağırıyorsa, siz de referans nesneninhashCode
metodunu çağırın. Eğer referans null ise 0 değerini döndürün. - 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.
- Eğer anlamlı alan bir ilkel tür ise,
- Yukarıda hesaplanan
c
hash kodunu, aşağıdaki formülü kullanarakresult
değişkenine ekleyinresult = 31 * result + c;
- Bu alan için değeri
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.
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.
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.
[…] istemiş (Madde 10) ve hatta hashCode‘u da geçersiz kılması gerektiğini unutmamış (Madde 11). Ancak, equals metodunu geçersiz kılmaya çalışan programcı yanlışlıkla aşırı yükleme […]