हैशकोड() में int से int को कैसे मैप करना चाहिए?

Question

मैं वस्तुओं है कि एक long क्षेत्र जिसका मान विशिष्ट, मेरे पूरे सिस्टम भर में एक विशेष वस्तु को दिखाता है बहुत एक GUID तरह की एक श्रृंखला है। तुलनात्मक रूप से इस आईडी का उपयोग करने के लिए मैंने Object.equals() को ओवर्रिडन किया है, क्योंकि मैं इसे ऑब्जेक्ट की प्रतियों के साथ काम करना चाहता हूं। अब मैं Object.hashCode() भी ओवरराइड करने के लिए, मूल रूप से मेरी long कुछ int को वापसी मान मानचित्रण जिसका अर्थ है चाहता हूँ।

अगर मैं सही ढंग hashCode के प्रयोजन समझ में आया, यह मुख्य रूप से हैश तालिकाओं में प्रयोग किया जाता है, तो एक समान वितरण वांछनीय होगा। इसका मतलब यह होगा कि id % 2^32 वापस लौटना पर्याप्त होगा। क्या यह सब कुछ है, या मुझे किसी और चीज के बारे में पता होना चाहिए?

Answer 1

जावा 8 जब से तुम

Long.hashCode(guid); 

उपयोग कर सकते हैं जावा के पुराने संस्करणों के लिए आप उपयोग कर सकते हैं निम्नलिखित:

Long.valueOf(guid).hashCode(); 

ध्यान दें कि यह समाधान ढेर के लिए एक नई वस्तु बनाता है, जबकि पहले नहीं (हालांकि यह संभावना है कि जावा ऑब्जेक्ट सृजन को दूर करता है ..)

दस्तावेज़ों को देखते हुए, दोनों तरीकों से केवल निम्नलिखित एल्गोरिदम का उपयोग करें:

(int)(this.longValue()^(this.longValue()>>>32)) 

ये सभ्य समाधान हैं क्योंकि वे जावा लाइब्रेरी का उपयोग करते हैं - पहले से परीक्षण किए गए किसी भी चीज़ का लाभ उठाने के लिए हमेशा बेहतर होता है।

Answer 2

आप सही ढंग से hashCode के प्रयोजन समझ लिया है। हां, एक समान वितरण वांछनीय है (हालांकि वास्तविक आवश्यकता नहीं है)।

मैं ((id >> 32)^id) सुझाव है।

ऊपर अभिव्यक्ति:

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

Answer 3

int result = (int)((longVal >> 32)^longVal); 

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

Answer 4

यह एक छोटी सी बात का एक सा है, तो आप पहले से ही Guava उपयोग कर रहा है नहीं कर रहे हैं, लेकिन अमरूद do this for you अच्छी तरह से कर सकते हैं:

public int hashCode() { 
    return Longs.hashCode(id); 
} 

है कि आप Long.valueOf(id).hashCode() के बराबर देता है:

return (int) (value^(value >>> 32)); 

साथ ही, यदि आपके पास हैशकोड का हिस्सा अन्य मूल्य या ऑब्जेक्ट्स थे, तो आप केवल

लिख सकते थे

longLong में ऑटोबॉक्साइड किया जाएगा ताकि आपको संपूर्ण हैशकोड के हिस्से के रूप में इसके लिए सही हैशकोड प्राप्त हो सके।

Answer 5

(l >> 32)^l ज्यादातर मामलों में एक अच्छा हैशकोड है; खासकर जब लंबे समय तक एक समान वितरण होता है।

चूंकि यह स्वीकार्य उत्तर था, इसलिए मैं अपनी कुछ टिप्पणियों को स्पष्ट करने के लिए इसे पोस्ट कर रहा हूं कि यह लंबे समय तक एक अच्छा हैशकोड नहीं है।

public class Point { 
    private final long coords; //x in high-bits, y in low 
    public int getX() { 
     return (int)(coords >> 32); 
    } 
    public int getY() { 
     return (int)coords; 
    } 
    public int hashCode() { 
     return (int)((coords >> 32)^(coords)); 
    } 
} 

यह काल्पनिक लग सकता है, लेकिन कभी कभी आप एक लंबे में पैक एकाधिक "फील्ड" है:

उदाहरण मैं दे दी है इस तरह एक प्वाइंट वर्ग था।

तो coords फ़ील्ड x के 32 बिट्स और 32 बिट्स वाई का प्रतिनिधित्व करता है। तो यह एक समस्या क्यों है? खैर, ऐसा नहीं है कि प्रत्येक एक्स और वाई को उनके संबंधित 32 बिट्स पर समान रूप से वितरित किया जाता है। लेकिन यह अभ्यास में असंभव है। अधिक संभावना है कि एक्स और वाई कुछ संख्या से बंधे हैं। आइए 1024 कहें क्योंकि यह 2^10 है। इसका मतलब है कि अधिक से अधिक प्रत्येक एक्स और वाई के निचले 10 बिट सेट कर रहे हैं:

00000000 00000000 000000XX XXXXXXXX 00000000 00000000 000000YY YYYYYYYY 

2^20 (1024 * 1024) संभव संयोजनों रहे हैं। लेकिन ऑपरेशन हैशकोड क्या कर रहा है?

00000000 00000000 000000XX XXXXXXXX 
^ 00000000 00000000 000000YY YYYYYYYY 
------------------------------------- 
= 00000000 00000000 000000?? ???????? 

पर सबसे 2^10 (1024) संभव hashCode मूल्यों के बाद से ही कम 10 बिट कभी शून्य के अलावा कुछ भी हो सकता हैं। हैश मानों का वास्तविक मूल्यों का अनुपात 1024:(1024*1024) या 1:1024 है। तो बल्ले से बाहर एक 1/1024 संभावना है कि दो संख्याओं में एक ही हैश है।

अब birthday problem से गणित लागू करके टकराव की संभावना की गणना करें। पी (एन) को संभावना है कि एन मानों के साथ कम से कम एक टकराव होगा। हम जानते हैं कि पी (1025+) = 1 क्योंकि केवल 1024 मान हैं।

p(n) = 1 - (n! * (1024 choose n))/1024^n 

यह निम्न करने के लिए बाहर काम करता है:

n: p(n) 
1: 0.00000 
2: 0.00098 
3: 0.00293 
4: 0.00585 
5: 0.00973 
6: 0.01457 
... 
38: 0.50096 
... 
79: 0.95444 
... 
148: 0.99999 

सिर्फ 38 आइटम के साथ

, वहाँ शायद एक टक्कर है। 148 वस्तुओं के साथ, 99.9 99% मौका (कम से कम एक) टक्कर है। 148 वस्तुओं के साथ, प्रत्येक आइटम में किसी अन्य आइटम के साथ टकराने का 7% मौका होता है। उचित हैशिंग फ़ंक्शन के साथ, डोमेन का ज्ञान लेते हुए, ये संख्या आसानी से 0

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

Answer 6

जावा 8 जेडीके में Long.hashCode(long) जोड़ता है।

निम्नलिखित कोड उच्च प्रदर्शन प्राप्त कर सकता है। यह कोड 64-बिट long के साथ कंप्यूटिंग के बजाय 32-बिट int की गणना को कम कर देता है। इससे 32-बिट और छोटे आर्किटेक्चर पर अंतर हो सकता है। X86 मशीनों पर 32-बिट प्रक्रियाओं को इसे एक ही निर्देश में अनुकूलित किया जा सकता है जो बस XORs 2 रजिस्टर्स है।

return (int)(value^(value >>> 32));

अन्य उत्तर में बताया गया है, इस नहीं एक अच्छा avalanche effect और इसलिए है टकराव का कारण बन सकता है। उच्च हिमस्खलन प्रभाव सुनिश्चित करने के लिए क्रिप्टोग्राफिक हैश फ़ंक्शन के साथ जा सकता है। हालांकि, अन्य एल्गोरिदम जैसे Murmur Hash (अधिक information) हैं जिनके पास बहुत अच्छा हिमस्खलन प्रभाव है लेकिन अधिक CPU समय का उपभोग नहीं करते हैं।