java - इस उदाहरण में HashMap हैश एल्गोरिथम के बारे में स्पष्टीकरण




collision hashcode (4)

क्या कोई मुझे समझा सकता है कि मुझे उस प्रश्न का सही हल क्यों मिला जो मैं उस उत्तर के बजाय हल करने की कोशिश कर रहा था जिसकी मुझे उम्मीद थी?

यह संयोग की बात है

अपडेट करें

जैसा कि पहले ही दूसरों द्वारा उल्लेख किया गया है, LinkHashMap छांटे के विपरीत, या प्रविष्टि के क्रम को संरक्षित करने वाले LinkHashMap विपरीत, एक LinkHashMap किसी भी क्रम की गारंटी नहीं देता है। तो हां, अगर आपके तत्व हल किए गए हैं, तो यह सिर्फ एक संयोग है।

मैं इस प्रश्न को हल करने की कोशिश कर रहा था:

केवल 3 अद्वितीय संख्याओं के साथ पूर्णांकों की एक सरणी को देखते हुए संख्याओं को ओ (एन) समय में आरोही क्रम (उनकी संबंधित आवृत्तियों के साथ) में प्रिंट करें।

मैं counting sort एल्गोरिथ्म का उपयोग किए बिना इसे हल करना चाहता था, इसलिए मैंने सोचा कि मैं बस एक for loop कर सकता HashMap entrySet और HashMap entrySet में नंबर डाल सकता हूं और फिर HashMap entrySet माध्यम से loop HashMap entrySet और आवश्यक जानकारी प्रिंट कर सकता HashMap entrySet

यहाँ समारोह है:

public static void printOut(int[] arr){
        Map<Integer,Integer> hm=new HashMap<Integer,Integer>();
        for(int num : arr){
            if(hm.containsKey(num)){
                hm.put(num,hm.get(num)+1);
            }else{hm.put(num,1);}
        }
        for(Map.Entry<Integer,Integer> entry : hm.entrySet()){
            System.out.println("Key= "+entry.getKey()+" Value= "+entry.getValue());
        }
}

जब मेरी सरणी थी तो यह चाल थी: [3, 3, 2, 1, 3, 2, 1]

हालाँकि उपरोक्त सरणी से कोई टकराव नहीं होना चाहिए, इसलिए मैंने एक ऐसे सरणी का उपयोग करने का प्रयास किया, जो टकराव की ओर ले जाए, मैंने अपने फ़ंक्शन का परीक्षण करने वाले सरणियों में से एक था: [6,6,9,9,6,3,9] अभी तक मेरे कार्य ने अभी भी Keys को आरोही क्रम में मुद्रित किया, जो मुझे भ्रमित कर गया, क्योंकि मैंने सोचा कि जब hashIndex = key % noOfBuckets एक पूर्णांक है हैश कोड hashIndex = key % noOfBuckets होना चाहिए hashIndex = key % noOfBuckets जब मेरे पास संख्या 6, 9 and 3 जैसा कि मेरे HashMap keys मुझे लगा कि टक्करें होंगी और मेरा कार्य प्रिंट होना चाहिए (उपरोक्त प्रयुक्त सरणी के आधार पर):

Key= 6 Value= 3
Key= 9 Value= 3
Key= 3 Value= 1 

लेकिन इसके बजाय यह मुद्रित:

Key= 3 Value= 1
Key= 6 Value= 3
Key= 9 Value= 3

क्या कोई मुझे समझा सकता है कि मुझे उस प्रश्न का सही हल क्यों मिला जो मैं उस उत्तर के बजाय हल करने की कोशिश कर रहा था जिसकी मुझे उम्मीद थी?

धन्यवाद।


  1. हैश मैप / हैश टेबल में "टकराव" शब्द एक ऐसी स्थिति है जब दो अलग-अलग कुंजी में समान हैश कोड होता है। HashMap के जावा कार्यान्वयन टकरावों को हल करने के लिए सूची / आरबी-पेड़ का उपयोग करते हैं लेकिन जब आपके पास वास्तव में 3 पूर्णांक कुंजी होती है तो यह निश्चित रूप से आपका मामला है।
  2. HashMap तत्वों के सम्मिलन (या किसी अन्य) के आदेश की गारंटी नहीं देता है। LinkedHashMap या TreeMap जैसी अलग-अलग संरचनाएं हैं जो कुछ आदेश की गारंटी दे सकती हैं। लेकिन आपके मामले के लिए इस संरचना का उपयोग करना थोड़ा उपरिव्यय है क्योंकि आप निरंतर समय पर 3 तत्वों के अपने संग्रह को सॉर्ट कर सकते हैं। तुम भी अपने काम के लिए HashMap के बजाय Map.Entry की सरणी का उपयोग कर सकते हैं।

मुझे यकीन नहीं है कि आप वास्तव में "टकराव" से क्या मतलब है, लेकिन जैसा कि आप पहले ही बता चुके हैं कि यदि आप हैशपॉप ( https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html के प्रलेखन को पढ़ते हैं https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html ) आदेश देने के बारे में कोई घोषणा नहीं है:

"यह वर्ग नक्शे के आदेश के अनुसार कोई गारंटी नहीं देता है; विशेष रूप से, यह गारंटी नहीं देता है कि आदेश समय के साथ स्थिर रहेगा।"

और बाद में "प्रभाव को संशोधित करने के लिए, जब चाबियाँ तुलना होती हैं, तो यह वर्ग संबंधों को तोड़ने में मदद करने के लिए कुंजियों के बीच तुलना क्रम का उपयोग कर सकता है।"

आप अंतिम इंटेगर को कुंजियों के रूप में उपयोग करते हैं, जो कि तुलनात्मक इंटरफ़ेस को लागू कर रहे हैं, इसका मतलब है कि हाशप कार्यान्वयन उनकी कुंजी का आदेश दे सकता है - जो यह वास्तव में करता है।

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


यह महज संयोग है और एंट्रीसेट और कीसेट से ऑर्डर की गारंटी नहीं है। Infact hashmap खुद प्रविष्टि आदेश की गारंटी नहीं देता है और यह आदेश रीशेज़िंग के दौरान भी बदल सकता है।

अब आप हैशमैप में आदिम इंट को सम्मिलित करने का प्रयास कर रहे हैं, जो आंतरिक रूप से ऑटोबॉक्सिंग करता है और इंटेगर ऑब्जेक्ट को कुंजी के रूप में डाला जाएगा।

इंटेगर हैशकोड फ़ंक्शन है

public static int hashCode(int value) {
    return value;
} 

इसका मतलब है कि यह सीधे मूल्य पर लौटता है, आपके मामले में 6,9 और 3

फिर इस हैशकोड का उपयोग हैशैम्प द्वारा आंतरिक रूप से सूचकांक स्थिति प्राप्त करने के लिए किया जाता है

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

जैसा कि आप देख सकते हैं कि दिए गए मानों के साथ बिटवाइज़ ऑपरेटर 0 लौटाएगा और उन मूल्यों पर घातांक 3 के एक ही सूचकांक कविता को जन्म देगा जो टकराव की ओर जाता है। तो, हैशमैप इसके बाद LinkedList (java8) और ट्री (java8 और इसके दूसरे वर्जन) का उपयोग करके स्टोर करेगा।

KeySet या entrySet के माध्यम से पुनरावृत्ति करते समय, आदेश की गारंटी नहीं होगी और इसलिए आपको जो आदेश मिल रहा है वह मात्र संयोग है।





hashcode