SORU
4 Kasım 2008, Salı


Geçersiz kılınmış bir Sistem için en iyi algoritma nedir.Nesne.GetHashCode?

.System.Object.GetHashCode NET yöntem boyunca pek çok yerde kullanılır .NET temel sınıf kütüphaneleri. Özellikle hızlı bir koleksiyondaki öğeleri bulma ve eşitlik belirlemek için zaman. Performans aşağılamak istemiyorum bu yüzden standart bir algoritma özel derslerim için GetHashCode geçersiz uygulama konusunda/ iyi uygulama var mı?

CEVAP
4 Kasım 2008, Salı


Ben genelde uygulama Josh Bloch. verilen gibi bir şey ile gitmekmuhteşemEffective Java. Hızlı ve çarpışmalar neden olma ihtimali olan güzel bir karma oluşturur. İki farklı asal sayılar, örneğin 17 ve 23, ve yapın: seçin

public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = 17;
        // Suitable nullity checks etc, of course :)
        hash = hash * 23   field1.GetHashCode();
        hash = hash * 23   field2.GetHashCode();
        hash = hash * 23   field3.GetHashCode();
        return hash;
    }
}

EDİT: yorumlarda da belirtildiği Gibi, daha iyi yerine çoğalmaya büyük bir prime almak için bulabilirsiniz. Görünüşe göre 486187739... ve az sayıda gördüğüm en örnekler, asal sayıları kullanma eğiliminde olsa da, olmayan asal sayılar sık sık kullanıldığı en azından benzer bir algoritma vardır. Örneğin pek FNV örnek daha sonra, görünüşe göre iyi iş hangi numaraları kullandım ama başlangıç değeri bir asal değil. (Çarpma sabitBaşbakan olsa. Oldukça ne kadar önemli olduğunu bilmiyorum.)

Bu iki ana nedenden dolayı 6 **ing hashcodes yaygın bir uygulama daha iyidir. ** 7 iki alan: bir tür olduğunu varsayalım

XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y

Bu arada, önceki algoritma bir anda C tarafından kullanılır# anonim türleri için derleyici.

EDİT: This page Oldukça birkaç seçenek sunar. "Yeterli" ve inanılmaz derecede kolay ve doğru hatırlamak için. iyi bir çoğu için yukarıda olduğunu düşünüyorum FNV alternatif benzer şekilde basit, ama farklı sabitleri kullanır ve yerine birleştirme işlemi XOR EKLEYİN. Görünüyorbir şeyaşağıdaki kod gibi, ama normal FNV algoritma bu 32-bit hash değeri başına bayt başına, yerine bir döngü gerçekleştirmek için değiştirilmesi gerekir bu yüzden tek tek bayt üzerinde çalışır. FNV de burada kullanıyoruz her zaman alan değerleri için aynı sayıda ise veri değişken uzunlukları için tasarlanmıştır. Bu cevap hakkında yorum kodu burada gerçekten de çalışmıyor (örnek vaka test) ayrıca yaklaşım olarak yukarıda öneririz.

// Note: Not quite FNV!
public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = (int) 2166136261;
        // Suitable nullity checks etc, of course :)
        hash = hash * 16777619 ^ field1.GetHashCode();
        hash = hash * 16777619 ^ field2.GetHashCode();
        hash = hash * 16777619 ^ field3.GetHashCode();
        return hash;
    }
}

EDİT: Not olan bir şey farkında olan ideal olmalıdır önlemek sizin eşitlik duyarlı (ve böylece hashcode duyarlı) devlet değiştirdikten sonra ekleme için bir koleksiyon bağlı hash kodu.

documentation başına:

Değişmez başvuru türleri için GetHashCode kılabilirsiniz. Değişken başvuru türleri için genel olarak, GetHashCode sadece geçersiz kılmak gerekir:

  • Değiştirilebilir alanlardan karma kodu Hesaplaması; ya
  • Değiştirilebilir bir nesnenin hash kodunu nesnenin hash kodunu kullanan bir koleksiyon yer alıyor olsa değişmez emin olabilirsiniz.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • laptopmag

    laptopmag

    25 Ocak 2008
  • PaulGBelliveau

    PaulGBellive

    5 Mart 2009
  • RiceBunny

    RiceBunny

    16 ŞUBAT 2006