Neden hashcode \ equals yeniden yazılsın? Genç programcılar röportajlarda nadiren net konuşurlar
Java genç geliştirme ile röportaj yaparken sık sık şunu sordum: Hashcode yöntemini hiç yeniden yazdınız mı? Birçok aday doğrudan hiç yazmadıklarını söyledi. Belki daha önce yazmadım diye düşündüm, bu yüzden başka bir soruyla teyit edeceğim: Anahtar kısımda HashMap'i kullandığınızda, özel nesneleri kaçırdınız mı? Bu sırada, aday bırakmasını söyledi, bu nedenle iki sorunun cevabı çelişkili idi.
Son zamanlarda sorulan bu sorunun cevabı genellikle pek iyi değil, bu yüzden bu yazıda hash tablosuyla başlayıp HashMap'in veri depolama kurallarını anlatacağım, böylece herkes doğal olarak yukarıdaki sorunun cevabını bilecek.
Bir, HashMap nesnesinin verimliliğini anlamak için Hash algoritması aracılığıyla
Veri yapısındaki bir bilgi noktasını gözden geçirelim: n uzunluğunda (10000 varsayılarak) doğrusal bir listede (ArrayList varsayılarak), depolanmış sırasız sayılar vardır; belirli bir sayı bulursak, Arama baştan sona dolanarak gerçekleştirilir Ortalama arama sayısı n bölü 2'dir (burada 5000).
Hash tablosuna tekrar bakalım (Buradaki Hash tablosu tamamen bir veri yapısı kavramıdır ve Java ile hiçbir ilgisi yoktur). Ortalama arama sayısı 1'e yakındır ve maliyeti oldukça düşüktür Anahtar, Hash tablosunda depolanan verilerin ve depolama konumunun Hash fonksiyonu ile ilişkilendirilmiş olmasıdır.
Bir Hash fonksiyonunun x * x% 5 olduğunu varsayıyoruz. Elbette, gerçek durumda bu kadar basit bir Hash fonksiyonunu kullanmak imkansızdır.Burada sadece açıklama kolaylığı için buradayız ve Hash tablosu 11 uzunluğunda doğrusal bir tablodur. İçine 6 koymak istersek, o zaman önce Hash fonksiyonu ile 6'yı hesaplayacağız ve sonuç 1 olacak, bu yüzden indeks numarasının 1 olduğu konuma 6 koyacağız. Benzer şekilde 7 sayısını Hash fonksiyonu hesaplamasından sonra koymak istersek 7'nin sonucu 4 olur, o zaman indeksin 4 olduğu konuma getirilir. Bu etki aşağıdaki şekilde gösterilmektedir.
Bunun faydaları çok açık. Örneğin, element 6'yı ondan bulmak istersek, önce 6'nın indeks konumunu Hash fonksiyonu aracılığıyla hesaplayabilir ve sonra doğrudan indeks 1'den bulabiliriz.
Ancak "Hash değeri çatışması" sorunuyla karşılaşacağız. Örneğin, Hash fonksiyonu hesaplandıktan sonra 7 ve 8 aynı Hash değerine sahip olacaktır.Bunun için Java HashMap nesnesi "zincir adres metodu" çözümünü kullanır. Sonuçlar aşağıda gösterildiği gibidir.
Spesifik yöntem, karma değeri i olan tüm nesneler için eşanlamlı bağlantılı bir liste oluşturmaktır. Diyelim ki pozisyon 4 zaten 8'i yerleştirdiğimizde işgal edilmiş durumda, o zaman yeni bir bağlantılı liste düğümü oluşturup 8 koyacağız. Benzer şekilde, 8'i arıyorsak, o zaman 4 numaralı indeksin 8 olmadığını buluruz, sonra sırayla bağlantılı liste boyunca bakarız.
Karma değer çatışmaları sorununu hala tamamen önleyemesek de, karma işlevi makul bir şekilde tasarlanmıştır ve eşanlamlı bağlantılı listenin uzunluğunun makul bir aralık içinde kontrol edilmesini yine de sağlayabilir. Burada bahsedilen teorik bilgi amaçsız değildir. HashCode yöntemini daha sonra yeniden yazmanın önemini açıkça anlayabilirsiniz.
2. Eşittir ve hashCode yöntemlerini neden yeniden yazmalısınız?
Özel bir sınıfta saklamak için HashMap kullandığımızda, bu özel sınıfın equals ve hashCode yöntemlerini geçersiz kılmazsak, sonuç beklediğimizden farklı olacaktır. Bu örneğe WithoutHashCode.java bakalım.
2. ila 18. satırlarda bir Key sınıfı tanımlıyoruz; 3. satırda benzersiz bir öznitelik kimliği tanımlıyoruz. Şu anda, ilk olarak 9. satırdaki eşittir yöntemini ve 16. satırdaki hashCode yöntemini yorumluyoruz.
java.util.HashMap'i içe aktarın;
class Key {
özel Tamsayı kimliği;
public Tamsayı getId ()
{
dönüş kimliği;
}
genel Anahtar (Tamsayı kimliği)
{
this.id = id;
}
// Eşittir ve hashCode yöntemlerini bilinçli olarak yorumlayın
// public boolean equals (Object o) {
// if (o == null ||! (o anahtar örneği))
// {yanlış dönüş;}
// Başka
// {return this.getId (). equals (((Key) o) .getId ());}
//}
// genel int hashCode ()
// {return id.hashCode ();}
}
public class WithoutHashCode {
public static void main (String args) {
Anahtar k1 = yeni Anahtar (1);
Anahtar k2 = yeni Anahtar (1);
HashMap < Anahtar, Dize > hm = yeni HashMap < Anahtar, Dize > ();
hm.put (k1, "Kimlikli anahtar 1'dir");
System.out.println (hm.get (k2));
}
}
Ana fonksiyonun 22. ve 23. satırlarında, aynı kapıyı açabilen iki özdeş anahtar gibi iki Anahtar nesne tanımlıyoruz, bunların kimliği 1'dir.
24. satırda jenerikler aracılığıyla bir HashMap nesnesi oluşturduk. Anahtar kısmı Anahtar tipi nesneleri depolayabilir ve değer kısmı Dize tipi nesneleri depolayabilir.
25. satırda, k1'i ve bir karakter dizisini hm'ye koymak için put yöntemini kullanıyoruz; 26. satırda, HashMap'ten değeri almak için k2'yi kullanmak istiyoruz; bu, k1'in anahtarını kullanmak istiyormuşuz gibi Kapıyı kilitleyin ve kapıyı açmak için k2'yi kullanın. Bu mantıklı, ancak mevcut sonuçlardan yola çıkarak 26. satırın dönüş sonucu hayal ettiğimiz dize değil, boş.
İki neden var - yeniden yazmak yok. Birincisi, hashCode yönteminin yeniden yazılmaması ve ikincisi, eşittir yönteminin yeniden yazılmamasıdır.
HashMap'e k1 koyduğumuzda, hash değerini hesaplamak için önce Key sınıfının hashCode metodunu çağırıyoruz ve ardından hash değeri ile gösterilen hafıza konumuna k1 koyuyoruz.
Anahtar, Key'de hashCode yöntemini tanımlamamış olmamızdır. Object sınıfının hashCode yöntemi hala burada çağrılır (tüm sınıflar Object alt sınıflarıdır) ve Object sınıfının hashCode yöntemi tarafından döndürülen karma değeri aslında k1 nesnesinin bellek adresidir (1000 olduğu varsayılırsa).
Daha sonra hm.get (k1) 'i çağırırsak, hashCode yöntemini tekrar çağırırız (yine de k11000 adresini döndürürüz) ve sonra elde edilen hash değerine bağlı olarak k1'i hızlıca bulabiliriz.
Ama buradaki kodumuz hm.get (k2). Object sınıfının hashCode metodunu k2'nin hash değerini hesaplamak için çağırdığımızda (çünkü Key'de tanımlanmadı), aslında elde ettiğimiz şey k2'nin hafıza adresidir (2000 olduğunu varsayarsak). K1 ve k2 iki farklı nesne olduğundan, bellek adresleri aynı olmamalıdır, yani hash değerleri farklı olmalıdır, bu yüzden k2'nin hash değerini k1 elde etmek için kullanamayız.
HashCode metodunun 16. ve 17. satırlardaki yorumlarını kaldırdığımızda, bunun id özniteliğinin hashCode değerini döndürdüğünü göreceğiz.Burada, k1 ve k2'nin id hem 1 hem de hash değerleri eşittir.
K1'i kaydetme ve k2'yi getirme eylemlerini düzeltelim. K1 depolandığında, id değerinin hash değerine dayanır, burada 100 olduğunu varsayarak, k1 nesnesini karşılık gelen konuma koyun. K2 alındığında, önce hash değeri hesaplanır (çünkü k2'nin kimliği de 1'dir, bu değer de 100'dür) ve sonra onu bulmak için bu konuma gidin.
Ancak sonuç beklentimizin ötesinde olacak: açıkça 100. pozisyonda k1 var, ancak 26. satırdaki çıktı sonucu hala boş. Bunun nedeni, Key nesnesinin eşittir yönteminin geçersiz kılınmamış olmasıdır.
HashMap, çakışmaları işlemek için zincir adres yöntemini kullanır, yani, 100 konumunda, bağlantılı bir liste biçiminde saklanan birden çok nesne olabilir. HashCode yöntemi tarafından döndürülen karma değeri 100'dür.
K2'nin hashCode'u aracılığıyla pozisyon 100'ü aradığımızda, gerçekten k1 elde edeceğiz. Ancak k1 yalnızca k2 ile aynı hash değerine sahip olabilir, ancak k2'ye eşit olmayabilir (k1 ve k2'nin iki anahtarı aynı kapıyı açamayabilir). Şu anda, ikisinin olup olmadığını belirlemek için Anahtar nesnesinin eşittir yöntemini çağırmanız gerekir. Eşittir.
Key nesnesinde equals yöntemini tanımlamadığımız için, sistemin Object sınıfının equals yöntemini çağırması gerekiyordu. Object'in doğasında bulunan yöntem, iki nesnenin bellek adreslerine göre yargılama yapmak olduğundan, k1 ve k2 eşit olmamalıdır, bu nedenle 26. satırda hm.get (k2) yoluyla hala boş alıyorsunuz.
Bu sorunu çözmek için, eşittir yönteminin açıklamasını 9'dan 14'e kadar satırlarda açmamız gerekir. Bu yöntemde, iki nesne Anahtar tipinde olduğu ve kimlikleri eşit olduğu sürece eşittir.
3. Görüşme sorularının açıklaması
HashMap projelerde sıklıkla kullanıldığından, görüşme sırasında kesinlikle şu soruyu soracağım: hashCode yöntemini hiç yeniden yazdınız mı? HashMap kullanırken hashCode ve equals yöntemlerini geçersiz kıldınız mı? Nasıl yazdın
Sorgulamanın sonuçlarına göre, genç programcıların genellikle bu bilgiye hakim olmadıklarını buldum. Tekrarlamak gerekirse, HashMap'in "anahtar" bölümünde özel bir nesne depolamak istiyorsanız, bu nesnedeki eşittir ve hashCode yöntemlerinizi, Nesnede aynı ada sahip yöntemleri geçersiz kılmak için kullanmanız gerekir.
