यह क्यों है कि, मेरी कुंजी में अधिक '1' बिट्स, हैश मैप में जितना अधिक समय लगता है?

Question

मैं एक कक्षा के लिए एक परियोजना कर रहा हूं जो स्मृति में अधिकतर 0 मानों के साथ एक विशाल मैट्रिक्स को संग्रहीत करने और उस पर कुछ मैट्रिक्स गणित करने पर केंद्रित है। मैट्रिक्स तत्वों को संग्रहीत करने के लिए मेरा पहला विचार HashMap का उपयोग करना था, और बड़ी मात्रा में स्मृति का उपयोग करने से बचने के लिए केवल उन तत्वों को स्टोर करें जो गैर-शून्य हैं।

मैं HashMap के लिए एक कुंजी बनाना चाहता था जो कि तत्व में पंक्ति और कॉलम संख्या दोनों का प्रतिनिधित्व करेगा, जब मैंने मानचित्र में उस प्रविष्टि को एक्सेस किया था, तो मैं दोनों मानों को फिर से निकाल सकता था। मुझे जावा के साथ-साथ सी # - सी # में नहीं पता है, मैं और Column सदस्यों के साथ बनाउंगा, लेकिन जावा में मुझे जल्दी से एहसास हुआ कि उपयोगकर्ता मान प्रकार नहीं हैं। एक समय सीमा के साथ मैं एक सुरक्षित शर्त के साथ गया और Key एक लंबा बनाया। मैंने पहले 32 बिट्स में पंक्ति डेटा (32-बिट int) और पिछले 32 में कॉलम डेटा को कुछ बहुत ही सरल बिट स्थानांतरण का उपयोग करके संग्रहीत किया। [संपादित करें: मैं यह भी ध्यान रखना चाहूंगा कि मेरा हैश मैप एक विशिष्ट प्रारंभिक आकार के साथ शुरू किया गया है जो वास्तव में मेरे द्वारा संग्रहीत मूल्यों की संख्या का प्रतिनिधित्व करता है, जो कभी भी पार नहीं किया जाता है।]

[साइड नोट: कारण मैं चाहता हूं बूट करने के लिए एक छोटे n फिर पंक्ति/स्तंभ डेटा निकालने के बहुत O(n^2) से O(n) को, आव्यूह गुणन की क्षमता बढ़ाने के लिए है, सक्षम होने के लिए और]

क्या मैं इस संरचना को लागू करने के बाद पाया है कि यह एक whopping लेता है एक पाठ फ़ाइल से 23426 x 23426 मैट्रिक्स पढ़ने के लिए 7 सेकंड जिसमें केवल गैर-शून्य तत्व दिए जाते हैं, लेकिन हमें केवल ईज़ीन मानों की गणना करने में 2 सेकंड लगते हैं जिन्हें हमें देने की आवश्यकता होती है! विधियों की चुनिंदा टिप्पणी-आउट के बाद, मैंने निष्कर्ष निकाला है कि इस 7 सेकंड के समय में बड़े पैमाने पर मेरे मूल्यों को HashMap में संग्रहीत किया जाता है।

public void Set(double value, int row, int column) { 
    //assemble the long key, placing row and column in adjacent sets of bits 
    long key = (long)row << SIZE_BIT_MAX; //(SIZE_BIT_MAX is 32) 
    key += column; 
    elements.put(key, value); 
} 

वह मान निर्धारित करने के लिए कोड है। यदि मैं इसके बजाय इस विधि का उपयोग करता हूं:

public void Set(double value, int row, int column) { 
    //create a distinct but smaller key (around 32 bits max) 
    long key = (long)(row * matrixSize) + column; 
    elements.put(key, value); 
} 

पढ़ने में केवल 2 सेकंड लगते हैं। कुंजी के इन दोनों संस्करणों में प्रत्येक तत्व के लिए अलग-अलग हैं, दोनों लंबे प्रकार के होते हैं, और उनमें से किसी एक को बनाने के लिए वास्तविक कोड जटिलता में न्यूनतम होता है। यह elements.put(key, value) है जो 7 सेकंड और 2 के बीच अंतर बनाता है।

मेरा प्रश्न है, क्यों? इन महत्वपूर्ण संस्करणों के बीच मैं जो अंतर देखता हूं वह यह है कि पहली बार बिट्स को 1 से अधिक बार सेट किया जाता है, जबकि दूसरे में इसकी सभी 32 बिट्स 0 पर सेट होती हैं। क्या मैं लाल हेरिंग का पीछा कर रहा हूं, या यह काफी नाटकीय अंतर है प्रदर्शन में HashMap.put विधि में कुछ आंतरिक परिणाम?

Answer 1

कैसे Long पर एक नजर डालें hashCode() विधि (कम से कम OpenJDK 7 में) लागू करता है:

public int hashCode() { 
    return (int)(value^(value >>> 32)); 
} 

इसका मतलब है कि अपने प्रमुख 32 बिट में वापस भरवां हो जाता है; सभी निचले बिट्स एक-दूसरे को अक्सर एक-दूसरे को रद्द कर रहे हैं, जिसके परिणामस्वरूप कई टकराव होते हैं जिसके लिए HashMap की आवश्यकता होती है ताकि बाल्टी में एक मुफ्त स्लॉट की तलाश में अतिरिक्त समय व्यतीत किया जा सके। आपकी दूसरी विधि उस समस्या से बचाती है क्योंकि प्रत्येक कुंजी के जेनरेट किए गए हैश कोड एक अद्वितीय मान है (क्योंकि आपके पास केवल 23426 x 23426 = 548777476 आइटम हैं जो 32 बिट्स में अच्छी तरह से फिट बैठते हैं)।

तो, resaon आपका मुख्य चयन है लेकिन सेट बिट्स की संख्या नहीं है।

हालांकि, वास्तव में क्या आप के साथ

public class MatrixKey { 
    private final int row; 
    private final int column; 
    public MatrixKey(int row, int column) { 
     this.row = row; 
     this.column = column; 
    } 
    public int getRow() { return row; } 
    public int getColumn() { return column; } 
} 

इस वर्ग मतलब है "उपयोगकर्ता मूल्य हैं?" जावा में एक Map के लिए एक पूरी तरह से अच्छा कुंजी कर सकते हैं एक बार आप hashCode() और equals() लागू। बस सुनिश्चित करें कि आप hashCode विधि को Long तरीके से लागू नहीं करते हैं। :)

Answer 2

कार्यान्वयन के आधार पर, आप हैश टकराव मार सकते हैं।

यदि आपके सभी हैश मान एक ही "बाल्टी" में समाप्त होते हैं, तो कार्यान्वयन आम तौर पर उन्हें किसी प्रकार की सूची में फेंक देगा। यदि ऐसा है तो आपके एक्सेस समय में काफी नुकसान होगा।

Answer 3

JDK 6 documentation for Long.hashCode() से

(ध्यान दें कि आपके long आदिम एक Long वस्तु में autoboxed है - सी # पुरातन में जबकि वास्तव में वस्तुओं रहे हैं):

इस लंबे समय के लिए एक हैश कोड देता है। परिणाम इस लंबी वस्तु द्वारा आयोजित आदिम लंबे मूल्य के दो हिस्सों का अनन्य या दो है।यही कारण है कि hashCode अभिव्यक्ति के मूल्य है, यह है:

(int)(this.longValue()^(this.longValue()>>>32)) 

मैं इस परिभाषा दी लगता है, इस बताता है कि क्यों:

टक्कर दर कम हो जाता है जब आप अधिक एन्ट्रापी परिचय और इस तरह यह फैलाने long मान के ऊपरी भाग के माध्यम से अधिक। (संपादित: मैं आदेश गलत पढ़ा है, इसलिए यहाँ नीचे जवाबी तर्क है)

टकराव जब long श्रेणी में विस्तार अधिक होने की संभावना हो सकती है - सभी के बाद, जावा में, hashCodes केवल int आकार के होते हैं, इसलिए आपके पास केवल समान वितरण की सीमित मात्रा हो सकती है। यदि आप जानते हैं कि यह int रेंज पर वितरित "समान रूप से" है तो आपके टकराव कम हो गए हैं। यदि आप इसे long रेंज में फैलाते हैं, तो यह टकराव की संभावना को बहुत बढ़ा देता है।

यहाँ from the HashMap Java documentation (जोर मेरा) है:

इस कार्यान्वयन बुनियादी कार्यों के लिए लगातार समय प्रदर्शन (हो और डाल) प्रदान करता है, हैश फंक्शन संभालने बाल्टी के बीच ठीक से तत्वों disperses

साइड नोट: आपको initial capacity और load factor को ट्यून करके भी अधिक प्रदर्शन लाभ मिलेगा - अधिक जानकारी के लिए HashMap दस्तावेज़ देखें।