एक बिट हैरे

Question

के लिए एक अच्छा हैश कोड (GetHashCode) उत्पन्न करना मुझे बिटटायर के लिए GetHashCode में एक तेज़ हैश कोड जेनरेट करने की आवश्यकता है। मेरे पास एक शब्दकोश है जहां चाबियाँ बिटराइज़ हैं, और सभी बिटरायर एक ही लंबाई के हैं।

क्या किसी को इस परिदृश्य में बिट्स की एक चर संख्या से एक अच्छा हैश उत्पन्न करने के लिए एक तेज़ तरीका पता है?

अद्यतन:

दृष्टिकोण मैं मूल रूप से लिया (गति इस मामले में कैप्सूलीकरण से ज्यादा महत्वपूर्ण है) सीधे प्रतिबिंब के माध्यम से ints के आंतरिक सरणी तक पहुँचने के लिए है, तो उन मूल्यों XOR था। (

public int GetHashCode(BitArray array) 
    { 
     int hash = 0; 
     foreach (int value in array.GetInternalValues()) 
     { 
      hash ^= value; 
     } 
     return hash; 
    } 

हालांकि, दृष्टिकोण मार्क बायर्स ने सुझाव दिया और StackOverflow पर कहीं और देखा थोड़ा बेहतर था 16,570 बराबर है: XOR दृष्टिकोण यानी मेरे 'बराबर' अच्छी तरह से काम करने लगता है जब शब्दकोश में खोज विधि जरूरत से ज्यादा नहीं बुलाया जाता है मेरे परीक्षण डेटा के लिए एक्सओआर के लिए कॉल बनाम 16608)। ध्यान दें कि यह दृष्टिकोण पिछले एक बग को ठीक करता है जहां बिट सरणी के अंत से परे बिट्स हैश मान को प्रभावित कर सकता है। यह तब हो सकता है जब बिट सरणी लंबाई में कम हो गई हो।

public int GetHashCode(BitArray array) 
    { 
     UInt32 hash = 17; 
     int bitsRemaining = array.Length; 
     foreach (int value in array.GetInternalValues()) 
     { 
      UInt32 cleanValue = (UInt32)value; 
      if (bitsRemaining < 32) 
      { 
       //clear any bits that are beyond the end of the array 
       int bitsToWipe = 32 - bitsRemaining; 
       cleanValue <<= bitsToWipe; 
       cleanValue >>= bitsToWipe; 
      } 

      hash = hash * 23 + cleanValue; 
      bitsRemaining -= 32; 
     } 
     return (int)hash; 
    } 

GetInternalValues ​​विस्तार विधि इस तरह कार्यान्वित किया जाता है:

public static class BitArrayExtensions 
{ 
    static FieldInfo _internalArrayGetter = GetInternalArrayGetter(); 

    static FieldInfo GetInternalArrayGetter() 
    { 
     return typeof(BitArray).GetField("m_array", BindingFlags.NonPublic | BindingFlags.Instance); 
    } 

    static int[] GetInternalArray(BitArray array) 
    { 
     return (int[])_internalArrayGetter.GetValue(array); 
    } 

    public static IEnumerable<int> GetInternalValues(this BitArray array) 
    { 
     return GetInternalArray(array); 
    } 

... more extension methods 
} 

सुधार के लिए कोई सुझाव का स्वागत है!

Answer 1

यदि बिट सरणी 32 बिट्स या कम हैं तो आपको उन्हें 32 बिट पूर्णांक में परिवर्तित करने की आवश्यकता है (यदि आवश्यक हो तो शून्य बिट्स के साथ पैडिंग)।

यदि वे लंबे समय तक हो सकते हैं तो आप उन्हें 32-बिट पूर्णांक और एक्सओआर की श्रृंखला में परिवर्तित कर सकते हैं, या बेहतर: प्रभावी जावा में वर्णित एल्गोरिदम का उपयोग करें।

public int GetHashCode() 
{ 
    int hash = 17; 
    hash = hash * 23 + field1.GetHashCode(); 
    hash = hash * 23 + field2.GetHashCode(); 
    hash = hash * 23 + field3.GetHashCode(); 
    return hash; 
} 

here से लिया गया। फ़ील्ड 1, फ़ील्ड 2 पहले 32 बिट्स, दूसरा 32 बिट्स इत्यादि।

Answer 2

यह एक शब्दकोश में एक कुंजी के रूप में कार्य करने के लिए एक भयानक वर्ग है। GetHashCode() को लागू करने का एकमात्र उचित तरीका बिट्स को एक बाइट [] में कॉपी करने के लिए अपनी CopyTo() विधि का उपयोग कर रहा है। यह बहुत अच्छा नहीं है, यह कचरा का एक टन बनाता है।

बदले में चोरी करें, चोरी करें या इसके बजाय BitVector32 का उपयोग करने के लिए उधार लें। GetHashCode() के लिए इसका एक अच्छा कार्यान्वयन है। यदि आपके पास 32 से अधिक बिट्स हैं तो अपनी कक्षा को कताई करने पर विचार करें ताकि आप कॉपी करने के बिना अंतर्निहित सरणी प्राप्त कर सकें।