यहाँ स्ट्रिंग्स के लिए मेरा हैश फ़ंक्शन है

public class GoodHashFunctor implements HashFunctor {

    @Override
    public int hash(String item) {

        String binaryRepString = "";

        for(int i = 0; i < item.length(); i++){
            // Add the String version of the binary version of the integer  version of each character in item
            binaryRepString += Integer.toBinaryString((int)(item.charAt(i)));
        }


        long longVersion = Long.parseLong(binaryRepString, 2) % Integer.MAX_VALUE;


        return (int) longVersion;

    }

}

हालांकि, जब मैं बड़े स्ट्रिंग्स (लगभग 10-15 वर्ण) हैशिंग करने का प्रयास करता हूं, तो मुझे त्रुटियां मिल रही हैं क्योंकि जब यह पार्सलॉन्ग करने का प्रयास करता है, तो यह मर जाता है क्योंकि यह बहुत बड़ी संख्या है।

आप सभी को क्या लगता है कि मुझे क्या करना चाहिए? और मेरे प्रोफेसर ने कहा कि हम जावा के हैशकोड () का उपयोग नहीं कर सकते

मैंने एक ऐसी ही पोस्ट देखी जहां इस तरह हैश का सबसे अच्छा जवाब था:

int hash=7;

for (int i=0; i < strlen; i++) {
    hash = hash*31+charAt(i);
}

लेकिन क्या मैं उसी समस्या में नहीं पड़ूंगा? मुझे लगता है कि स्ट्रिंग्स को इस नए तरीके से तोड़ने में शायद बहुत अधिक समय लगेगा। मुझे नहीं पता मैं काफी उलझन में हूँ...

1
user114518 15 जुलाई 2011, 20:04
3
आप स्ट्रिंग के डिफ़ॉल्ट हैश एल्गो को क्यों नहीं देखते?
 – 
Amir Raminfar
15 जुलाई 2011, 20:11
1
@ सिल्वर: अपाचे कॉमन्स से हैशबिल्डर है। क्या यह आपके लिए पर्याप्त नहीं है?
 – 
Kowser
15 जुलाई 2011, 20:17
आह, धन्यवाद, मैंने सोचा था कि स्ट्रिंग का डिफ़ॉल्ट हैश एल्गो छिपा हुआ था (नोब गलती) तो यह एस [0] * 31 ^ (एन -1) + एस [1] * 31 ^ (एन -2) + ... + एस है [एन -1] इसके अलावा, कौसर, मैं हैशबिल्डर चीज देख रहा हूं, लेकिन इसे बिल्कुल समझ नहीं पा रहा हूं। लेकिन मुझे लगता है कि मैं सिर्फ डिफ़ॉल्ट को दोहराने की कोशिश करने जा रहा हूं। सभी को धन्यवाद!
 – 
user114518
15 जुलाई 2011, 20:24
मुझे यकीन नहीं है कि आप समझते हैं कि आपका कोड क्या कर रहा है। "abcdefgh" (बाइनरी 0x6162636465666768) जैसे स्ट्रिंग के लिए, binaryRepString में 0110000101100010011000110110010001100101 0110011001100111 का मान होगा, जिसे आप आधार 2 में long के रूप में पार्स करने का प्रयास करते हैं। यह 63 बिट्स है, जो एक long में फिट होगा। हालांकि, यदि आप स्ट्रिंग में एक और बाइट जोड़ते हैं, तो मध्यवर्ती मान अब 64 बिट से अधिक है और अब फिट नहीं बैठता है।
 – 
Jim Garrison
15 जुलाई 2011, 20:25
गैरीसन: हाँ, मैं समझ गया कि मुझे त्रुटि क्यों मिल रही है। मैंने पहले सोचा, अच्छी तरह से मैं क्या उपयोग कर सकता हूं जिसमें बड़ी संख्याएं हैं, और लंबी कहानी छोटी है, मुझे अंततः एक बेहतर तरीका मिला (डिफ़ॉल्ट हैश एल्गो) और अब दुनिया में सब ठीक है :)
 – 
user114518
15 जुलाई 2011, 20:33

2 जवाब

सबसे बढ़िया उत्तर

long में बदलने से पहले आपको प्रत्येक वर्ण को एक स्ट्रिंग (और वह भी बाइनरी रूप में) में बदलने की आवश्यकता क्यों है? क्यों न केवल एक long मान जिसमें आप char जोड़ते हैं?

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

संपादित करें: मैं समझता हूं कि आप उन्हें केवल सारांशित नहीं करना चाहते हैं क्योंकि विपर्यय सभी का हैश मान समान होगा। लेकिन मुझे लगता है कि आप पहले से ही जानते हैं कि इससे कैसे बचा जाए। ध्यान दें कि कैसे बिट्स को जोड़कर, आप मूल रूप से बिट्स को कुछ पदों से स्थानांतरित करने के बाद एक मूल्य में जोड़ रहे हैं। यानी "10101"+"10001" 1010100000+10001 - 21<<5+17 के समान है।

स्ट्रिंग में अपनी स्थिति के अनुपात में प्रत्येक वर्ण को स्थानांतरित करके, हैश में जोड़ा गया मान वर्ण के मान और स्थिति दोनों पर निर्भर करता है। साथ ही, देखें कि स्केलिंग के बजाय केवल गुणा करके समान प्रभाव प्राप्त किया जा सकता है।

एक और ध्यान देने योग्य बात यह है कि एक long में केवल 64 बिट होते हैं। इसके अतिप्रवाह शुरू होने से पहले आप इसमें केवल इतने char s पैक कर सकते हैं। तो सबसे व्यावहारिक हैश फ़ंक्शन मान मॉड्यूलो को कुछ संख्या में लेते हैं। बेशक इसका मतलब है कि असीमित संख्या में इनपुट स्ट्रिंग्स के लिए सीमित संख्या में संभावित हैश मान हैं। टकराव अपरिहार्य हैं, लेकिन आपके शिफ्ट/गुणक और मॉड के लिए अच्छी तरह से चुने गए मान टकराव की संख्या को कम कर सकते हैं।

0
MAK 15 जुलाई 2011, 20:40
मैं वर्णों के लंबे मानों का योग नहीं करना चाहता क्योंकि तब विपर्यय में समान हैशकोड होगा
 – 
user114518
15 जुलाई 2011, 20:13
अहह्ह्ह, यह समझ में आता है। मुझे लगता है कि मैं कोशिश करने जा रहा हूं और हालांकि डिफ़ॉल्ट अहंकार करता हूं।
 – 
user114518
15 जुलाई 2011, 20:34

एक अच्छा हैश-फ़ंक्शन क्या है, इस पर निर्भर करता है कि आप अच्छे से क्या मतलब रखते हैं। मुझे पता है कि यह अटपटा लगता है लेकिन यह इतना सच है। यह पहचानने के लिए कि आपके विशिष्ट समस्या-डोमेन के लिए कौन सा हैश-फ़ंक्शन सर्वोत्तम है, आपको निर्दिष्ट करना होगा:

  • इनपुट कितना समय है

  • इनपुट में कौन से अक्षर हैं (एक निश्चित वर्णमाला में अक्षर, या आनुवंशिक अनुक्रमों में केवल 4 संभावित अक्षर, और यदि आप वास्तव में एक अच्छा हैश फ़ंक्शन चाहते हैं तो आपको प्रत्येक अक्षर की अपेक्षित संभावना निर्दिष्ट करने की भी आवश्यकता है)

  • आप किस तरह से स्ट्रिंग्स को अलग करना चाहते हैं (एमएके के जवाब पर आपकी टिप्पणी से पता चलता है कि आप एक ही स्ट्रिंग के क्रमपरिवर्तन के लिए हैश अलग होना चाहते हैं। तो आपका += उम्मीदवार नहीं है, लेकिन कुछ कार्यों के लिए नीचे दिया गया लिंक देखें जो इस आवश्यकता को पूरा करते हैं)

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

एक साइड-नोट के रूप में: स्पष्ट रूप से आपका += एक लंबे समय में केवल छोटे तारों के लिए काम करता है। लेकिन एक अलग हैश-फ़ंक्शन के साथ भी आपको प्रत्येक संभावित स्ट्रिंग के लिए अद्वितीय हैश मान नहीं मिलते हैं जिसे आप 64-बिट लॉन्ग (जावा) में फिट कर सकते हैं: आप केवल 2 ^ 64 स्ट्रिंग्स को परफेक्ट हैश के साथ भी अलग कर सकते हैं। मजबूत> समारोह। सामान्य तौर पर यदि आपके पास एक हैशटेबल है जो aKey->anObject को मैप करता है तो आप अभी भी मूल कुंजी को स्टोर करते हैं (न कि केवल हैश-वैल्यू जो यह बकेट दर्शाता है) ताकि आप अनुरोधित कुंजी स्ट्रिंग के साथ इसकी तुलना कर सकें।

आपकी आवश्यकताओं के आधार पर आप क्रिप्टोग्राफ़िक हैश-फ़ंक्शंस के विषय पर एक नज़र डालना चाहेंगे ताकि यह तय किया जा सके कि वे वही हैं जो आप चाहते हैं। हालाँकि पहले बहुत अच्छी विकिपीडिया-प्रविष्टि पर एक नज़र डालें जिसमें कुछ अच्छे हैश-फ़ंक्शंस सूचीबद्ध हैं और इससे भी महत्वपूर्ण बात यह है कि जिन स्थितियों के लिए वे अच्छे हैं: http://en.wikipedia.org/wiki/Hash_function

0
Bernd Elkemann 15 जुलाई 2011, 20:36