पूर्णांक गुणा, अतिप्रवाह, और सूचना हानि

Question

पर मैं जोशुआ ब्लोच के प्रभावी जावा के Chapter 3 के माध्यम से पढ़ रहा हूं। मद 8 में:

result = 37 * result + c; 

इसके बाद वे बताती हैं कि क्यों 37 में चुना गया था (जोर जोड़ा):

हमेशा जब आप ओवरराइड hashCode ओवरराइड के बराबर होती है, लेखक अपने हैशिंग समारोह में निम्नलिखित संयोजन कदम का उपयोग करता है

गुणक 37 चुना गया था क्योंकि यह एक विषम प्रधान है। यदि यह भी था और गुणा बहती है, तो जानकारी खो जाएगी क्योंकि गुणा दो से स्थानांतरित करने के बराबर है। एक प्राइम नंबर का उपयोग करने के फायदे कम स्पष्ट हैं, लेकिन इस उद्देश्य के लिए प्राइम का उपयोग करना पारंपरिक है।

मेरा प्रश्न क्यों यह फर्क पड़ता है कि संयोजन कारक (37) अजीब है? क्या कारक अजीब था या नहीं, इस पर ध्यान दिए बिना सूचना के नुकसान में ओवरफ्लो परिणाम गुणा नहीं करेगा?

Answer 1

विचार करें कि क्या होता है जब बेस-2 प्रतिनिधित्व में सकारात्मक मूल्य दो बार गुणा किया जाता है - अंततः सभी सेट बिट्स अंत में मार्च से निकलते हैं, जिससे आपको शून्य मिल जाता है।

एक भी गुणक कम विविधता वाले हैश कोड का परिणाम देगा।

दूसरी तरफ अजीब संख्याएं अतिप्रवाह हो सकती हैं, लेकिन विविधता के नुकसान के बिना।

Answer 2

एक hashCode के प्रयोजन जो अनियमितता का अभाव है जब आप 2 से कई सबसे कम बिट केवल 0 हो सकता है इनपुट (विशेष रूप से इन के रूप में निम्न बिट्स अक्सर अधिक उपयोग किया जाता है)

के आधार पर यादृच्छिक बिट्स के लिए, है । यदि आप एक विषम संख्या से एकाधिक हैं तो सबसे कम बिट अजीब या यहां तक ​​कि हो सकता है।

---

ऐसा ही एक सवाल आप यहाँ क्या मिलता है

public static void main(String... args) { 
    System.out.println(factorial(66)); 
} 

public static long factorial(int n) { 
    long product = 1; 
    for (; n > 1; n--) 
     product *= n; 
    return product; 
} 

प्रिंट

0 

हर दूसरा नंबर एक और भी है और हर आगे 4 आदि की एक बहु

Answer 3

समाधान आपके गुणक और आपके मॉड्यूलो संख्या के संख्या सिद्धांत और Lowest common denominator में निहित है।

एक उदाहरण मदद कर सकता है। आइए 32 बिट के बजाय आपको केवल एक संख्या का प्रतिनिधित्व करने के लिए 2 बिट मिले। तो आपको 4 संख्याएं (कक्षाएं) मिलीं। 0, 1, 2 और 3

सीपीयू में एक अतिप्रवाह

Class - x2 - mod 4 - x2 - mod 4 

0  0  0  0  0 

1  2  2  4  0 

2  4  0  0  0 

3  6  2  4  0 

एक सापेक्ष आपरेशन के रूप में ही 2 आपरेशन आप केवल 1 संभावित संख्या (वर्ग) बाईं मिल गया के बाद है। तो आपके पास 'खो' जानकारी है।

Class - x3 - mod 4 - x3 - mod 4 ... 

0  0  0  0  0 

1  3  3  9  1 

2  6  2  6  2 

3  9  1  3  3 

यह हमेशा के लिए जा सकता है और आपके पास अभी भी सभी 4 कक्षाएं हैं। तो आप जानकारी खोना नहीं है।

कुंजी यह है कि आपके मल्टीप्लियर का एलसीडी और आपकी मॉड्यूलो कक्षा 1 है। यह सभी विषम संख्याओं के लिए सच है क्योंकि आपका मॉड्यूलो नंबर वर्तमान में हमेशा 2 की शक्ति है। उन्हें प्राइम नहीं होना चाहिए और उनके पास नहीं होना चाहिए विशेष रूप से 37 होना चाहिए। लेकिन जानकारी नुकसान सिर्फ एक मापदंड क्यों 37 उठाया जाता है अन्य criterias मूल्यों आदि क्यों ...

प्रधानमंत्री संख्या विविधता रखने के लिए hashing के लिए उपयोग किया जाता है की

Answer 4

गैर गणित सरल संस्करण के वितरण हो रहा है।

शायद सेट और मानचित्र कार्यान्वयन के कारण विविधता अधिक महत्वपूर्ण है। ये कार्यान्वयन प्रविष्टियों के आंतरिक सरणी को इंडेक्स करने के लिए ऑब्जेक्ट हैश संख्याओं के अंतिम बिट्स का उपयोग करते हैं।

उदाहरण के लिए, आकार 8 के साथ प्रविष्टियों के लिए आंतरिक तालिका (सरणी) के साथ हैश मैप में यह तालिका प्रविष्टि को एड्रेस करने के लिए हैश संख्याओं के अंतिम 3 बिट्स का उपयोग करेगा।

 

    static int indexFor(int h, int length) { 
     return h & (length-1); 
    } 

वास्तव में ऐसा नहीं है, लेकिन अगर पूर्णांक वस्तु है

 

    hash = 4 * number; 

तालिका तत्वों की सबसे खाली हो जाएगा लेकिन उसमें कुछ ऐसे भी कई प्रविष्टियों शामिल होंगे। यह विशेष प्रविष्टि की खोज करते समय अतिरिक्त पुनरावृत्तियों और तुलना संचालन का कारण बन जाएगा।

मुझे लगता है कि जोशुआ ब्लॉच की मुख्य चिंता हैश पूर्णांक वितरित करना संभव था, साथ ही साथ मैप्स और सेट्स में वस्तुओं को वितरित करके संग्रह के प्रदर्शन को अनुकूलित करने के लिए भी संभव है। प्राइम संख्या सहजता से वितरण का एक अच्छा कारक प्रतीत होता है।

Answer 5

प्राइम नंबर विविधता सुनिश्चित करने के लिए सख्ती से आवश्यक नहीं हैं; यह आवश्यक है कि कारक मॉड्यूलस के लिए अपेक्षाकृत प्रमुख हो।

बाइनरी अंकगणित के लिए मॉड्यूलस हमेशा दो की शक्ति है, कोई विषम संख्या अपेक्षाकृत प्रमुख है, और पर्याप्त होगा। यदि आप ओवरफ्लो के अलावा एक मॉड्यूलस लेना चाहते थे, हालांकि, एक प्रमुख संख्या विविधता सुनिश्चित करना जारी रखेगी (मान लीजिए कि आपने एक ही प्राइम नहीं चुना है ...)।