चेनिंग के साथ हैश टेबल को कैसे कार्यान्वित करें?

Question

यह शायद एक बेवकूफ सवाल है, लेकिन मैं भगवान के प्यार के बारे में बताता हूं कि चेनिंग के साथ हैश टेबल के पीछे सिद्धांत में मैं क्या खो रहा हूं।

एक हैश तालिका एक स्थान जहां एक मूल्य संग्रहीत किया जाता है के लिए एक महत्वपूर्ण संबद्ध करने के लिए एक हैश का उपयोग करता है:

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

इस मामले में हम उसी स्थान के साथ सभी स्थानों को उस स्थान पर एक लिंक की गई सूची में संग्रहीत करके चेनिंग लागू कर सकते हैं।

यह क्या मुझे समझ नहीं आता है:

जब आप में प्रवेश के लिए एक महत्वपूर्ण और हैश समारोह, एक स्थान है, जिस पर वहाँ चेनिंग पर हो जाता है कि यह कैसे निर्धारित करता है लिंक्ड सूची में जो मूल्य उस स्थान के अंतर्गत आता है पर टकराव में शामिल एक और कुंजी के विपरीत, उस विशिष्ट कुंजी?

मुझे एहसास है कि यह मूल सिद्धांत है, लेकिन अगर कोई मेरी तर्क में त्रुटियों को इंगित कर सकता है या मुझे बता सकता है कि मैं क्या खो रहा हूं तो मैं इसकी बहुत सराहना करता हूं।

Answer 1

सरल तरीका: "हैश टेबल प्रविष्टियों" की एक लिंक सूची बनाए रखें, जो कुंजी/मूल्य जोड़े हैं। एक बार जब आप बाल्टी में जाते हैं, तो बाल्टी में सभी चाबियों के खिलाफ अपनी क्वेरी कुंजी जांचें।

Answer 2

जब आप एक महत्वपूर्ण और हैश समारोह में प्रवेश एक स्थान है, जिस पर वहाँ चेनिंग है, यह कैसे निर्धारित करता है के रूप में में शामिल एक अन्य प्रमुख का विरोध करने के उस स्थान पर लिंक्ड सूची में जो मूल्य, कि विशिष्ट कुंजी के अंतर्गत आता है पैदा करता है टकराव?

आप बस कुंजी द्वारा बाल्टी की रैखिक खोज का सहारा लेते हैं।

आप निम्न मिनी हैश तालिका कार्यान्वयन एफ # में लिखा, this blog post से लिया सराहना हो सकता है:

> let hashtbl xs = 
    let spine = [|for _ in xs -> ResizeArray()|] 
    let f k = spine.[k.GetHashCode() % spine.Length] 
    Seq.iter (fun (k, v) -> (f k).Add (k, v)) xs 
    fun k -> Seq.pick (fun (k', v) -> if k=k' then Some v else None) (f k);; 
val hashtbl : seq<'a * 'b> -> ('a -> 'b) when 'a : equality 

यह hashtbl समारोह, कुंजी-मान जोड़ों का एक संघ अनुक्रम xs लेता है एक spine के रूप में प्रतिनिधित्व एक हैश तालिका बनाता है ResizeArray बाल्टी की सरणी और एक लैम्ब्डा फ़ंक्शन देता है जो उपयुक्त बाल्टी पाता है और दिए गए कुंजी k के लिए इसमें रैखिक खोज करता है। रैखिक खोज Seq.pick फ़ंक्शन का उपयोग करके की जाती है।