हैशकोड के पैर कहाँ से बढ़ते हैं

जावा साक्षात्कार में फिर से, hashCode और equals बारे में पूछें? और साक्षात्कारकर्ताओं में से कौन स्वयं प्रश्न का उत्तर देगा, Object.hashCode() और System.identityHashCode() गणना कैसे की जाती है? इन तरीकों से कॉल करना कितना महंगा है? उन्हें हॉटस्पॉट JVM में कैसे त्वरित किया जा सकता है? मुझे यकीन है कि शायद ही कोई सही जवाब देगा। जब तक, जो इस लेख को पढ़ता है।

एक आम गलतफहमी है कि Object.hashCode मेमोरी में किसी ऑब्जेक्ट का पता देता है। एक बार तो शायद ऐसा ही था। उदाहरण के लिए, Dalvik VM अभी भी दाईं ओर 3 बिट्स द्वारा स्थानांतरित ऑब्जेक्ट के पते का उपयोग करता है। हालांकि, ऐसा कार्यान्वयन असफल है: पहले, क्रमिक रूप से आवंटित वस्तुओं में अनुक्रमिक हैश कोड होंगे; दूसरे, कचरा संग्रहकर्ता अपने पते बदलकर वस्तुओं को स्मृति में ले जा सकता है।

ऐसा हुआ कि पिछले सप्ताह मैं दो बार हैश कोड कंप्यूटिंग के विषय के खिलाफ आया, जिसने मुझे एक नोट लिखने के लिए प्रेरित किया। सबसे पहले, एक बहुत ही गलत विचार वाली टिप्पणी ने मेरी आंख को पकड़ लिया। यह SSSurkv था जिसने काफी सही तरीके से माना कि एक यादृच्छिक संख्या जनरेटर का उपयोग Object.hashCode गणना करने के लिए किया गया था।
- तो कैसे? - आप पूछें। - आखिरकार, एप्लिकेशन के जीवन भर ऑब्जेक्ट का हैश कोड स्थिर रहना चाहिए।

बिलकुल ठीक। अंतर्निहित हैश कोड प्रत्येक कॉल के लिए केवल एक बार hashCode() विधि के लिए पहली कॉल के दौरान उत्पन्न होता है, जिसके बाद इसे बाद के कॉल के लिए ऑब्जेक्ट हेडर में संग्रहीत किया जाता है। लेकिन पहली बार इसका उपयोग यादृच्छिक रूप से किया जाता है! OpenJDK स्रोत कोड ( get_next_hash फ़ंक्शन) को get_next_hash अपने लिए देखें।

मैं शायद इस मामले के बारे में भूल जाता अगर दूसरे दिन मुझे वास्तविक प्रोजेक्ट में वास्तविक समस्या का सामना नहीं करना पड़ता। किसी एप्लिकेशन को प्रोफाइल करते समय, सबसे हॉट तरीकों के बीच, मैंने अचानक IdentityHashMap.put() देखा, जो, मेरी राय में, काफी कुशलता से लागू किया गया है। अड़चन System.identityHashCode() , जो IdentityHashMap पर निर्भर करता है। और ऑब्जेक्ट पर केवल पहचानहैशकोड की पहली कॉल धीमी थी। दूसरी और बाद की कॉल, जैसा कि हम अब जानते हैं, हेडर से संग्रहीत मूल्य लेते हैं।

लेकिन चांदी की परत नहीं है। तथ्य यह है कि हॉटस्पॉट में आप कमांड लाइन स्विच -XX:hashCode=n का उपयोग करके Object.hashCode के कार्यान्वयन का चयन कर सकते हैं -XX:hashCode=n (जहां n 0 से 5 तक है)।
0 - पार्क-मिलर RNG (डिफ़ॉल्ट)
1 - f (पता, global_state)
2 - निरंतर 1
3 - सीरियल काउंटर
4 - वस्तु पता
5 - थ्रेड-स्थानीय ज़ोर्शिफ़्ट
मेरी राय में, सबसे उपयुक्त, उत्तरार्द्ध है - यह केवल बिट संचालन का उपयोग करके एक अच्छा समान वितरण देता है, और, जो प्रतिस्पर्धी एल्गोरिदम के लिए महत्वपूर्ण है, यह वैश्विक चर को नहीं छूता है।
इसलिए, सिर्फ JVM -XX:hashCode=5 कुंजी को जोड़ने -XX:hashCode=5 , मैंने जादुई रूप से अपने एल्गोरिथ्म को 30% तक तेज कर दिया है! इस विकल्प को अभी तक डिफ़ॉल्ट क्यों नहीं बनाया गया है यह एक रहस्य बना हुआ है ...

अंत में, एक मज़ेदार तथ्य: हॉटस्पॉट hashCode 0 कभी नहीं लौटेगा, क्योंकि 0 को एक संकेत माना जाता है कि इस वस्तु के लिए एक हैश कोड अभी तक उत्पन्न नहीं हुआ है:

 if (value == 0) value = 0xBAD ; 

मुझे उम्मीद है कि अब जब आपने hashCode बारे में पूरी सच्चाई जान ली है, तो आप न केवल साक्षात्कार में अपने सहयोगियों को आश्चर्यचकित कर सकते हैं, बल्कि आपके एल्गोरिदम को और भी अधिक कुशल बना सकते हैं।