जावा में हैश मैप.containsKey() की समय जटिलता क्या है?

Question

मुझे यह जानने की ज़रूरत है: जावा में हैश मैप.containsKey() की समय जटिलता क्या है?

Answer 1

API doc ofHashMap से

है:

इस कार्यान्वयन बुनियादी कार्यों के लिए लगातार समय प्रदर्शन (हो और डाल प्रदान करता है), मानते हुए हैश फ़ंक्शन तत्वों को बाल्टी के बीच ठीक से फैलता है।

containsKey() के बाद से सिर्फ एक get() कि पुनः प्राप्त मूल्य फेंक देता है, यह हे (1) (यह मानते हुए हैश फंक्शन ठीक से काम करता है, फिर से) है।

Answer 2

यह सामान्य रूप में O(1) है, लेकिन सबसे खराब स्थिति में यह O(n)

public boolean containsKey(Object key) { 
    352   return getEntry(key) != null; 
    353  } 
    354 
    355  /** 
    356  * Returns the entry associated with the specified key in the 
    357  * HashMap. Returns null if the HashMap contains no mapping 
    358  * for the key. 
    359  */ 
    360  final Entry<K,V> getEntry(Object key) { 
    361   int hash = (key == null) ? 0 : hash(key.hashCode()); 
    362   for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
    363    e != null; 
    364    e = e.next) { 
    365    Object k; 
    366    if (e.hash == hash && 
    367     ((k = e.key) == key || (key != null && key.equals(k)))) 
    368     return e; 
    369   } 
    370   return null; 
    371  } 

Answer 3

आम तौर पर ओ (1), लेकिन यदि हम एक खराब हैशकोड फ़ंक्शन का उपयोग कर रहे हैं, तो हमें एक बाल्टी में कई तत्व जोड़ना होगा ताकि यह सबसे खराब स्थिति में ओ (एन) हो।

Answer 4

containsKey के समय जटिलता, JDK-1.8 में बदल गया है के रूप में दूसरों का उल्लेख किया यह आदर्श मामलों में O(1) है। हालांकि, टकराव के मामले में जहां keysComparable, डिब्बे भंडारण टकराती तत्वों का अब रेखीय नहीं कर रहे हैं वे कुछ सीमा TREEIFY_THRESHOLD कहा जाता है, जो 8 के बराबर है से अधिक के बाद,

/** 
* The bin count threshold for using a tree rather than list for a 
* bin. Bins are converted to trees when adding an element to a 
* bin with at least this many nodes. The value must be greater 
* than 2 and should be at least 8 to mesh with assumptions in 
* tree removal about conversion back to plain bins upon 
* shrinkage. 
*/ 
static final int TREEIFY_THRESHOLD = 8; 

दूसरे शब्दों में कर रहे हैं, TreeNodes उपयोग किया जाएगा (TreeMap में उन लोगों के समान) डिब्बे स्टोर करने के लिए, (यानी: एक लाल-काला पेड़ संरचना) और इससे हमें टकराव के मामले में O(lgn) जटिलता मिलती है।

ही get(key) जहां जहां दोनों तरीकों फोन getNode के लिए लागू होता है आंतरिक

नोट: n यहाँbin और नहीं HashMap