हैशकोड गणना क्यों अतिप्रवाह बिट्स गुणा और अनदेखा करें?

Question

यह सवाल इस बात के बारे में नहीं है कि क्यों कोई गुणा करता है, यह काफी स्पष्ट है - वितरण के बारे में।

Why use a prime number in hashCode?

बल्कि इस गुणा के अधिक के बारे में एक संपत्ति है कि अधिक महत्वपूर्ण और अधिक कारकों एक hashCode गणना सूत्र में शामिल किए गए हैं हो जाता है।

एक साधारण गणना स्पष्ट रूप से बहती है लेकिन यह बहुत कम महत्व है।

a * 31 + b 

असली समस्या तब प्रदर्शित होती है जब कई आइटम सूत्र में होते हैं।

((a * 31) + b) * 31 ... 6n. 

एक बार से अधिक 5 या 6 शब्द हैं, पहले सत्र के मूल्य के रूप में अपनी बिट्स समय hashCode मूल्य 5 + अवधि सहित पर निर्भर है द्वारा अतिप्रवाह है खो दिया है शामिल हैं। इस प्रणाली का उपयोग केवल अंतिम 5 या तो शब्द अंतिम मूल्य के लिए वास्तव में महत्वपूर्ण योगदानकर्ता हैं।

31^7 > Integer.MAX_VALUE 

तो क्यों न सबसे गणना बिट्स कि वापस w/परिणाम के निचले बिट्स के आसपास है और XOR अतिप्रवाह रोल। मुझे इसकी सराहना है कि इसके लिए थोड़ा सा झुकाव और गणना लंबी अवधि (64 बिट्स) का उपयोग करके की जानी चाहिए ताकि शीर्ष 32 बिट्स को पूर्णांक परिणाम के साथ XOR'd किया जा सके लेकिन कम से कम कोई बिट खो जाएगा।

क्या कोई विशेष कारण है कि अतिप्रवाह को नजरअंदाज क्यों किया जाता है? जैसा कि पहले वर्णित एक लंबे समय तक उपयोग करने के लिए महंगा नहीं है।

संपादित

100000*31^7=   2751261411100000  0x9C641F717C560 
6553600000*31^7 180306667837849600000 0xC641F717C5600000 

ध्यान दें कि बाद के मूल्य जो भी मतलब है कि अपने जवाब 16 बिट बड़ा है पिछले की तुलना में वास्तव में 65536 गुना बड़ा है। ध्यान दें कि 0xC641F717C5600000 का पूर्णांक मान 0xC5600000 है जो वास्तविक बिट मान 16 बिट मान से खो जाता है।

*SAMPLE A* 
65536*4096*27512614111 

=7385361114638319616 
=0x667E12CDF0000000 
    12345678 
=0xF0000000 

*SAMPLE B* 
9*65536*4096*27512614111 

=66468250031744876544 
=0x9A6EA93D70000000 
    12345678 
=0x70000000 

सूचना है कि नमूना बी के शीर्ष सबसे बिट जो वास्तव में 9x नमूना एक है अंतिम 32 बिट मूल्य में लगभग पूर्ण कोई फर्क नहीं पड़ता - अगर मैं 17x को 9x बदल तो निम्न बिट्स होगा समान। हालांकि यदि शीर्ष 32 बिट्स के साथ अतिप्रवाह और xord के कारण शीर्षतम बिट्स "खो गए" नहीं थे तो मान अलग होगा।

Answer 1

कोई विशेष कारण है कि अतिप्रवाह नजरअंदाज कर दिया है है? जैसा कि पहले वर्णित एक लंबे समय तक उपयोग करने के लिए महंगा नहीं है।

लेकिन इसके बारे में निश्चित रूप से कोई लाभ नहीं है। यह पद्धति आम तौर पर शुरू करने के लिए मूल्यों का एक अच्छा वितरण पैदा करती है।

Answer 2

एक विषम संख्या से गुणा करने से लाभ यह है कि; पहले की संख्या पूरी तरह से पूर्णांक के अंत से कभी नहीं गिरती है। के लिए एक तत्व नष्ट हो, 31^n 2 के एक शक्ति की आवश्यकता होगी, और कहा कि ऐसा नहीं हो सकता। आपके मामले में, 31^7 साथ, उदाहरण के लिए, आप एक 32-बिट संख्या के लिए 0x67E12CDF मिलता है, इस प्रकार, इनपुट तत्व है कि मूल्य से गुणा अभी भी परिणाम के लिए, अतिप्रवाह के बावजूद योगदान देगा।

Answer 3

मुझे उदाहरणों में बिंदु नहीं दिख रहा है। वे मुझे लगता है, हैश कोड की गणना करने के तरीके से असंबद्ध: a * 31 + b।

आप शायद a और b के पा सकते हैं, जो एक ही हैशकोड देगा, (लेकिन जहां उच्च बिट अलग हैं)। फिर यह हैशकोड में उच्च बिट्स को वापस करने के लिए समझ में आता है।

या, ((a * 31) + b)*31 + ... + z के लिए एक अलग उदाहरण होगा। फिर कुछ a, b, ..., z खोजें, जहां हैशकोड a पर निर्भर नहीं है। तो a एक महत्वपूर्ण योगदानकर्ता नहीं होगा।

बेशक

, यदि आप 3165536 से बदलने के लिए, यह उन a, ..., z को खोजने के लिए बहुत आसान है। कोई भी मूल्य करेगा, a बिट्स बस गिर जाएंगे, a बाईं ओर स्थानांतरित हो जाएंगे और कट ऑफ हो जाएंगे। लेकिन, क्या आप 31 के लिए ऐसा कर सकते हैं? या इसी तरह, आप उच्च बिट्स को वापस कर सकते हैं। लेकिन, क्यों? क्या आपको ऐसा कोई मामला मिल सकता है जहां यह मदद करता है?

65536 के साथ समस्या यह है कि बाइनरी में यह 10000000000000000 जैसा दिखता है। इसलिए, जब आप इसके द्वारा एक संख्या गुणा करते हैं, बाइनरी में यह 16 शून्य फिर से होगा। बाइनरी में 31, 11111 के लिए, ऐसा नहीं होगा।

ओह, मेरा मतलब यह नहीं है कि वे उदाहरण मौजूद नहीं हैं, क्योंकि वे करते हैं (यह केवल बाद में हैश है)। लेकिन, आपको कई या समान उदाहरण नहीं मिलेगा।