औसत प्रोग्रामर के लिए "अच्छा पर्याप्त" हैश फ़ंक्शन है?

Question

हमें बताया गया है कि हमें अपनी कक्षाओं के लिए हैशकोड() को लागू करना चाहिए, लेकिन मेरे जैसे अधिकांश लोगों को यह नहीं पता कि यह कैसे करना है या अगर हमें "गलत" मिलता है तो क्या होता है। उदाहरण के लिए मुझे पेड़ (Finding the most frequent subtrees in a collection of (parse) trees) में इंडेक्सिंग नोड्स के लिए हैश फ़ंक्शन की आवश्यकता है। इस मामले में मुझे क्रमशः बाल नोड्स के आधार पर हैशकोड उत्पन्न करने की आवश्यकता है, उदा।

hashCode = function(child1.hashCode, child2.hashCode, ...) 

hashCodes उत्तरों की एक recent discussion में तार के लिए एक हैश और भी bitshifting (एक लंबे प्रधानमंत्री और 31 के आधार पर) शामिल थे। स्ट्रिंग हैश है:

// adapted from String.hashCode() 
public static long hash(String string) { 
    long h = 1125899906842597L; // prime 
    int len = string.length(); 

    for (int i = 0; i < len; i++) { 
    h = 31*h + string.charAt(i); 
    } 
    return h; 
} 

मुझे सुरक्षा में रूचि नहीं है और टकराव नहीं है। क्या आदेशित वस्तुओं के हैशकोड के संयोजन के लिए एक "सार्वभौमिक कार्य" है जो नुकसान से अधिक अच्छा होगा (और इसे बिल्कुल कॉल करने से ज्यादा अच्छा नहीं)?

क्या ऐसी साइट भी है जहां हम आम मामलों को देख सकते हैं? तार, सूचियां, आदि)

मैंने एक भाषा निर्दिष्ट नहीं की क्योंकि मुझे उम्मीद थी कि सार्वभौमिक दृष्टिकोण थे। लेकिन अगर यह गंभीरता से भाषा-विशिष्ट है तो कृपया भाषा को इंगित करें और यह सार्वभौमिक क्यों नहीं है।

अद्यतन आईडीई के हैशकोड जनरेटर का उपयोग करने के लिए दो सुझाव हैं। यह एक उत्कृष्ट डिफ़ॉल्ट लगता है; यहाँ Netbeans है:

public int hashCode() { 
    int hash = 5; 
// objects 
    hash = 97 * hash + (this.rootElement != null ? this.rootElement.hashCode() : 0); 
    hash = 97 * hash + (this.tableElement != null ? this.tableElement.hashCode() : 0); 
// a string 
    hash = 97 * hash + (this.tag != null ? this.tag.hashCode() : 0); 
    return hash; 
} 

Answer 1

जोशुआ ब्लोच के Effective Java में एक उत्कृष्ट हैशकोड() है। नमूना अध्याय 3, "सभी ऑब्जेक्ट्स के लिए सामान्य तरीके" नि: शुल्क था (ठीक है, इसके लिए सूर्य की पुरानी साइट पर एक पृष्ठ था जब यह वापस किया जाता था। यदि आप खोज करते हैं तो आपको अभी भी उस अध्याय का पीडीएफ संस्करण मिल रहा है कहीं)।

आप अपाचे कॉमन्स लैंग में HashCodeBuilder के स्रोत को भी देख सकते हैं, लेकिन इसे उद्धृत किए बिना कक्षा के लिए कॉपी न करें। वास्तव में इस बारे में जानने के लिए समय बिताया गया है - यह आपको एक बेहतर व्यक्ति बना देगा।

Answer 2

आप Windows का उपयोग कर रहे हैं, तो आप HashData() उपयोग कर सकते हैं।

Answer 3

हालांकि टैग गायब होने के बावजूद, आप मान लेंगे कि आप जावा के बारे में बात कर रहे हैं।

एक "आलसी" समाधान ग्रहण 3.5 के साथ पैक किया जाता है, जो आपके लिए बटन के धक्का पर हैश कोड उत्पन्न करेगा। toString() और बराबर() भी। बहुत अच्छा! मुझे संदेह है कि आप आईडीईए और नेटबीन में समान कार्यक्षमता पा सकते हैं।

इसके अलावा, व्यावहारिक रूप से किसी भी हैश फ़ंक्शन जो लगातार उसी इनपुट के लिए समान मूल्य उत्पन्न करता है। यह (शायद) केवल हैशमैप्स जैसी चीजों की दक्षता को प्रभावित करेगा।

Answer 4

यदि आप कस्टम कक्षाओं के लिए हैशकोड को परिभाषित करने के संबंध में बात कर रहे हैं, तो सबसे अच्छा शर्त है कि आप अपने सभी फ़ील्ड हैशकोड फ़ंक्शंस के कुछ प्रकार के गणितीय संयोजन को परिभाषित करें।

हैशकोड को परिभाषित करने में, आपका लक्ष्य आम तौर पर टकराव को कम करने के लिए होता है ताकि यदि आप ऐसा कुछ करते हैं, तो आप आमतौर पर स्पष्ट रूप से स्पष्ट होंगे।

hashcode=(field1.hashcode()*7)+(field2.hashcode()*3)+(field3.hashcode()*51)... 

Answer 5

किसी भी प्रबंधित वातावरण में किसी ऑब्जेक्ट हैश फ़ंक्शन का कच्चा कार्यान्वयन स्मृति पता ही होता है।यदि आपको हैश फ़ंक्शन के गुणों की परवाह नहीं है, तो कोई भी मूल्य तब तक करेगा जब तक कि किसी प्रकार का समकक्ष संबंध अलग-अलग उदाहरणों के बीच मौजूद न हो जो समान मान का प्रतिनिधित्व करते हैं।

यदि आप डेटाबेस डेटाबेस के संबंध में परिचित हैं, तो अपनी ऑब्जेक्ट की प्राथमिक कुंजी के बारे में सोचें? प्राथमिक मूल्य प्राथमिक कुंजी का गठन करता है?

कहना है कि यह a, b and c है, ठीक है, तो hashCode अपने क्रियान्वयन की तरह लग रहे हैं इस

return a.hashCode()^b.hashCode()^c.hashCode(); 

^है XOR (अनन्य या) बिट के लिहाज से ऑपरेशन, इस तरह से आप श्रृंखला कर सकते हैं एक साथ मूल्यों के किसी भी संख्या एक हैश मूल्य बनाने के लिए, और अभी भी एक सभ्य फैलाव बनाए रखने के लिए।

Answer 6

आपके प्रश्न का उत्तर देने के लिए क्या गलत हो सकता है: आपके फ़ंक्शन द्वारा उत्पन्न हैशकोड का उपयोग आपके वर्ग के उदाहरणों के लिए जगह खोजने के लिए किया जाएगा यदि आप इसे हैशटेबल (शब्दकोश/मानचित्र) में डालते हैं। यदि आपका हैशफंक्शन बहुत से टकराव उत्पन्न करता है, तो आपके हैशटेबल का प्रदर्शन ओ (एन) जितना खराब हो सकता है।

public static int CombineHashCodes(params int[] hashCodes) 
{ 
    unchecked 
    { 
     var result = 0; 
     foreach (var hash in hashCodes) 
      result = (result * 397)^hash; 
     return result; 
    } 
} 

सहज ज्ञान युक्त तर्क है कि संयोजन पहलू XOR ऑपरेटर है:

Answer 7

यह एक हैश कोड के संयोजन समारोह है कि मैं का उपयोग करें (सी # में) है। इस प्रकार .NET 4 टुपल्स के लिए करता है:

public static int CombineHashCodes(int h1, int h2) 
{ 
    return ((h1 << 5) + h1)^h2; 
}