सवाल मैं सी # में बाइट सरणी से हैशकोड कैसे उत्पन्न करूं?


मान लें कि मेरे पास एक ऑब्जेक्ट है जो बाइट सरणी संग्रहीत करता है और मैं इसके लिए हैशकोड को कुशलता से उत्पन्न करने में सक्षम होना चाहता हूं। मैंने अतीत में क्रिप्टोग्राफ़िक हैश फ़ंक्शंस का उपयोग किया है क्योंकि उन्हें कार्यान्वित करना आसान है, लेकिन वे क्रिप्टोग्राफ़िक रूप से चलने के बजाय बहुत अधिक काम कर रहे हैं, और मुझे इसकी परवाह नहीं है (मैं बस इसका उपयोग कर रहा हूं एक हैशटेबल में एक कुंजी के रूप में हैशकोड)।

यहां मेरे पास आज है:

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);
    }
}

कोई विचार?


डीपी: आप सही हैं कि मुझे बराबर में एक चेक याद आया, मैंने इसे अपडेट किया है। बाइट सरणी से मौजूदा हैशकोड का उपयोग संदर्भ समानता (या कम से कम वही अवधारणा हैशकोड में अनुवादित) के परिणामस्वरूप होगा। उदाहरण के लिए:

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

उस कोड के साथ, दो बाइट सरणी के भीतर उनके समान मूल्य होने के बावजूद, वे स्मृति के विभिन्न हिस्सों का जिक्र कर रहे हैं और परिणामस्वरूप (संभवतः) विभिन्न हैश कोड होंगे। मुझे समान सामग्री के साथ दो बाइट एरे के लिए हैश कोड की आवश्यकता है।


44
2017-08-19 14:55


मूल




जवाब:


किसी ऑब्जेक्ट का हैश कोड अद्वितीय होने की आवश्यकता नहीं है।

जांच नियम है:

  • हैश कोड बराबर हैं? फिर पूर्ण (धीमी) को कॉल करें Equals तरीका।
  • क्या हैश कोड बराबर नहीं हैं? फिर दो आइटम निश्चित रूप से बराबर नहीं हैं।

आप चाहते हैं कि एक है GetHashCode एल्गोरिदम जो आपके संग्रह को मोटे तौर पर समूहों में विभाजित करता है - इसे कुंजी के रूप में नहीं बनाना चाहिए HashTable या Dictionary<> पुनर्प्राप्ति को अनुकूलित करने के लिए हैश का उपयोग करने की आवश्यकता होगी।

आप डेटा की कितनी देर तक उम्मीद करते हैं? कितना यादृच्छिक है? यदि लंबाई काफी भिन्न होती है (फ़ाइलों के लिए कहें) तो बस लंबाई वापस करें। यदि लम्बाई बाइट्स के सबसेट पर समान दिखने की संभावना है जो भिन्न होता है।

GetHashCode से बहुत तेज होना चाहिए Equals, लेकिन अद्वितीय होने की जरूरत नहीं है।

दो समान चीजें कभी नहीं होना चाहिए अलग हैश कोड हैं। दो अलग-अलग वस्तुएं नहीं चाहिए एक ही हैश कोड है, लेकिन कुछ टकराव की उम्मीद की जा रही है (आखिरकार, 32 बिट पूर्णांक से अधिक क्रमिकताएं हैं)।


58
2017-08-19 15:17



+1 वह सबसे स्पष्ट स्पष्टीकरणों में से एक था जिसे मैंने कभी सुना है कि क्यों बराबर ओवरराइड करना फायदेमंद है तथा GetHashcode। - Andrew Hare


एक हैशटेबल के लिए क्रिप्टोग्राफिक हैंश का उपयोग न करें, यह हास्यास्पद / ओवरकिल है।

यहाँ जाओ ... सी # में संशोधित एफएनवी हैश

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



आपने धमाल मचाया! यह अद्वितीय फ़ाइल नामों के लिए अच्छी तरह से काम करता प्रतीत होता है :) - mpen
यह बहुत ही अद्वितीय हैश का उत्पादन करेगा, लेकिन वास्तव में इसके लिए अच्छा काम नहीं करेगा GetHashCode। विचार यह है कि हैश संग्रह को दो जांचने की त्वरित विधि रखने की अनुमति देता है byte[] धीमी गति से उपयोग करने से पहले मैच Equals। इस कार्यान्वयन में आप पूरे सरणी को लूप कर रहे हैं, इसलिए बहुत बड़े सरणी के लिए समानता जांच बहुत तेज हो सकती है। यह एक सामान्य उद्देश्य हैश की गणना करने का एक अच्छा तरीका है, लेकिन कैसे नेट वास्तव में उपयोग करता है GetHashCode यह वास्तव में संग्रह को धीमा कर सकता है। - Keith
@tigrou - मैं यह नहीं कह रहा हूं कि यह एक उपयोगी हैश तंत्र नहीं है, लेकिन आपको इसका उपयोग नहीं करना चाहिए GetHashCode कार्यान्वयन क्योंकि .NET संग्रह संग्रह सभी मानते हैं GetHashCode तीव्रता के कई आदेश तेजी से होंगे Equals। वास्तव में अगर GetHashCode चेक पास करें वे कॉल करने के लिए आगे बढ़ेंगे Equals क्योंकि टकराव की कुछ मात्रा की उम्मीद है। यदि दोनों विधियां पूरे संग्रह को लूप करती हैं तो आपको बहुत धीमी गति मिलती है HashTable या Dictionary। - Keith
@ किथ - आप यहाँ गलत हैं। मुख्य बिंदु यह है कि GetHashCode () को केवल एक बार बुलाया जाना चाहिए, जबकि समानता () को प्रत्येक तुलना के लिए बुलाया जाना चाहिए। तो हैश गणना के बराबर बराबर समय के लिए यह ठीक है। वास्तव में, अंतर्निहित .NET स्ट्रिंग हैशिंग बस यही करता है। - kaalus
@ किथ: कालस सही है। एक अच्छे हैश कोड में पूरे ऑब्जेक्ट से जानकारी शामिल होनी चाहिए जिसमें सभी संपत्ति और फ़ील्ड मान शामिल हैं। प्रति कॉल इस जानकारी को स्कैन करने से बचने का कोई तरीका नहीं है, जब तक कि प्रश्न में वस्तु अपरिवर्तनीय न हो और सृजन पर हैश कोड कैश करें। - Frank Hileman


JetBrains सॉफ़्टवेयर द्वारा उत्पन्न कोड से उधार लेते हुए, मैंने इस फ़ंक्शन पर बस लिया है:

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

बाइट्स को केवल XOring के साथ समस्या यह है कि लौटा मूल्य के 3/4 (3 बाइट्स) में केवल 2 संभावित मान हैं (सभी या सभी बंद)। यह थोड़ा और आसपास बिट्स फैलता है।

बराबर में ब्रेकपॉइंट सेट करना एक अच्छा सुझाव था। एक शब्दकोश में मेरे डेटा की लगभग 200,000 प्रविष्टियां जोड़ना, लगभग 10 बराबर कॉल (या 1 / 20,000) देखता है।


11
2018-01-08 17:37



के लिये IList<byte> निश्चित रूप से इंडेक्सिंग के आधार पर लूप का उपयोग करें foreach। इसके लिए कोई फर्क नहीं पड़ता है byte[] जबसे foreach में परिवर्तित किया जाएगा for आंतरिक रूप से। - nawfal


क्या आपने इसकी तुलना की है SHA1CryptoServiceProvider.ComputeHash तरीका? यह एक बाइट सरणी लेता है और एक SHA1 हैश देता है, और मेरा मानना ​​है कि यह बहुत अच्छी तरह अनुकूलित है। मैंने इसे एक में इस्तेमाल किया पहचानकर्ता हैंडलर जो लोड के तहत बहुत अच्छी तरह से प्रदर्शन किया।


3
2017-08-19 15:53



एसएचए 1 एमडी 5 की तुलना में धीमी है। यदि आप सुरक्षा के बारे में चिंतित नहीं हैं तो MD5 का उपयोग करें। - Jonathan C Dickinson
धन्यवाद जॉन .. SHA1CryptoServiceProvider.ComputeHash विधि मेरे लिए काम किया .. !! - Deepak


मुझे दिलचस्प परिणाम मिले:

मेरे पास कक्षा है:

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();          
    }
}

फिर मैंने यह जांचने के लिए माईहाश के प्रकार के साथ एक शब्दकोश बनाया, ताकि मैं कितनी तेज़ी से सम्मिलित कर सकूं और मैं यह भी जान सकूं कि कितने टकराव हैं। मैंने निम्नलिखित किया

        // 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();

प्रत्येक बार जब मैं शब्दकोश में एक नया आइटम डालता हूं तो शब्दकोश उस ऑब्जेक्ट के हैश की गणना करेगा। तो आप विधि में यहां पाए गए कई उत्तरों को रखकर बता सकते हैं कि कौन सी विधि सबसे अधिक कुशल है public override int GetHashCode() विधि जो सबसे तेज़ थी और कम से कम टकराव की संख्या थी:

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

निष्पादित करने में 2 सेकंड लग गए। प्रक्रिया

    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;
        }
    }

कोई टक्कर नहीं थी लेकिन इसे निष्पादित करने में 7 सेकंड लग गए!


3
2018-03-12 20:40



क्या आप अपने हैश एल्गोरिदम को समझा सकते हैं - nicolay.anykienko


बाइट सरणी फ़ील्ड से मौजूदा हैशकोड का उपयोग करना पर्याप्त नहीं है? यह भी ध्यान रखें कि बराबर विधि में आपको जांच करनी चाहिए कि तुलना करने से पहले सरणी एक ही आकार के हैं।


1
2017-08-19 15:19





एक अच्छा हैश उत्पन्न करना आसान होने से कहा जाता है। याद रखें, आप मूल रूप से सूचना के एम बिट्स के साथ डेटा के एन बाइट्स का प्रतिनिधित्व कर रहे हैं। आपका डेटा सेट जितना बड़ा होगा और छोटा एम होगा, उतना अधिक संभावना है कि आपको टकराव मिलेगा ... डेटा के दो टुकड़े एक ही हैश को हल कर रहे हैं।

मैंने कभी सीखा सबसे आसान हैश बस सभी बाइट्स को एक साथ जोड़ रहा था। यह सबसे जटिल हैश एल्गोरिदम की तुलना में आसान, तेज़ है और छोटे डेटा सेट के लिए आधा रास्ते सभ्य सामान्य उद्देश्य हैश एल्गोरिदम है। यह वास्तव में हैश एल्गोरिदम का बबल सॉर्ट है। चूंकि सरल कार्यान्वयन आपको 8 बिट्स के साथ छोड़ देगा, यह केवल 256 हैश ... बहुत गर्म नहीं है। आप अलग-अलग बाइट्स के बजाय एक्सओआर चंक्स कर सकते हैं, लेकिन फिर एल्गोरिदम अधिक जटिल हो जाता है।

तो निश्चित रूप से, क्रिप्टोग्राफिक एल्गोरिदम शायद कुछ सामान कर रहे हैं जिनकी आपको आवश्यकता नहीं है ... लेकिन वे सामान्य उद्देश्य हैश गुणवत्ता में भी एक बड़ा कदम उठा रहे हैं। आपके द्वारा उपयोग किए जा रहे एमडी 5 हैश में 128 बिट्स हैं, अरबों और अरबों संभावित हैंश के साथ। एकमात्र तरीका आपको कुछ बेहतर करने की संभावना है, उस डेटा के कुछ प्रतिनिधि नमूनों को लेना जो आप अपने आवेदन के माध्यम से जा रहे हैं और यह देखने के लिए कि आप कितने टकराव प्राप्त करते हैं, इस पर विभिन्न एल्गोरिदम आज़माएं।

तो जब तक मुझे डिब्बाबंद हैश एल्गोरिदम (प्रदर्शन, शायद?) का उपयोग न करने का कोई कारण दिखाई देता है, तो मुझे आपको जो मिला है उसके साथ चिपकने की सलाह देनी होगी।


1
2017-08-19 15:31





चाहे आप एक परिपूर्ण हैशफंक्शन (प्रत्येक ऑब्जेक्ट के बराबर मूल्यांकन करने के लिए अलग-अलग मूल्य) चाहते हैं या सिर्फ एक अच्छा अच्छा हमेशा एक प्रदर्शन ट्रेडऑफ होता है, आमतौर पर एक अच्छा हैशफंक्शन की गणना करने में समय लगता है और यदि आपका डेटासेट छोटा है तो आप बेहतर हैं एक तेज समारोह। सबसे महत्वपूर्ण (आपकी दूसरी पोस्ट पॉइंट्स के रूप में) शुद्धता है, और यह सुनिश्चित करने के लिए कि आपको सरणी की लंबाई वापस करने की आवश्यकता है। आपके डेटासेट के आधार पर जो ठीक भी हो सकता है। यदि यह नहीं है (कहें कि आपके सभी सरणी समान रूप से लंबे हैं) तो आप पहले और आखिरी मूल्य को देखने और अपने मूल्यों को एक्सओर करने जैसे सस्ते कुछ के साथ जा सकते हैं और फिर अपने डेटा के लिए उपयुक्त दिखने के साथ और अधिक जटिलता जोड़ सकते हैं।

यह देखने का एक त्वरित तरीका है कि आपका डेटा आपके डेटा पर कैसे किया जाता है, हैशटेबल में सभी डेटा जोड़ना और बराबर फ़ंक्शन कहने की संख्या को गिनना है, यदि यह अक्सर होता है तो आपके पास फ़ंक्शन पर अधिक काम होता है। यदि आप ऐसा करते हैं तो ध्यान रखें कि जब आप प्रारंभ करते हैं तो हैशटेबल के आकार को आपके डेटासेट से बड़ा सेट करने की आवश्यकता है, अन्यथा आप डेटा को फिर से शुरू करने जा रहे हैं जो रीइन्सर्ट ट्रिगर करेगा और अधिक समान मूल्यांकन (हालांकि संभवतः अधिक यथार्थवादी है?)

कुछ ऑब्जेक्ट्स के लिए (यह नहीं) एक त्वरित हैशकोड ToString () द्वारा उत्पन्न किया जा सकता है। GetHashCode (), निश्चित रूप से इष्टतम नहीं है, लेकिन उपयोगी है क्योंकि लोग ऑब्जेक्ट की पहचान को ToString () से कुछ वापस लौटते हैं और यह बिल्कुल ठीक है GetHashcode क्या देख रहा है

ट्रिविया: मैंने कभी देखा है कि सबसे खराब प्रदर्शन तब था जब गलती से कोई गेटहैशकोड से निरंतर लौटा, हालांकि डीबगर के साथ स्पॉट करना आसान था, खासकर अगर आप अपने हैशटेबल में बहुत सारे लुकअप करते हैं


1
2017-09-09 22:35





यदि आप प्रदर्शन की तलाश में हैं, तो मैंने कुछ हैश कुंजी का परीक्षण किया है, और मेरा सुझाव है बॉब जेनकिन के हैश फ़ंक्शन। यह पागल तेज़ दोनों है क्रिप्टोग्राफिक के रूप में गणना करने और कुछ टकराव के रूप में देने के लिए हैश आप अब तक इस्तेमाल किया।

मुझे सी # बिल्कुल पता नहीं है, और मुझे नहीं पता कि यह सी से लिंक कर सकता है, लेकिन यहाँ है सी में इसका कार्यान्वयन


1
2017-08-19 15:16