दो एरे

Question

के साथ हैश तालिका बनाएं क्या कोई यह जानता है कि यह कैसे करें और छद्म कोड कैसा दिखता है?

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

Answer 1

वास्तव में, आज HashMap implentations वास्तव में सरणियों के बने होते हैं में से कुछ आप प्रस्ताव के रूप में। मुझे स्केच यह कैसे काम करता है:

हैश समारोह एक हैश समारोह पहली सरणी (सरणी कश्मीर) के लिए एक सूचकांक में अपनी चाबी बदल देती है। एक हैश फ़ंक्शन जैसे एमडी 5 या एक सरल, आमतौर पर मॉड्यूल ऑपरेटर समेत, इसका उपयोग इस के लिए किया जा सकता है।

बाल्टी एक साधारण सरणी आधारित हैशमैप कार्यान्वयन बाधाओं का सामना करने के लिए बाल्टी का उपयोग कर सकता है। प्रत्येक तत्व ('बाल्टी') सरणी कश्मीर में जोड़े की ही एक सरणी (सरणी पी) शामिल हैं। जोड़ते या एक तत्व के लिए क्वेरी, हैश फंक्शन जो आपकी वांछित सरणी पी फिर आप पी में तत्वों से अधिक पुनरावृति जब तक आप मिलान कुंजी मिल जाए, या आप एक नए तत्व आवंटित कश्मीर में सही बाल्टी, करने के लिए आप अंक हैश का उपयोग कर बाल्टी के लिए पी

की

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

rescaling एक कुंजी के हैश गणना की जा रही है और सही बाल्टी खोजने बहुत जल्दी है। लेकिन एक बार बाल्टी भरने के बाद, आपको सही होने से पहले अधिक से अधिक वस्तुओं को फिर से शुरू करना होगा। तो यह काफी बाल्टी ठीक से वस्तुओं वितरित करने के लिए महत्वपूर्ण है, या अपने HashMap धीमी गति से हो जाएगा।

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

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

Hash table Wikipedia entry में आप जो पूछ रहे हैं उसका एक भिन्नता 'सरणी हैश तालिका' के रूप में वर्णित है।

कोड कोड नमूने के लिए, here देखें।

उम्मीद है कि इससे मदद मिलती है।

Answer 2

क्या आप अधिक सटीक हो सकते हैं? क्या एक सरणी में कुंजी होती है, दूसरा मूल्य?

यदि हां, तो यहाँ जावा में एक उदाहरण है (लेकिन वहाँ यहाँ इस भाषा की कुछ विशिष्टताओं हैं):

for (int i = 0; i < keysArray.length; i++) { 
    map.put(keysArray[i], valuesArray[i]); 
} 

बेशक

, आप (अपने map वस्तु का दृष्टांत के लिए है अगर आप जावा का उपयोग कर रहे होंगे, मैं एक अप्रचलित HashTable के बजाय HashMap<Object, Object> का उपयोग करने का सुझाव देता हूं), और null ऑब्जेक्ट्स से बचने के लिए अपने सरणी का परीक्षण भी करें और जांचें कि उनके पास एक ही आकार है या नहीं।

Answer 3

आपका मतलब यह है?

निम्नलिखित एक उदाहरण के रूप में रूबी के irb उपयोग कर रहा है:

cities = ["LA", "SF", "NY"] 
=> ["LA", "SF", "NY"] 

items = ["Big Mac", "Hot Fudge Sundae"] 
=> ["Big Mac", "Hot Fudge Sundae"] 

price = {} 
=> {} 

price[[cities[0], items[1]]] = 1.29 
=> 1.29 

price 
=> {["LA", "Hot Fudge Sundae"]=>1.29} 

price[[cities[0], items[0]]] = 2.49 
=> 2.49 

price[[cities[1], items[0]]] = 2.99 
=> 2.99 

price 
=> {["LA", "Hot Fudge Sundae"]=>1.29, ["LA", "Big Mac"]=>2.49, ["SF", "Big Mac"]=>2.99} 

price[["LA", "Big Mac"]] 
=> 2.49 

Answer 4

नमूना स्पष्टीकरण:

1. मानचित्र प्रतिनिधित्व

• कुछ (सूची के एक्स संख्या) की सूची
• :

  नीचे स्रोत पर, मूल रूप से यह दो बातें करता है एक्स 2 शक्तियों की संख्या एन सूची खराब है। ए (2 पावर एन) -1, या (2 पावर एन) +1, या एक प्राइम नंबर अच्छा है।

उदाहरण:

List myhashmap [hash_table_size]; 
// an array of (short) lists 
// if its long lists, then there are more collisions 

नोट: यह है सरणियों की सरणी, नहीं दो सरणियों (मैं नहीं सिर्फ 2 सरणियों के साथ एक अच्छा तरीका है, एक संभव सामान्य hashmap देख सकते हैं)

यदि आप एल्गोरिदम> ग्राफ़ सिद्धांत> एडजेंसी सूची जानते हैं, तो यह बिल्कुल वैसा ही दिखता है।

2।हैश समारोह

और हैश फंक्शन एक नंबर (हैश मान) को स्ट्रिंग (इनपुट) है, जो एक सरणी

• प्रारंभ पहले चार को हैश मान का सूचकांक है धर्मान्तरित (के बाद int करने के लिए परिवर्तित)
प्रत्येक आगे चार के लिए
• , बाएँ पारी 4 बिट्स, तो चार जोड़ने

उदाहरण (के बाद int करने के लिए परिवर्तित),

int hash = input[0]; 
for (int i=1; i<input.length(); i++) { 
    hash = (hash << 4) + input[i] 
} 

hash = hash % list.size() 
// list.size() here represents 1st dimension of (list of lists) 
//  that is 1st dimension size of our map representation from point #1 
//  which is hash_table_size 

पहले दिए गए लिंक पर देखें:

int HTable::hash (char const * str) const 

स्रोत:
http://www.relisoft.com/book/lang/pointer/8hash.html
How does a hash table work?

अद्यतन
यह सबसे अच्छा स्रोत है: http://algs4.cs.princeton.edu/34hash/