java - स्ट्रिंग में जावा का हैशकोड() एक गुणक के रूप में 31 का उपयोग क्यों करता है?




string algorithm (7)

(ज्यादातर) पुराने प्रोसेसर, 31 से गुणा करके अपेक्षाकृत सस्ते हो सकते हैं। उदाहरण के लिए, एआरएम पर, यह केवल एक ही निर्देश है:

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

अधिकांश अन्य प्रोसेसर को एक अलग शिफ्ट की आवश्यकता होगी और निर्देश घटाएं। हालांकि, यदि आपका गुणक धीमा है तो यह अभी भी एक जीत है। आधुनिक प्रोसेसर में तेजी से गुणक होते हैं, इसलिए इससे कोई फर्क नहीं पड़ता है, जब तक कि 32 सही तरफ जाता है।

यह एक महान हैश एल्गोरिदम नहीं है, लेकिन यह 1.0 कोड से काफी अच्छा और बेहतर है (और 1.0 spec से बहुत बेहतर है!)।

जावा में, String ऑब्जेक्ट के लिए हैश कोड की गणना की जाती है

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

int अंकगणितीय का उपयोग करके, जहां s[i] स्ट्रिंग का i वां चरित्र है, n स्ट्रिंग की लंबाई है, और ^ एक्सपोनेंटिएशन इंगित करता है।

गुणक के रूप में 31 का उपयोग क्यों किया जाता है?

मैं समझता हूं कि गुणक अपेक्षाकृत बड़े प्रधान संख्या होना चाहिए। तो क्यों 29, या 37, या यहां तक ​​कि 97 नहीं?


असल में, 37 बहुत अच्छी तरह से काम करेगा! z: = 37 * x को y := x + 8 * x; z := x + 4 * y रूप में गणना की जा सकती है y := x + 8 * x; z := x + 4 * y y := x + 8 * x; z := x + 4 * y । दोनों कदम एक एलआईए x86 निर्देशों के अनुरूप हैं, इसलिए यह बेहद तेज़ है।

वास्तव में, यहां तक ​​कि बड़े-बड़े प्राइम 73 के साथ गुणा को एक ही गति से y := x + 8 * x; z := x + 8 * y सेट करके किया जा सकता है y := x + 8 * x; z := x + 8 * y y := x + 8 * x; z := x + 8 * y

73 या 37 (31 के बजाए) का उपयोग करना बेहतर हो सकता है, क्योंकि यह घनत्व कोड की ओर जाता है: दो एलआईए निर्देश केवल 6 बाइट बनाम 7 बाइट्स लेते हैं + शिफ्ट + गुणा के लिए घटाना 31. एक संभावित चेतावनी यह है कि यहां इस्तेमाल किए गए 3-तर्क वाले एलआईए निर्देश इंटेल के सैंडी ब्रिज आर्किटेक्चर पर धीमे हो गए, जिसमें 3 चक्रों की वृद्धि हुई।

इसके अलावा, 73 शेल्डन कूपर का पसंदीदा नंबर है।


गुणा करके, बिट्स को बाईं ओर स्थानांतरित कर दिया जाता है। यह टकराव को कम करने, हैश कोड के उपलब्ध स्थान के अधिक उपयोग करता है।

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

अभिव्यक्ति n * 31 बराबर है (n << 5) - n


चूंकि गुड्रिच और तामसिया बताते हैं, यदि आप 31,000 से अधिक अंग्रेजी शब्द (यूनिक्स के दो प्रकारों में प्रदान की गई शब्द सूचियों के संघ के रूप में गठित) करते हैं, तो स्थिरांक 31, 33, 37, 3 9 और 41 का उपयोग 7 से कम टकराव का उत्पादन करेगा प्रत्येक मामले में। इसे जानना, यह आश्चर्य की बात नहीं है कि कई जावा कार्यान्वयन इन स्थिरांकों में से एक चुनते हैं।

संयोग से, जब मैंने यह प्रश्न देखा तो मैं "बहुपद हैश कोड" अनुभाग पढ़ने के बीच में था।

संपादित करें: यहां ~ 10 एमबी पीडीएफ पुस्तक का लिंक है जिसका मैं उपरोक्त संदर्भ दे रहा हूं। जावा में डेटा संरचनाओं और एल्गोरिदम के अनुभाग 10.2 हैश टेबल्स (पृष्ठ 413) देखें


नील कॉफ़ी explains कि पूर्वाग्रहों को दूर करने के तहत 31 का उपयोग क्यों किया जाता है।

मूल रूप से 31 का उपयोग करके आपको हैश फ़ंक्शन के लिए एक और भी सेट-बिट संभावना वितरण प्रदान करता है।


ब्लोच इसमें काफी नहीं जाता है, लेकिन जिस तर्क को मैंने हमेशा सुना / माना है वह यह है कि यह मूल बीजगणित है। हैश गुणा और मॉड्यूलस संचालन के लिए उबालते हैं, जिसका मतलब है कि आप कभी भी सामान्य कारकों के साथ संख्याओं का उपयोग नहीं करना चाहते हैं यदि आप इसकी मदद कर सकते हैं। दूसरे शब्दों में, अपेक्षाकृत प्रमुख संख्याएं उत्तर का वितरण भी प्रदान करती हैं।

हैश का उपयोग करने वाली संख्याएं आम तौर पर होती हैं:

  • डेटा प्रकार के मॉड्यूलस जिसे आपने इसे रखा है (2 ^ 32 या 2 ^ 64)
  • आपके हैशटेबल में बाल्टी गिनती का मॉड्यूलस (बदलता है। जावा में प्राइम होता था, अब 2 ^ एन)
  • अपने मिश्रण समारोह में एक जादू संख्या से गुणा या स्थानांतरित करें
  • इनपुट मूल्य

आप वास्तव में केवल इन मूल्यों में से कुछ को नियंत्रित करते हैं, इसलिए थोड़ी अतिरिक्त देखभाल की वजह है।


http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 , जहां यहोशू ब्लोच ने कारणों का वर्णन किया है कि क्यों विशेष (नया) String.hashCode() कार्यान्वयन चुना गया था

नीचे दी गई तालिका तीन डेटा सेट के लिए ऊपर वर्णित विभिन्न हैश फ़ंक्शंस के प्रदर्शन को सारांशित करती है:

1) मरियम-वेबस्टर के दूसरे इंटेल अनब्रिज्ड डिक्शनरी (311,141 स्ट्रिंग्स, औसत लंबाई 10 वर्ण) में प्रविष्टियों वाले सभी शब्द और वाक्यांश।

2) सभी तारों में / bin / , / usr / bin / , / usr / lib / , / usr / ucb / और / usr / openwin / bin / * (66,304 तार, औसत लंबाई 21 वर्ण)।

3) एक वेब क्रॉलर द्वारा एकत्र किए गए यूआरएल की एक सूची जो कल रात कई घंटों तक दौड़ गई (28,372 तार, औसत लंबाई 49 वर्ण)।

तालिका में दिखाया गया प्रदर्शन मीट्रिक हैश तालिका में सभी तत्वों पर "औसत श्रृंखला आकार" है (यानी, किसी तत्व को देखने के लिए कुंजी की तुलना की अपेक्षित मान)।

                          Webster's   Code Strings    URLs
                          ---------   ------------    ----
Current Java Fn.          1.2509      1.2738          13.2560
P(37)    [Java]           1.2508      1.2481          1.2454
P(65599) [Aho et al]      1.2490      1.2510          1.2450
P(31)    [K+R]            1.2500      1.2488          1.2425
P(33)    [Torek]          1.2500      1.2500          1.2453
Vo's Fn                   1.2487      1.2471          1.2462
WAIS Fn                   1.2497      1.2519          1.2452
Weinberger's Fn(MatPak)   6.5169      7.2142          30.6864
Weinberger's Fn(24)       1.3222      1.2791          1.9732
Weinberger's Fn(28)       1.2530      1.2506          1.2439

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

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

हंसी मजाक करना






hash