java - हैश मैप कुंजी के रूप में केस असंवेदनशील स्ट्रिंग




dictionary case-insensitive (8)

इस वजह से, मैं हर घटना के लिए CaseInsensitiveString का एक नया ऑब्जेक्ट बना रहा हूं। तो, यह प्रदर्शन मारा जा सकता है।

नए ऑब्जेक्ट्स को लुकअप करने से पहले लपेटने या कम मामले में कुंजी को कनवर्ट करना। अपना खुद का java.util.Map लिखना इस से बचने का एकमात्र तरीका है। यह बहुत कठिन नहीं है, और आईएमओ इसके लायक है। मैंने कुछ हैश फ़ंक्शन को बहुत अच्छी तरह से काम करने के लिए पाया, कुछ सौ चाबियाँ तक।

static int ciHashCode(String string)
{
    // length and the low 5 bits of hashCode() are case insensitive
    return (string.hashCode() & 0x1f)*33 + string.length();
}

मैं निम्नलिखित कारणों से हैश मैप कुंजी के रूप में केस असंवेदनशील स्ट्रिंग का उपयोग करना चाहता हूं।

  • प्रारंभिकरण के दौरान, मेरा प्रोग्राम उपयोगकर्ता परिभाषित स्ट्रिंग के साथ हैश मैप बनाता है
  • किसी ईवेंट को संसाधित करते समय (मेरे मामले में नेटवर्क यातायात), मुझे एक अलग मामले में स्ट्रिंग प्राप्त हो सकती है, लेकिन मुझे ट्रैफ़िक से प्राप्त होने वाले मामले को अनदेखा करके <key, value> हैश मैप से ढूंढने में सक्षम होना चाहिए।

मैंने इस दृष्टिकोण का पालन किया है

CaseInsensitiveString.java

    public final class CaseInsensitiveString {
            private String s;

            public CaseInsensitiveString(String s) {
                            if (s == null)
                            throw new NullPointerException();
                            this.s = s;
            }

            public boolean equals(Object o) {
                            return o instanceof CaseInsensitiveString &&
                            ((CaseInsensitiveString)o).s.equalsIgnoreCase(s);
            }

            private volatile int hashCode = 0;

            public int hashCode() {
                            if (hashCode == 0)
                            hashCode = s.toUpperCase().hashCode();

                            return hashCode;
            }

            public String toString() {
                            return s;
            }
    }

LookupCode.java

    node = nodeMap.get(new CaseInsensitiveString(stringFromEvent.toString()));

इस वजह से, मैं हर घटना के लिए CaseInsensitiveString का एक नया ऑब्जेक्ट बना रहा हूं। तो, यह प्रदर्शन मारा जा सकता है।

क्या इस मुद्दे को हल करने का कोई और तरीका है?


अन्य उत्तरों के आधार पर, मूल रूप से दो दृष्टिकोण हैं: हैश HashMap या रैपिंग String उप HashMap । पहले व्यक्ति को थोड़ा और काम की आवश्यकता होती है। वास्तव में, यदि आप इसे सही तरीके से करना चाहते हैं, तो आपको लगभग सभी विधियों को ओवरराइड करना होगा ( containsKey, entrySet, get, put, putAll and remove )।

वैसे भी, यह एक समस्या है। यदि आप भविष्य की समस्याओं से बचना चाहते हैं, तो आपको String केस ऑपरेशंस में Locale निर्दिष्ट करना होगा। तो आप नए तरीके तैयार करेंगे ( get(String, Locale) , ...)। सब कुछ आसान और स्पष्ट लपेटना स्ट्रिंग है:

public final class CaseInsensitiveString {

    private final String s;

    public CaseInsensitiveString(String s, Locale locale) {
        this.s = s.toUpperCase(locale);
    }

    // equals, hashCode & toString, no need for memoizing hashCode
}

और अच्छी तरह से, प्रदर्शन पर आपकी चिंताओं के बारे में: समयपूर्व अनुकूलन सभी बुराई की जड़ है :)


एक दृष्टिकोण अपाचे कॉमन्स isEqualKeys क्लास का एक कस्टम उप-वर्ग बनाना है, hash ओवरराइड करना और केस असंवेदनशील हैशिंग और चाबियों की तुलना करने के लिए isEqualKeys विधियां हैं। (नोट - मैंने कभी यह कोशिश नहीं की है ...)

जब भी आपको मानचित्र लुकअप या अपडेट करने की आवश्यकता होती है तो यह नई वस्तुओं को बनाने के ऊपरी हिस्से से बचाता है। और सामान्य Map संचालन ओ (1) ... नियमित HashMap Map होना चाहिए।

और यदि आप उनके द्वारा किए गए कार्यान्वयन विकल्पों को स्वीकार करने के लिए तैयार हैं, तो Apache Commons CaseInsensitiveMap आपके लिए AbstractHashedMap को अनुकूलित / विशेषज्ञता का काम करता है।

लेकिन अगर ओ (लॉगएन) get और संचालन स्वीकार्य होते हैं, तो एक केस असंवेदनशील स्ट्रिंग तुलनित्र के साथ एक वृक्ष एक विकल्प है; उदाहरण के लिए String.CASE_INSENSITIVE_ORDER का उपयोग String.CASE_INSENSITIVE_ORDER

और यदि आप हर बार एक नया अस्थायी स्ट्रिंग ऑब्जेक्ट बनाने में कोई फर्क नहीं पड़ता है तो आप एक बार put या get , तो विशाल का जवाब ठीक है। (हालांकि, मुझे लगता है कि यदि आप ऐसा करते हैं तो आप कुंजी के मूल मामले को संरक्षित नहीं करेंगे ...)


एक मजबूत केस इन्सेंसिटिव मैप / केसइन्सेंसिटसेटसेट कार्यान्वयन के लिए, जावा-यूज ( https://github.com/jdereg/java-util ) देखें।

ये मानचित्र मानक ओ (1) लुकअप समय में प्रदर्शन करते हैं, जोड़े गए आइटमों का मामला बरकरार रखते हैं, putAll (), retainAll (), removeAll () को सभी मैप एपीआई का समर्थन करते हैं, और विषम वस्तुओं को कुंजी सेट में रखने की अनुमति देते हैं।

इसके अलावा, java.util.Set .keySet () और .entrySet () सम्मान केस असंवेदनशीलता द्वारा लौटाया गया है (कई कार्यान्वयन नहीं करते हैं)। अंत में, यदि आप पुनरावृत्ति करते समय कुंजी / एंट्री सेट से कुंजी प्राप्त करते हैं, तो आपको एक स्ट्रिंग बैक मिलता है, न कि केसइन्सेंसिव स्ट्रिंग रैपर क्लास।


जैसा कि Guido Garcia द्वारा उनके उत्तर में सुझाव दिया गया है :

import java.util.HashMap;

public class CaseInsensitiveMap extends HashMap<String, String> {

    @Override
    public String put(String key, String value) {
       return super.put(key.toLowerCase(), value);
    }

    // not @Override because that would require the key parameter to be of type Object
    public String get(String key) {
       return super.get(key.toLowerCase());
    }
}

या

http://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/map/CaseInsensitiveMap.html


मेरे मन में दो विकल्प आते हैं:

1) आप सीधे s.toUpperCase().hashCode(); उपयोग कर सकते हैं s.toUpperCase().hashCode(); Map की कुंजी के रूप में। 2) आप एक कस्टम तुलनाकर्ता के साथ एक TreeMap का उपयोग कर सकते हैं जो मामले को अनदेखा करता है।

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


सबक्लास HashMap और एक संस्करण बनाएं जो कम-मामले को कुंजी पर put और get (और शायद अन्य कुंजी उन्मुख तरीकों)।

या नई कक्षा में HashMap मैप को मिश्रित करें और मानचित्र पर सबकुछ प्रतिनिधि दें, लेकिन चाबियों का अनुवाद करें।

यदि आपको मूल कुंजी रखने की आवश्यकता है तो आप या तो दोहरी मानचित्र बनाए रख सकते हैं, या मूल कुंजी को मूल्य के साथ स्टोर कर सकते हैं।


हैशकोड को याद रखने के लिए स्ट्रिंग को "लपेटना" बेहतर नहीं होगा। सामान्य स्ट्रिंग क्लास हैशकोड () में पहली बार ओ (एन) है और फिर यह ओ (1) है क्योंकि इसे भविष्य के उपयोग के लिए रखा जाता है।

public class HashWrap {
    private final String value;
    private final int hash;

    public String get() {
        return value;
    }

    public HashWrap(String value) {
        this.value = value;
        String lc = value.toLowerCase();
        this.hash = lc.hashCode();
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o instanceof HashWrap) {
            HashWrap that = (HashWrap) o;
            return value.equalsIgnoreCase(that.value);
        } else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        return this.hash;
    }

    //might want to implement compare too if you want to use with SortedMaps/Sets.
}

यह आपको जावा में हैशटेबल के किसी भी कार्यान्वयन का उपयोग करने और ओ (1) हैकोड () के लिए उपयोग करने की अनुमति देगा।





case-insensitive