अंग्रेजी शब्दों के लिए एक अच्छा हैश फ़ंक्शन क्या है?

Question

मेरे पास अंग्रेजी शब्दों की एक लंबी सूची है और मैं उन्हें हैश करना चाहता हूं। एक अच्छा हैशिंग समारोह क्या होगा? अब तक मेरा हैशिंग फ़ंक्शन अक्षरों के ASCII मानों को सारांशित करता है, फिर टेबल आकार को मॉड्यूल करें। मैं कुछ कुशल और सरल खोज रहा हूं।

Answer 1

अक्षरों को बस योग करने के लिए एक अच्छी रणनीति नहीं है क्योंकि क्रमपरिवर्तन एक ही परिणाम देता है।

यह एक (djb2) काफी लोकप्रिय है और ASCII तारों के साथ अच्छी तरह से काम करता है।

unsigned long hashstring(unsigned char *str) 
{ 
    unsigned long hash = 5381; 
    int c; 

    while (c = *str++) 
     hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ 

    return hash; 
} 

आप और अधिक विकल्प और कुछ कार्यक्षमता उपायों की जरूरत है, here पढ़ें।

जोड़ा गया: ये सामान्य हैशिंग काम करता है, जहां इनपुट डोमेन पहले से ज्ञात नहीं है कर रहे हैं (शायद कुछ बहुत ही सामान्य मान्यताओं को छोड़कर: जैसे ascii इनपुट के साथ थोड़ा बेहतर ऊपर काम करता है) है, जो सबसे आम परिदृश्य है । यदि आपके पास एक ज्ञात प्रतिबंधित डोमेन है (इनपुट का सेट निश्चित है) तो आप बेहतर कर सकते हैं, Fionn का उत्तर देखें।

Answer 2

हो सकता है कि कुछ इस तरह आप में मदद मिलेगी: http://www.gnu.org/s/gperf/

यह इनपुट डोमेन के लिए एक अनुकूलित हैशिंग समारोह उत्पन्न करता है।

Answer 3

यदि आपको इसकी आवश्यकता नहीं है तो क्रिप्टोग्राफ़िक रूप से सुरक्षित हो, मैं मुर्मूर हैश का सुझाव दूंगा। यह बेहद तेज़ है और इसमें उच्च प्रसार है। प्रयोग करने में आसान।

http://en.wikipedia.org/wiki/MurmurHash

http://code.google.com/p/smhasher/wiki/MurmurHash3

आप एक क्रिप्टोग्राफी द्वारा सुरक्षित हैश की जरूरत है, तो मैं OpenSSL के माध्यम से SHA1 सुझाव देते हैं।

http://www.openssl.org/docs/crypto/sha.html

Answer 4

एक थोड़ी देर हो चुकी है, लेकिन यहां से नीचे 64-बिट संस्करण के लिए एक बहुत ही कम टक्कर दर के साथ एक हैशिंग समारोह है, और ~ लगभग ~ 32-बिट संस्करण के लिए अच्छा के रूप में:

uint64_t slash_hash(const char *s) 
//uint32_t slash_hash(const char *s) 
{ 
    union { uint64_t h; uint8_t u[8]; }; 
    int i=0; h=strlen(s); 
    while (*s) { u[i%8] += *s + i + (*s >> ((h/(i+1)) % 5)); s++; i++; } 
    return h; //64-bit 
    //return (h+(h>>32)); //32-bit 
} 

हैश-संख्या भी संभव सीमा से बहुत समान रूप से फैली हुई है, जिसमें कोई क्लंपिंग नहीं है जिसे मैं पहचान सकता हूं - यह केवल यादृच्छिक तारों का उपयोग करके चेक किया गया था।
[संपादित करें]
64-बिट में 0 टकराव और 32-बिट में 1 टकराव के साथ लिबर ऑफिस डिक्शनरी/थिसॉरस शब्दों (अंग्रेज़ी और फ़्रेंच - 97000 से अधिक शब्द और संरचनाओं) के साथ संयुक्त स्थानीय टेक्स्ट-फाइलों से निकाले गए शब्दों से निकाले गए शब्दों के खिलाफ भी परीक्षण किया गया है:)

(इसके अलावा FNV1A_Hash_Yorikke, djb2 और MurmurHash2 एक ही सेट पर साथ तुलना में: Yorikke & djb2 अच्छा प्रदर्शन नहीं किया, slash_hash थोड़ा बेहतर सभी परीक्षणों में http किया MurmurHash2 से)