स्ट्रिंग

Question

के लिए हैश फ़ंक्शन वर्तमान में हम अपनी कक्षा में हैश फ़ंक्शन से निपट रहे हैं। हमारे प्रशिक्षक ने हमें हमारे कोड में इस्तेमाल किए गए दो की तुलना करने के लिए इंटरनेट पर हैश फ़ंक्शन के लिए कहा है।

पहले एक:

int HashTable::hash (string word) 
// POST: the index of entry is returned 
{  int sum = 0; 
     for (int k = 0; k < word.length(); k++) 
      sum = sum + int(word[k]); 
     return sum % SIZE; 
} 

दूसरा:

int HashTable::hash (string word) 
{ 
    int seed = 131; 
    unsigned long hash = 0; 
    for(int i = 0; i < word.length(); i++) 
    { 
     hash = (hash * seed) + word[i]; 
    } 
    return hash % SIZE; 
} 

कहाँ आकार 501 (हैश तालिका का आकार) है और इनपुट 20,000 शब्दों का एक पाठ फ़ाइल से आ रहा है।

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

यदि मेरा तर्क ध्वनि है, तो क्या किसी के पास एक अच्छा उदाहरण है या एक संसाधन है जिसमें एक अलग हैश फ़ंक्शन दिखा रहा है जिसमें स्ट्रिंग शामिल है? या यहां तक ​​कि अपने स्वयं के कुशल हैश समारोह लिखने की प्रक्रिया भी।

Answer 1

सबसे पहले, कि ज्यादा नहीं यह आम तौर पर करता है बात व्यवहार में। अधिकांश हैश फ़ंक्शन "पर्याप्त अच्छे" हैं।

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

आपका दूसरा हैश फ़ंक्शन थोड़ा बेहतर हो सकता है, क्योंकि संभवतः स्ट्रिंग "ba" स्ट्रिंग "ab" को अलग करना चाहिए। दूसरी तरफ, यह पहले हैश फ़ंक्शन से शायद कम तेज़ है। यह आपके आवेदन के लिए प्रासंगिक हो सकता है, या नहीं हो सकता है।

मुझे लगता है कि जीनोम तारों के लिए उपयोग किए गए हैश फ़ंक्शन टेलीफोन डेटाबेस में हैश परिवार के नामों के उपयोग से काफी अलग हैं। अंग्रेजी या फ्रेंच शब्दों की तुलना में शायद कुछ स्ट्रिंग हैश फ़ंक्शन जर्मन के लिए बेहतर उपयुक्त हैं।

कई सॉफ़्टवेयर लाइब्रेरी आपको पर्याप्त हैश फ़ंक्शन प्रदान करते हैं, उदा। क्यूटी में qhash है, और सी ++ 11 std::hash<functional> में है, ग्लिब में सी hash functions सी है, और POCO में कुछ hash फ़ंक्शन है।

मुझे प्रायः प्राइम्स से जुड़े हैंशिंग फ़ंक्शन (Bézout's identity देखें) और xor, उदा।

#define A 54059 /* a prime */ 
#define B 76963 /* another prime */ 
#define C 86969 /* yet another prime */ 
#define FIRSTH 37 /* also prime */ 
unsigned hash_str(const char* s) 
{ 
    unsigned h = FIRSTH; 
    while (*s) { 
    h = (h * A)^(s[0] * B); 
    s++; 
    } 
    return h; // or return h % C; 
} 

लेकिन मैं एक हैश विशेषज्ञ होने का दावा नहीं करता हूं। बेशक, A, B, C, FIRSTH के मान प्राथमिक रूप से प्राइम होना चाहिए, लेकिन आप अन्य प्रमुख संख्याओं को चुन सकते थे।

कुछ हैश फ़ंक्शन हो सकता है, यह महसूस करने के लिए कुछ MD5 कार्यान्वयन को देखें।

एल्गोरिदमिक्स पर सबसे अच्छी किताबें कम से कम एक पूरा अध्याय है जो हैशिंग को समर्पित है। hash function & hash table पर विकिपीज़ से शुरू करें।

Answer 2

जावा के String implements hashCode like this:

public int hashCode() 

Returns a hash code for this string. The hash code for a String object is computed as 

    s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and^indicates exponentiation. (The hash value of the empty string is zero.) 

तो कुछ इस तरह:

int HashTable::hash (string word) { 
    int result = 0; 
    for(size_t i = 0; i < word.length(); ++i) { 
     result += word[i] * pow(31, i); 
    } 
    return result; 
} 

Answer 3

- इन दिनों जाने का रास्ता -

उपयोग SipHash। अपनी सुरक्षा के लिए।

- पुराने और खतरनाक -

unsigned int RSHash(const std::string& str) 
{ 
    unsigned int b = 378551; 
    unsigned int a = 63689; 
    unsigned int hash = 0; 

    for(std::size_t i = 0; i < str.length(); i++) 
    { 
     hash = hash * a + str[i]; 
     a = a * b; 
    } 

    return (hash & 0x7FFFFFFF); 
} 

unsigned int JSHash(const std::string& str) 
{ 
     unsigned int hash = 1315423911; 

     for(std::size_t i = 0; i < str.length(); i++) 
     { 
      hash ^= ((hash << 5) + str[i] + (hash >> 2)); 
     } 

     return (hash & 0x7FFFFFFF); 
} 

"सामान्य प्रयोजन हैश फंक्शन"

एल्गोरिथम उपयोग के लिए

Answer 4

हैश कार्यों आम तौर पर 2 लक्ष्य के लिए गूगल से पूछो, पहले वे तेजी से होना है, दूसरा उन्हें संभावित संख्याओं में मूल्यों को समान रूप से विचलित करना होगा। हैश फ़ंक्शन को एक ही इनपुट मान के लिए समान संख्या देने की आवश्यकता है।

अगर आपके मानों को स्ट्रिंग्स कर रहे हैं, यहाँ बुरा हैश फंक्शन के लिए कुछ उदाहरण हैं:

1. string[0] - ASCII वर्ण AZ तरह से अधिक बार कर रहे हैं तो दूसरों
2. string.lengh() - सबसे संभावित मान 1
है

अच्छा हैश फ़ंक्शन गणना समय को न्यूनतम रखते हुए इनपुट के हर बिट का उपयोग करने का प्रयास करता है। अगर आपको केवल कुछ हैश कोड की आवश्यकता है, तो बाइट्स को प्राइम संख्याओं से गुणा करने का प्रयास करें, और उन्हें योग करें।

Answer 5

उपयोग boost::hash

#include <boost\functional\hash.hpp> 

...

std::string a = "ABCDE"; 
size_t b = boost::hash_value(a);