क्यों एक बाहरी इंटरफ़ेस हैशकोड/हैश मैप के बराबर प्रदान करने की अनुमति नहीं देता है?

TreeMap के साथ एक कस्टम Comparator प्रदान करने के लिए यह छोटा है, इस प्रकार मानचित्र में जोड़े गए Comparable ऑब्जेक्ट्स द्वारा प्रदान किए गए अर्थशास्त्र को ओवरराइड करना। HashMap एस हालांकि इस तरह से नियंत्रित नहीं किया जा सकता है; हैश मान और समानता जांच प्रदान करने वाले फ़ंक्शन 'साइड-लोड' नहीं हो सकते हैं।क्यों एक बाहरी इंटरफ़ेस हैशकोड/हैश मैप के बराबर प्रदान करने की अनुमति नहीं देता है?

मुझे संदेह है कि यह एक इंटरफ़ेस डिज़ाइन करने के लिए आसान और उपयोगी दोनों होगा और HashMap (या एक नई कक्षा) में इसे फिर से निकालने के लिए उपयोगी होगा? कुछ इस तरह, बेहतर नाम के साथ छोड़कर:

new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY);

यह संभव नहीं होगा, या आप इस दृष्टिकोण के साथ किसी भी बुनियादी समस्याओं देख सकते हैं:

interface Hasharator<T> { 
    int alternativeHashCode(T t); 
    boolean alternativeEquals(T t1, T t2); 
    } 

    class HasharatorMap<K, V> { 
    HasharatorMap(Hasharator<? super K> hasharator) { ... } 
    } 

    class HasharatorSet<T> { 
    HasharatorSet(Hasharator<? super T> hasharator) { ... } 
    }

case insensitive Map समस्या एक छोटी सी समाधान मिलता है?

क्या दृष्टिकोण किसी भी मौजूदा (गैर-जेआरई) libs में उपयोग किया जाता है? कोई के लिए शीर्षक परिवर्तित:;: (। गूगल, कोई किस्मत की कोशिश की)

संपादित करें)

संपादित hazzen द्वारा प्रस्तुत अच्छा वैकल्पिक हल है, लेकिन मुझे डर लग रहा इस समाधान मैं से बचने के लिए कोशिश कर रहा हूँ ... है अब "तुलनात्मक" का जिक्र करें; मुझे संदेह है कि यह थोड़ा उलझन में था।

संपादित करें: प्रदर्शन के संबंध में स्वीकृत उत्तर; एक और विशिष्ट जवाब प्यार करेंगे!

संपादित करें: एक कार्यान्वयन है; नीचे स्वीकृत उत्तर देखें।

संपादित करें: पहली वाक्य को दोबारा स्पष्ट करने के लिए दोहराया गया है कि यह पक्ष-लोडिंग है जिसके बाद मैं हूं (ऑर्डर नहीं कर रहा हूं; ऑर्डरिंग हैश मैप में नहीं है)।

स्रोत

2008-10-17 volley

"यह कक्षा मानचित्र के आदेश के रूप में कोई गारंटी नहीं देती है, विशेष रूप से, यह गारंटी नहीं देती है कि आदेश समय के साथ स्थिर रहेगा।" - हैश मैप के जावाडॉक्स। दूसरे शब्दों में, हैश मैप का आदेश नहीं दिया गया है। – Powerlord

यह कथन किसी भी हैशकोड कार्यान्वयन का उपयोग करने की अनुमति देता है और यह भी मानचित्र को आकार बदलने के लिए अनुमति देता है। तो यह एक विशेषता है और इस संदर्भ में कोई समस्या नहीं है? – volley

Trove4j में मेरी सुविधा है और वे इसे हैशिंग रणनीतियां कहते हैं।

उनके मानचित्र में विभिन्न सीमाओं के साथ कार्यान्वयन है और इस प्रकार अलग-अलग आवश्यकताएं हैं, इसलिए इसका अर्थ यह नहीं है कि जावा के "मूल" हैश मैप के लिए कार्यान्वयन संभव होगा।

स्रोत

2009-12-09 20:42:35 volley

नोट: जैसा कि अन्य सभी उत्तरों में उल्लेख किया गया है, हैशमैप्स के पास कोई स्पष्ट आदेश नहीं है। वे केवल "समानता" को पहचानते हैं। हैश-आधारित डेटा संरचना से ऑर्डर प्राप्त करना व्यर्थ है, क्योंकि प्रत्येक ऑब्जेक्ट हैश में बदल जाता है - अनिवार्य रूप से एक यादृच्छिक संख्या।

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

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

एक साधारण कार्यान्वयन:

public class LowerStringWrapper { 
    public LowerStringWrapper(String s) { 
     this.s = s; 
     this.lowerString = s.toLowerString(); 
    } 

    // getter methods omitted 

    // Rely on the hashing of String, as we know it to be good. 
    public int hashCode() { return lowerString.hashCode(); } 

    // We overrode hashCode, so we MUST also override equals. It is required 
    // that if a.equals(b), then a.hashCode() == b.hashCode(), so we must 
    // restore that invariant. 
    public boolean equals(Object obj) { 
     if (obj instanceof LowerStringWrapper) { 
      return lowerString.equals(((LowerStringWrapper)obj).lowerString; 
     } else { 
      return lowerString.equals(obj); 
     } 
    } 

    private String s; 
    private String lowerString; 
}

स्रोत

2008-10-17 23:09:31 hazzen

नेट और IEquatable (एक प्रकार है जो अपने आप में एक और उदाहरण के लिए तुलना कर सकते हैं के लिए) (एक प्रकार है जो दो वस्तुओं की तुलना कर सकते हैं के लिए) IEqualityComparer के माध्यम से इस है।

वास्तव में, मेरा मानना है कि यह java.lang.Object या System.Object में समानता और हैशकोड को परिभाषित करने की गलती थी। विशेष रूप से समानता को ऐसे तरीके से परिभाषित करना कठिन होता है जो विरासत के साथ समझ में आता है। मैं इस बारे में ब्लॉग करने का अर्थ रखता हूं ...

लेकिन हां, मूल रूप से विचार ध्वनि है।

स्रोत

2008-10-17 23:40:48

और यह इस अवधारणा के लिए जिम्मेदार है कि किसी दिए गए प्रकार के लिए समानता की एक से अधिक अवधारणा हो सकती है। –

अच्छा सवाल, जॉश ब्लोच से पूछें। मैंने जावा 7 में आरएफई के रूप में उस अवधारणा को प्रस्तुत किया, लेकिन इसे छोड़ दिया गया, मेरा मानना है कि कारण कुछ प्रदर्शन से संबंधित था। मैं सहमत हूं, हालांकि, किया जाना चाहिए था।

स्रोत

2008-10-18 01:35:09

हम्म। शायद ऐसा इसलिए है क्योंकि आप गणना किए गए हैश कोड को कैश करने का अवसर याद करते हैं .. – volley

मुझे संदेह है कि ऐसा नहीं किया गया है क्योंकि यह हैशकोड कैशिंग को रोक देगा?

मैंने एक सामान्य नक्शा समाधान बनाने का प्रयास किया जहां सभी चाबियाँ चुपचाप लपेटी गईं। यह पता चला कि रैपर को लपेटा हुआ ऑब्जेक्ट, कैश हैशकोड और समानता-जांच के लिए जिम्मेदार कॉलबैक इंटरफ़ेस का संदर्भ रखना होगा। यह स्पष्ट रूप से एक रैपर वर्ग का उपयोग करने के रूप में उतना कुशल नहीं है, जहां आपको मूल कुंजी और एक और ऑब्जेक्ट को कैश करना होगा (हज़ेंस उत्तर देखें)।

(मैं जेनरिक से संबंधित एक समस्या में भी उछल गया; गेट-विधि ऑब्जेक्ट को इनपुट के रूप में स्वीकार करता है, इसलिए हैशिंग के लिए ज़िम्मेदार कॉलबैक इंटरफेस को एक अतिरिक्त उदाहरण देना होगा। या तो, या मैप क्लास होगा इसकी चाबियों की कक्षा जानने के लिए।)

स्रोत

2008-10-18 15:43:56 volley

यह एक दिलचस्प विचार है, लेकिन यह प्रदर्शन के लिए बिल्कुल भयानक है। इसका कारण idea of a hashtable के लिए काफी मौलिक है: ऑर्डरिंग पर भरोसा नहीं किया जा सकता है। हैशटेबल्स बहुत तेज हैं (constant time) जिस तरीके से वे तालिका में इंडेक्स तत्वों को सूचीबद्ध करते हैं: उस तत्व के लिए छद्म-अद्वितीय पूर्णांक हैश की गणना करके और उस स्थान को उस सरणी में एक्सेस करना। यह सचमुच स्मृति में एक स्थान की गणना कर रहा है और तत्व को सीधे संग्रहित कर रहा है।

यह एक संतुलित बाइनरी खोज पेड़ (TreeMap) के साथ विरोधाभास करता है जो रूट पर शुरू होना चाहिए और लुकअप की आवश्यकता होने पर हर बार वांछित नोड पर काम करना चाहिए। विकिपीडिया में कुछ more in-depth analysis है। संक्षेप में, एक पेड़ मानचित्र की दक्षता एक सतत क्रम पर निर्भर है, इस प्रकार तत्वों का क्रम अनुमानित और सभ्य है। हालांकि, "आपके गंतव्य के विपरीत" दृष्टिकोण द्वारा लगाए गए प्रदर्शन हिट के कारण, बीएसटी केवल ओ (लॉग (एन)) प्रदर्शन प्रदान करने में सक्षम हैं। बड़े मानचित्रों के लिए, यह एक महत्वपूर्ण प्रदर्शन हिट हो सकता है।

हैशटेबल पर एक सतत क्रम लगाने के लिए संभव है, लेकिन ऐसा करने के लिए LinkedHashMap जैसी तकनीकों का उपयोग करना और मैन्युअल रूप से ऑर्डरिंग को बनाए रखना शामिल है। वैकल्पिक रूप से, दो अलग-अलग डेटा संरचनाओं को आंतरिक रूप से बनाए रखा जा सकता है: एक हैशटेबल और एक पेड़। तालिका को लुकअप के लिए इस्तेमाल किया जा सकता है, जबकि पेड़ को पुनरावृत्ति के लिए इस्तेमाल किया जा सकता है। पाठ्यक्रम की समस्या यह है कि यह आवश्यक स्मृति को दोगुनी से अधिक उपयोग करता है। इसके अलावा, सम्मिलन पेड़ के जितना तेज़ होते हैं: ओ (लॉग (एन))। समवर्ती चालें इसे थोड़ा नीचे ला सकती हैं, लेकिन यह एक विश्वसनीय प्रदर्शन अनुकूलन नहीं है।

संक्षेप में, आपका विचार लगता है वास्तव में अच्छा है, लेकिन यदि आप वास्तव में इसे लागू करने का प्रयास करते हैं, तो आप देखेंगे कि ऐसा करने के लिए बड़े पैमाने पर प्रदर्शन सीमाएं लागू होंगी। अंतिम निर्णय (और दशकों से रहा है): यदि आपको प्रदर्शन की आवश्यकता है, तो हैशटेबल का उपयोग करें; अगर आपको आदेश देने की आवश्यकता है और खराब प्रदर्शन के साथ रह सकते हैं, तो एक संतुलित बाइनरी खोज पेड़ का उपयोग करें। मुझे डर है कि एक या दूसरे की कुछ गारंटी खोने के बिना वास्तव में दो संरचनाओं को संयोजित नहीं किया गया है।

स्रोत

2008-10-18 16:26:48

मुझे नहीं लगता कि आपके उत्तर में प्रश्न के साथ बहुत कुछ करना है। वॉली सिर्फ हैशटेबल का उपयोग करना चाहता है जहां हैश फ़ंक्शन उपयोगकर्ता-निर्दिष्ट है, डिफ़ॉल्ट ऑब्जेक्ट.hashCode() के बजाय। –

नहीं, मुझे लगता है कि वह इससे थोड़ा अधिक चाहता है। उनके प्रस्तावित "समाधान" को वैकल्पिक हैश कोड का उपयोग करके ऑर्डर देना है, लेकिन यह काम नहीं करेगा (सीमित डोमेन में हैशिंग)। हैशटेबल को ऑर्डर करने के लिए, कुछ सहायक संरचना की आवश्यकता है। –

हम्म वास्तव में मुझे लगता है कि एडम सही है; ध्यान दें कि मेरे द्वारा सुझाए गए इंटरफ़ेस में हैश की गणना करने के लिए एक विधि है और यह जांचने के लिए एक विधि है कि दो ऑब्जेक्ट बराबर हैं या नहीं। आदेश वहाँ नहीं है! तुलनात्मक को एक समानता के रूप में वर्णित किया गया है। (वैसे, डार्विनियन लोगो, डैनियल!) – volley

com.google.common.collect.CustomConcurrentHashMap में ऐसी सुविधा है, दुर्भाग्य से, Equivalence (उनके Hasharator) को सेट करने का कोई सार्वजनिक तरीका नहीं है।हो सकता है कि वे अभी तक इसके साथ नहीं किए गए हैं, हो सकता है कि वे इस सुविधा को पर्याप्त उपयोगी न मानें। guava mailing list पर पूछें।

मुझे आश्चर्य है कि यह अभी तक क्यों नहीं हुआ है, क्योंकि यह दो साल पहले इस talk में उल्लेख किया गया था।

स्रोत

2011-04-18 10:54:45 maaartinus

आपके लिए थोड़ा देर हो चुकी है, लेकिन भविष्य के आगंतुकों के लिए, यह जानना उचित हो सकता है कि कॉमन्स-संग्रह में AbstractHashedMap (3.2.1 में और 4.0 में जेनेरिक के साथ) है। आप अपने वांछित व्यवहार प्राप्त करने के लिए इन संरक्षित तरीकों ओवरराइड कर सकते हैं: के

protected int hash(Object key) { ... } 
protected boolean isEqualKey(Object key1, Object key2) { ... } 
protected boolean isEqualValue(Object value1, Object value2) { ... } 
protected HashEntry createEntry(
    HashEntry next, int hashCode, Object key, Object value) { ... }

एक उदाहरण कार्यान्वयन इस तरह के एक विकल्प के HashedMap है कॉमन्स-संग्रह 'खुद IdentityMap (केवल अप करने के लिए 3.2.1 जावा के रूप में its own 1.4 के बाद से है)।

यह Map उदाहरण के लिए बाहरी "Hasharator" प्रदान करने जितना शक्तिशाली नहीं है। आपको हर हैशिंग रणनीति (रचना बनाम विरासत वापस हड़ताली ...) के लिए एक नया नक्शा वर्ग लागू करना होगा। लेकिन यह अभी भी जानना अच्छा है।

स्रोत

2013-11-17 12:43:03

प्लसऑन। हो सकता है कि आप उस लिंक को [AbstractHashedMap] (http://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/map/AbstractHashedMap.html) पर इंगित करना चाहें वी 4 के लिए जो अंत में जेनेरिक है। – Nicolai

@ निकोलई पैरालॉग: इस उत्तर को संपादित करने के लिए स्वतंत्र महसूस करें :) –

@ निकोलई पैरालॉग: पवित्र ... मुझे 'java.util.IdentityHashMap' के बारे में पता नहीं था! टीआईएल ... –

HashingStrategy वह अवधारणा है जिसे आप ढूंढ रहे हैं। यह एक रणनीति इंटरफेस है जो आपको बराबर और हैशकोड के कस्टम कार्यान्वयन को परिभाषित करने की अनुमति देता है।

public interface HashingStrategy<E> 
{ 
    int computeHashCode(E object); 
    boolean equals(E object1, E object2); 
}

आप HashSet या HashMap में बनाया के साथ एक HashingStrategy उपयोग नहीं कर सकते। GS Collections में java.util.Set शामिल है जिसे UnifiedSetWithHashingStrategy कहा जाता है और एक java.util.Map को UnifiedMapWithHashingStrategy कहा जाता है।

चलिए एक उदाहरण देखें।

public class Data 
{ 
    private final int id; 

    public Data(int id) 
    { 
     this.id = id; 
    } 

    public int getId() 
    { 
     return id; 
    } 

    // No equals or hashcode 
}

यहां बताया गया है कि आप UnifiedSetWithHashingStrategy कैसे सेट कर सकते हैं और इसका उपयोग कर सकते हैं।

java.util.Set<Data> set = 
    new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(Data::getId)); 
Assert.assertTrue(set.add(new Data(1))); 

// contains returns true even without hashcode and equals 
Assert.assertTrue(set.contains(new Data(1))); 

// Second call to add() doesn't do anything and returns false 
Assert.assertFalse(set.add(new Data(1)));

क्यों न केवल Map का उपयोग करें? UnifiedSetWithHashingStrategyUnifiedMap की आधा मेमोरी का उपयोग करता है, और एक चौथाई HashMap की स्मृति का उपयोग करता है। और कभी-कभी आपके पास सुविधाजनक कुंजी नहीं होती है और उसे एक सिंथेटिक बनाने की ज़रूरत होती है, जैसे टुपल। यह और स्मृति बर्बाद कर सकते हैं।

हम लुकअप कैसे करते हैं? याद रखें कि सेट्स में है, लेकिन get() नहीं है। PoolSet के अतिरिक्त लागू करता है, इसलिए यह get() का एक रूप भी लागू करता है।

केस-असंवेदनशील स्ट्रिंग को संभालने के लिए यहां एक आसान तरीका है।

UnifiedSetWithHashingStrategy<String> set = 
    new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(String::toLowerCase)); 
set.add("ABC"); 
Assert.assertTrue(set.contains("ABC")); 
Assert.assertTrue(set.contains("abc")); 
Assert.assertFalse(set.contains("def")); 
Assert.assertEquals("ABC", set.get("aBc"));

यह एपीआई को दिखाता है, लेकिन यह उत्पादन के लिए उपयुक्त नहीं है। समस्या यह है कि हैशिंगस्ट्रेटी लगातार String.toLowerCase() पर प्रतिनिधि करता है जो कचरा स्ट्रिंग्स का एक गुच्छा बनाता है। यहां बताया गया है कि आप केस-असंवेदनशील स्ट्रिंग्स के लिए एक कुशल हैशिंग रणनीति कैसे बना सकते हैं।

public static final HashingStrategy<String> CASE_INSENSITIVE = 
    new HashingStrategy<String>() 
    { 
    @Override 
    public int computeHashCode(String string) 
    { 
     int hashCode = 0; 
     for (int i = 0; i < string.length(); i++) 
     { 
     hashCode = 31 * hashCode + Character.toLowerCase(string.charAt(i)); 
     } 
     return hashCode; 
    } 

    @Override 
    public boolean equals(String string1, String string2) 
    { 
     return string1.equalsIgnoreCase(string2); 
    } 
    };

नोट: मैं जी एस संग्रह पर एक डेवलपर हूँ।

स्रोत

2014-12-31 23:31:46

क्यों एक बाहरी इंटरफ़ेस हैशकोड/हैश मैप के बराबर प्रदान करने की अनुमति नहीं देता है?

उत्तर

संबंधित मुद्दे