ConcurrentHashMap और फाइबोनैचि संख्या असंगत परिणाम

Question

मैं रिकर्सिवली फिबोनैकी संख्या की गणना, एक ConcurrentHashMap और computeIfAbsent() विधि के साथ के लिए एक कार्यक्रम लिखा था 10 to 20 से कार्यक्रम कभी नहीं रुकती

public class Test { 
    static Map<Integer, Integer> concurrentMap = new ConcurrentHashMap<>(); 

    public static void main(String[] args) { 
     System.out.println("Fibonacci result for 20 is" + fibonacci(20)); 
    } 

    static int fibonacci(int i) { 
     if (i == 0) 
      return i; 

     if (i == 1) 
      return 1; 

     return concurrentMap.computeIfAbsent(i, (key) -> { 
      System.out.println("Value is " + key); 
      return fibonacci(i - 2) + fibonacci(i - 1); 
     }); 
    } 
} 

कुछ एक मुझे बता सकते हैं क्यों यह हमेशा के लिए अटक जा रहा है?

Answer 1

आप एक डेडलॉक मार रहे हैं।

computeIfAbsent एक ConcurrentHashMap पर उस बाल्टी को लॉक करेगा जिसमें संबंधित कुंजी जाएगी। यदि आप अपने मानचित्र में बाल्टी की संख्या से अधिक फाइबोनैकी की गणना करने का प्रयास कर रहे हैं, तो रिकर्सिव कॉल कॉल की स्टैक को पहले से लॉक कर चुके बाल्टी को लॉक करने का प्रयास करेंगे। लेकिन निश्चित रूप से, उस लॉक को तब तक जारी नहीं किया जा सकता जब तक कि सभी रिकर्सिव कॉल पूरी नहीं हो जातीं। इस प्रकार, आपका डेडलॉक।

मैं यहां ConcurrentHashMap का उपयोग करने के आपके निर्णय पर पुनर्विचार करूंगा।

Answer 2

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

मुझे आश्चर्य है कि आप कैशिंग के लिए ConcurentHashMap का उपयोग क्यों कर रहे हैं। मैं या तो सरल नक्शा, या कैशिंग के लिए सरणी का उपयोग करेंगे।

मानचित्रों को सरणी के खिलाफ लाभ होता है, जब मानों को छिड़क दिया जाता है, लेकिन जब आपके पास संख्याओं का अनुक्रम होता है, तो आप सरल सरणी का उपयोग कर सकते हैं।

Answer 3

मैंने थ्रेड डंप लिया, और हम लॉक 0x000000076b70bba0 के साथ थ्रेड को मृत लॉक समस्या का कारण बन सकते हैं।

अगर गलत है तो कृपया मुझे सही करें। जबकि गणना कार्य प्रगति पर है

main - priority:5 - threadId:0x00000000021af000 - nativeId:0x2798 - state:RUNNABLE 
    stackTrace: 
    java.lang.Thread.State: RUNNABLE 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1674) 
    - locked <0x000000076b70bba0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70c720> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70c5c0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70c460> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70c300> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70c1a0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70c040> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70bee0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70bba0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.main(Test.java:8) 
    Locked ownable synchronizers: 
    - None 

Answer 4

अन्य धागे से इस नक्शे पर Oracle Doc

कुछ प्रयास किया अद्यतन संचालन के अनुसार अवरुद्ध किया जा सकता है, तो गणना छोटे और सरल होना चाहिए, और करने के लिए प्रयास नहीं करना चाहिए इस नक्शे के किसी भी अन्य मानचित्रण को अपडेट

के रूप में ठीक ही जो सी सर्वोच्च जवाब में से कहा, ConcurrentHashMap के डिफ़ॉल्ट प्रारंभ एक SMA है तात्कालिकता के समय आवंटित बाल्टी की संख्या होगी।

ConcurrentHashMap का उपयोग करने का उद्देश्य नक्शा के समेकित संशोधन को कई धागे से अवरुद्ध करने की आवश्यकता के बिना (link) की अनुमति देना है।

---

आप अभी भी अपने आवेदन के लिए ConcurrentHashMap का उपयोग कर के साथ रहना चाहते हैं, तो मैं इसके निर्माण के दौरान initialCapacity बढ़ाने की सलाह देते हैं।

static Map<Integer, Integer> concurrentMap = new ConcurrentHashMap<>(11); 

, तक फिबोनैकी श्रृंखला और 25

---

दस्तावेज़ के अनुसार सहित

ConcurrentHashMap() की गणना कर सकते
डिफ़ॉल्ट प्रारंभिक तालिका आकार के साथ एक नया, रिक्त मानचित्र बनाती (16)।

हालांकि, मैं इस पर भिन्न होना चाहता हूं क्योंकि मैंने देखा कि डिफ़ॉल्ट आकार बहुत छोटा है।
इसका कारण यह है कि जब आप ConcurrentHashMap<>(11) से ConcurrentHashMap<>() < - डिफ़ॉल्ट 16 होना चाहिए .. लेकिन यह नहीं है।