हैशटेबल हैशिंग नकारात्मक हैशकोड से बचें

Question

मुझे आश्चर्य है कि क्यों Hashtable नकारात्मक हैशकोड का उपयोग करने से बचें?

int hash = key.hashCode(); 
int index = (hash & 0x7FFFFFFF) % tab.length; 

कहाँ (hash & 0x7FFFFFFF) पर हस्ताक्षर किए सा सकारात्मक 0 होने के लिए करता है, लेकिन क्यों हम अहस्ताक्षरित के रूप में हस्ताक्षर किए 32 बिट पूर्णांक का इलाज नहीं कर सकता है? या इसे सकारात्मक बनने के लिए मॉड्यूलर चाल का भी उपयोग करें। उदाहरण के लिए,

public static long int_mod(int hashcode, int tab_length){ 
    return (hashcode % tab_length + tab_length) % tab_length; 
} 

Answer 1

मूल्य क्योंकि यह मान (और अतिप्रवाह तत्वों) भंडारण (इस मामले में tab) एक आंतरिक सरणी में एक सूचकांक के रूप में प्रयोग किया जाता है 0 और tab.length - 1 के बीच हो गया है। इसलिए, यह नकारात्मक नहीं हो सकता है।

मुझे लगता है (hash & 0x7FFFFFFF) % tab.length(hashcode % tab.length + tab.length) % tab.length की वरीयता में प्रयोग किया जाता है अनावश्यक रूप से टकराव की संभावना बढ़ बिना तेजी से, क्योंकि यह है, लेकिन आप एक डिजाइन दस्तावेज़ लगता है या मूल डेवलपर्स से बात निश्चित रूप से जानना होगा।

Answer 2

... लेकिन क्यों सकता है नहीं हम ...

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

कोड में किसी विचार को लागू करने के लिए हमेशा कई तरीके हैं। कोड लिखने वाला व्यक्ति उनमें से एक को चुनना है। यह पूछने के लिए बहुत समझदारी नहीं है, तथ्य के बाद, एक और विशेष कार्यान्वयन क्यों नहीं चुना गया था।

Answer 3

जावा का मूल निवासी प्रकार नहीं है। यदि hashCode के पास नकारात्मक मान होंगे तो हमें हर जगह ऐसी मास्किंग चालें लागू करनी होंगी जहां हम hashCode का उपयोग सरणी में इंडेक्स के रूप में करते हैं।

Answer 4

कोई भी आपको क्यों बता सकता है क्यों मूल लेखक ने स्वयं को (और शायद उनके सहयोगियों) को छोड़कर उस कार्यान्वयन को चुना। यह वास्तव में किसी भी तरह से कोई फर्क नहीं पड़ता क्योंकि यह ठीक काम करता है।

बारे में क्या अपने प्रस्तावित कार्यान्वयन: यह शायद आप क्या सोचते हैं यह करना चाहिए नहीं करता है। जावा में% ऑपरेटर वास्तव में क्या करता है आपको रीफ्रेश करना चाहिए: For example here। मिश्रण में पूर्णांक ओवरफ़्लो जोड़ें और आपकी प्रस्तावित अभिव्यक्ति के परिणामस्वरूप ऋणात्मक मूल्य हो सकते हैं ...

Answer 5

एक असाधारण कारण है कि हम हस्ताक्षरित int का हस्ताक्षर नहीं कर सकते हैं: मूल जावा डेवलपर्स ने सोचा कि हस्ताक्षरित समर्थन एक था अनावश्यक जटिलता, जैसा कि हस्ताक्षरित अंकगणित confusing हो सकता है। जावा के लिए पता लगाने के लिए यह एक बड़ा मुद्दा नहीं रहा है।

verdesmerald mentioned के रूप में, के बाद से वहाँ क्यों (hash & 0x7FFFFFFF) % tab.length, अपने चालाक modding के प्रभाव से कुछ अधिक में चुना गया था, हालांकि हम निर्णय के लिए प्रामाणिकता पा सकते हैं, अंत में हम केवल कारण है कि यह बनाया गया था के बारे में अटकलें कर सकते हैं का कोई स्पष्ट रिकार्ड है।

अर्थशास्त्र का एक अंतिम बिंदु, जो शायद यह महत्वपूर्ण नहीं है: यह इतना नहीं है कि हैशटेबल नकारात्मक हैशकोड का उपयोग नहीं कर रहा है क्योंकि यह है कि हैशकोड को "अनुवाद" को इंडेक्स के लिए एक गैर-स्वरूपित रूप में "अनुवादित किया जा रहा है"।

Answer 6

आप अपनी क्षमता 2 की एक शक्ति है,

private static final int CAPACITY = 64; 
private static final int HASH_MASK = CAPACITY - 1; 

final int index = obj.hashCode() & HASH_MASK; 

असल में, सब बाहर मुखौटा लेकिन निम्न बिट्स जिसमें आप रुचि रखते हैं रखें। निचले एन बिट्स को मानना ​​है कि पूरे हैश कोड के रूप में वितरण के रूप में भी है।