Soru C # içinde bir bayt dizisinden bir hashcode nasıl oluştururum?


Bayt dizisini saklayan bir nesneyim olduğunu ve bunun için bir karma kodun verimli bir şekilde üretilmesini istediğimi varsayalım. Geçmişte bunun için kriptografik karma işlevlerini kullandım çünkü uygulamak çok kolay, ama onlar kriptografik olarak yolda olması gerektiğinden çok daha fazla iş yapıyorlar ve bunu umursamıyorum (sadece kullanıyorum hashcode bir hashtable içine anahtar olarak).

İşte bugün sahip olduğum şey:

struct SomeData : IEquatable<SomeData>
{
    private readonly byte[] data;
    public SomeData(byte[] data)
    {
        if (null == data || data.Length <= 0)
        {
            throw new ArgumentException("data");
        }
        this.data = new byte[data.Length];
        Array.Copy(data, this.data, data.Length);
    }

    public override bool Equals(object obj)
    {
        return obj is SomeData && Equals((SomeData)obj);
    }

    public bool Equals(SomeData other)
    {
        if (other.data.Length != data.Length)
        {
            return false;
        }
        for (int i = 0; i < data.Length; ++i)
        {
            if (data[i] != other.data[i])
            {
                return false;
            }
        }
        return true;
    }
    public override int GetHashCode()
    {
        return BitConverter.ToInt32(new MD5CryptoServiceProvider().ComputeHash(data), 0);
    }
}

Düşüncesi olan var mı?


dp: Haklı olduğum için haklısın, eşittir, güncelledim. Var olan kodun bayt dizisinden kullanılması, referans eşitliği ile sonuçlanacaktır (veya en azından aynı kavramın kodeklere çevrilmesi). Örneğin:

byte[] b1 = new byte[] { 1 };
byte[] b2 = new byte[] { 1 };
int h1 = b1.GetHashCode();
int h2 = b2.GetHashCode();

Bu kodla, içlerinde aynı değerlere sahip iki bayt dizisine rağmen, belleğin farklı kısımlarına atıfta bulunurlar ve (muhtemelen) farklı karma kodları ile sonuçlanırlar. Aynı içeriğe sahip iki bayt dizisi için karma kodlara ihtiyacım var.


44
2017-08-19 14:55


Menşei




Cevaplar:


Bir nesnenin karma kodunun benzersiz olması gerekmez.

Kontrol kuralı:

  • Karma kodlar eşit mi? Sonra tam (yavaş) arayın Equals yöntem.
  • Karma kodlar eşit değil mi? Sonra iki öğe kesinlikle eşit değil.

Tek istediğin bir GetHashCode Koleksiyonunuzu kabaca gruplara bölen algoritma - anahtarı HashTable veya Dictionary<> alımı optimize etmek için karma kullanmanız gerekecektir.

Verilerin ne kadar olmasını bekliyorsunuz? Ne kadar rasgele? Uzunluklar büyük ölçüde değişirse (dosyalar için söyleyin), o zaman sadece uzunluğunu döndürün. Uzunlukların, değişmekte olan baytların bir alt kümesine benzer olması muhtemeldir.

GetHashCode daha hızlı olmalı Equalsama benzersiz olması gerekmiyor.

İki özdeş şey asla farklı karma kodları var. İki farklı nesne yapmamalı aynı karma kodu var, ama bazı çarpışmalar beklenmelidir (sonuçta, olası 32 bit tam sayıdan daha fazla permütasyon vardır).


58
2017-08-19 15:17



+1 Eşitliği geçersiz kılmanın neden faydalı olduğunu duyduğum en açık açıklamalardan biriydi ve GetHashCode. - Andrew Hare


Bir hashtable için şifreleme karma kullanmayın, bu saçma / overkill.

İşte gidip ... C # Modifiye FNV Hash

http://bretm.home.comcast.net/hash/6.html

    public static int ComputeHash(params byte[] data)
    {
        unchecked
        {
            const int p = 16777619;
            int hash = (int)2166136261;

            for (int i = 0; i < data.Length; i++)
                hash = (hash ^ data[i]) * p;

            hash += hash << 13;
            hash ^= hash >> 7;
            hash += hash << 3;
            hash ^= hash >> 17;
            hash += hash << 5;
            return hash;
        }
    }

42
2018-01-22 04:55



Harikasın! Bu benzersiz dosya isimleri için iyi çalışıyor gibi görünüyor :) - mpen
Bu oldukça benzersiz hashlar üretecek, ancak gerçekten işe yaramayacak GetHashCode. Buradaki fikir, karmanın, koleksiyonun hızlı bir şekilde kontrol edilip edilmeyeceğini kontrol etmesine izin vermesidir. byte[] yavaş kullanmadan önce eşleştir Equals. Bu uygulamada dizinin tamamını birleştiriyorsunuz, dolayısıyla çok büyük diziler için eşitlik kontrolü çok daha hızlı olabilirdi. Bu, genel amaçlı bir karmayı hesaplamanın iyi bir yoludur, ancak .Net aslında nasıl kullanılır? GetHashCode Bu aslında koleksiyonları yavaşlatabilir. - Keith
@tigrou - Bunun kullanışlı bir karma mekanizma olmadığını söylemiyorum, ancak bunu bir GetHashCode Uygulama çünkü .Net hashed koleksiyonları tüm varsayalım GetHashCode büyüklük birkaç emir daha hızlı olacak Equals. Aslında eğer GetHashCode onayladılar, aramaya devam edecekler Equalsçünkü bazı çarpışmalar bekleniyor. Her iki yöntem de koleksiyonun tamamını kaplarsa çok yavaş olur HashTable veya Dictionary. - Keith
@Keith - burada yanılıyorsun. Anahtar nokta, GetHashCode () 'ın sadece bir kez çağrılması gerektiğidir, Equals () ise her karşılaştırma için çağrılmalıdır. Bu yüzden, karma hesaplamanın eşittirden daha uzun çalışma süresi olması gayet iyi. Aslında, yerleşik .NET dizgisi karmaşası sadece bunu yapar. - kaalus
@Keith: kaalus doğrudur. İyi bir karma kod, tüm özellik ve alan değerleri dahil olmak üzere, hashlanacak tüm nesneden bilgi içermelidir. Söz konusu nesne değişmez ve yaratılıştaki karma kodu önbelleğe almadıkça, bu bilgiyi her aramada taramaktan kaçınmanın bir yolu yoktur. - Frank Hileman


JetBrains yazılımının ürettiği koddan borç alarak, bu işleve yerleştim:

    public override int GetHashCode()
    {
        unchecked
        {
            var result = 0;
            foreach (byte b in _key)
                result = (result*31) ^ b;
            return result;
        }
    }

Sadece XOring byte ile sorun, döndürülen değerin 3/4 (3 byte) sadece 2 olası değere sahip olmasıdır (hepsi açık veya kapalı). Bu, bitleri biraz daha fazla yayıyor.

Eşitlikte bir kesme noktası kurmak iyi bir öneriydi. Verilerimin bir Sözlüke yaklaşık 200.000 girişi eklendiğinde, yaklaşık 10 Eşit çağrı (veya 1 / 20.000) görür.


11
2018-01-08 17:37



için IList<byte> kesinlikle indekslemeye dayalı bir for döngüsü kullanın foreach. Onun için bir fark olmayabilir byte[] dan beri foreach dönüştürülecek for içten. - nawfal


İle karşılaştırdınız mı SHA1CryptoServiceProvider.ComputeHash yöntem? Bir bayt dizisi alır ve bir SHA1 hash'ını döndürür ve oldukça iyi optimize edilmiş olduğuna inanıyorum. Onu bir Identicon İşleyici yük altında oldukça iyi performans gösterdi.


3
2017-08-19 15:53



SHA1, MD5'ten daha yavaştır. Güvenlik konusunda endişelenmiyorsanız, MD5'i kullanın. - Jonathan C Dickinson
Teşekkürler Jon .. SHA1CryptoServiceProvider.ComputeHash yöntemi benim için çalıştı .. !! - Deepak


İlginç sonuçlar buldum:

Dersim var:

public class MyHash : IEquatable<MyHash>
{        
    public byte[] Val { get; private set; }

    public MyHash(byte[] val)
    {
        Val = val;
    }

    /// <summary>
    /// Test if this Class is equal to another class
    /// </summary>
    /// <param name="other"></param>
    /// <returns></returns>
    public bool Equals(MyHash other)
    {
        if (other.Val.Length == this.Val.Length)
        {
            for (var i = 0; i < this.Val.Length; i++)
            {
                if (other.Val[i] != this.Val[i])
                {
                    return false;
                }
            }

            return true;
        }
        else
        {
            return false;
        }            
    }

    public override int GetHashCode()
    {            
        var str = Convert.ToBase64String(Val);
        return str.GetHashCode();          
    }
}

Sonra ne kadar hızlı sokabileceğimi test etmek için MyHash türünde bir sözlük oluşturdum ve kaç çarpışma olduğunu da biliyorum. Ben yaptım

        // dictionary we use to check for collisions
        Dictionary<MyHash, bool> checkForDuplicatesDic = new Dictionary<MyHash, bool>();

        // used to generate random arrays
        Random rand = new Random();



        var now = DateTime.Now;

        for (var j = 0; j < 100; j++)
        {
            for (var i = 0; i < 5000; i++)
            {
                // create new array and populate it with random bytes
                byte[] randBytes = new byte[byte.MaxValue];
                rand.NextBytes(randBytes);

                MyHash h = new MyHash(randBytes);

                if (checkForDuplicatesDic.ContainsKey(h))
                {
                    Console.WriteLine("Duplicate");
                }
                else
                {
                    checkForDuplicatesDic[h] = true;
                }
            }
            Console.WriteLine(j);
            checkForDuplicatesDic.Clear(); // clear dictionary every 5000 iterations
        }

        var elapsed = DateTime.Now - now;

        Console.Read();

Sözlüğe yeni bir öğe eklediğimde, sözlük o nesnenin karmasını hesaplayacaktır. Bu nedenle, burada yöntemde bulunan çeşitli cevapları yerleştirerek hangi yöntemin en verimli olduğunu anlayabilirsiniz. public override int GetHashCode() En hızlı ve en az çarpışma sayısına sahip olan yöntem şuydu:

    public override int GetHashCode()
    {            
        var str = Convert.ToBase64String(Val);
        return str.GetHashCode();          
    }

Bu yürütmek için 2 saniye sürdü. Yöntem

    public override int GetHashCode()
    {
        // 7.1 seconds
        unchecked
        {
            const int p = 16777619;
            int hash = (int)2166136261;

            for (int i = 0; i < Val.Length; i++)
                hash = (hash ^ Val[i]) * p;

            hash += hash << 13;
            hash ^= hash >> 7;
            hash += hash << 3;
            hash ^= hash >> 17;
            hash += hash << 5;
            return hash;
        }
    }

hiçbir çarpışma yoktu ama yürütmek için 7 saniye sürdü!


3
2018-03-12 20:40



Karma algoritmanızı açıklar mısınız - nicolay.anykienko


Bayt dizisi alanından var olan karma kodu yeterince iyi değil mi? Ayrıca, Eşittir yönteminde, karşılaştırma yapmadan önce dizilerin aynı boyutta olduğunu kontrol etmeniz gerektiğini unutmayın.


1
2017-08-19 15:19





İyi bir karma üretme, yapılması gerekenden daha kolaydır. Unutmayın, temel olarak, veri biti ile veri n baytlarını temsil ediyorsunuz. Veri kümeniz ne kadar büyükse ve daha küçük olan m ise, bir çarpışma elde edeceğinize göre daha büyük bir olasılıkla ... iki parça veri aynı karmaya dönüşüyor.

Şimdiye kadar öğrendiğim en basit karmaşa, tüm baytları bir araya getirmek oldu. En karmaşık karma algoritmalardan ve küçük veri kümeleri için yarı yolda uygun genel amaçlı karma algoritmadan daha kolay, daha hızlıdır. Bu gerçekten karma algoritmaların Bubble Sıralamadır. Basit uygulama sizi 8 bitten çıkaracağından, bu sadece 256 karma değil ... o kadar da sıcak değil. XOR, individal bayt yerine parçalayabilir, ancak algoritma çok daha karmaşık hale gelir.

Yani, kriptografik algoritmalar belki de ihtiyacınız olmayan bazı şeyler yapıyor olabilir ... ama aynı zamanda genel amaçlı karma kalitesinde de büyük bir adım. Kullandığınız MD5 hash, 128 bit, milyarlarca ve milyarlarca olası karma var. Daha iyi bir şey elde etmenin tek yolu, uygulamanızdan geçmeyi beklediğiniz verilerin temsili örneklerini almak ve kaç çarpışma elde edeceğinizi görmek için çeşitli algoritmaları denemenizdir.

Yani bir konserve algoritması kullanmamamın bir nedenini görene kadar (performans, belki?), Sana sahip olduklarına bağlı kalmanızı tavsiye etmek zorundayım.


1
2017-08-19 15:31