[संगीत बजाना]
>> डौग लॉयड: अब तक आप सरणियों बारे में बहुत कुछ पता है,
और आप लिंक सूचियों के बारे में बहुत कुछ पता है।
और हम चर्चा है पेशेवरों और विपक्ष, हम है
सूचियों जुड़ा हुआ है कि चर्चा की बड़े और छोटे प्राप्त कर सकते हैं,
लेकिन वे और अधिक आकार ले।
सारणियों और अधिक सरल करने के लिए कर रहे हैं उपयोग करते हैं, लेकिन वे के रूप में ज्यादा में प्रतिबंधात्मक रहे
हम का आकार निर्धारित करने के लिए है बहुत शुरुआत में सरणी
और फिर हम इसके साथ अटक कर रहे हैं।
>> लेकिन यह है कि हम बहुत ज्यादा है, है हमारे विषयों के सभी थक
लिंक सूचियों और सरणियों के बारे में।
या हम है?
शायद हम कुछ कर सकते हैं यहां तक ​​कि अधिक रचनात्मक।
और उधार देता है कि तरह एक हैश तालिका का विचार है।
>> तो एक हैश तालिका में हम कोशिश करने के लिए जा रहे हैं एक लिंक सूची के साथ एक सरणी गठबंधन।
हम लाभ लेने के लिए जा रहे हैं सरणी की, रैंडम एक्सेस की तरह,
सिर्फ सरणी के लिए जाने के लिए सक्षम किया जा रहा है तत्व 4 या सरणी तत्व 8
भर में पुनरावृति करने के लिए बिना।
यह ठीक है, बहुत तेज है?
>> लेकिन हम यह भी हमारे डेटा है चाहता हूँ संरचना बढ़ने और हटना करने में सक्षम हो।
हम नहीं करते हैं, की जरूरत नहीं प्रतिबंधित किया जा करना चाहते हैं।
और हम सक्षम होना चाहता हूँ जोड़ सकते हैं और चीजों को दूर करने के लिए
बहुत आसानी से, जो आपको याद है, एक सरणी के साथ बहुत जटिल है।
और हम इस कॉल कर सकते हैं नई बात यह है कि एक हैश तालिका।
>> और अगर, सही ढंग से लागू हम की तरह ले रहे हैं
दोनों डेटा के फायदे आप पहले से ही देखा है संरचनाओं,
सरणियों और लिंक सूचियों।
प्रविष्टि करने के लिए शुरू कर सकते हैं 1 का थीटा की ओर जाते हैं।
थीटा हम वास्तव में चर्चा नहीं की है, लेकिन थीटा सिर्फ औसत मामला है,
क्या वास्तव में होने जा रहा है।
तुम हमेशा के लिए नहीं जा रहे हैं सबसे बुरी स्थिति है,
और तुम हमेशा के लिए नहीं जा रहे हैं सबसे अच्छी स्थिति है, तो क्या है
औसत परिदृश्य?
>> खैर औसत प्रविष्टि एक हैश तालिका में
करीब लगातार समय को पाने के लिए शुरू कर सकते हैं।
और विलोपन प्राप्त कर सकते हैं लगातार समय के लिए बंद कर दें।
और देखने का मिल सकता है लगातार समय के लिए बंद कर दें।
That's-- हम एक डेटा नहीं है संरचना है कि अभी तक ऐसा कर सकते हैं,
और इसलिए यह पहले से ही लग रहा है एक बहुत बड़ी बात यह है की तरह।
हम वास्तव में कम किया गया है, अपने दम पर प्रत्येक के नुकसान।
>> इस प्रदर्शन को प्राप्त करने के लिए , हालांकि हम उन्नयन
हम कैसे जुड़ पुनर्विचार करने की जरूरत है संरचना में डेटा।
विशेष रूप से हम चाहते हैं डेटा ही हमें बताने के लिए
जहां यह संरचना में जाना चाहिए।
और हम तो उस में देखने के लिए अगर जरूरत है तो संरचना है, हम यह पता करने की जरूरत है,
हम डेटा को देखने के लिए चाहते हैं फिर से और प्रभावी ढंग से करने में सक्षम हो,
डेटा का उपयोग कर, बेतरतीब ढंग से इसे उपयोग।
बस को देखकर डेटा हम होनी चाहिए
वास्तव में हम कर रहे हैं, जहां की एक विचार हैश तालिका में इसे खोजने के लिए जा रहा है।
>> हैश का अब नकारात्मक पहलू तालिका में वे वास्तव में कर रहे हैं कि है
आदेश या डेटा छँटाई पर बहुत बुरा।
और वास्तव में, अगर आप शुरू आदेश या ऐसा करने के लिए उन्हें का उपयोग करने के लिए
डेटा आप सभी को खोना फायदे पहले आप
प्रविष्टि और विलोपन के मामले में किया था।
समय के करीब हो जाता है n के थीटा, और हम मूल रूप से है
एक लिंक सूची में वहीं।
और इसलिए हम केवल हैश उपयोग करना चाहते हैं टेबल के बारे में हम परवाह नहीं है
डेटा हल है या नहीं।
संदर्भ के लिए जो में आप CS50 में उन्हें इस्तेमाल करेंगे
आप शायद परवाह नहीं है डेटा हल है कि।
>> तो एक हैश तालिका एक संयोजन है दो अलग-अलग टुकड़ों में से
जिसके साथ हम परिचित हैं।
पहले एक समारोह है, जो हम आम तौर पर एक हैश समारोह कहते हैं।
और कहा कि हैश समारोह के लिए जा रहा है कुछ गैर-ऋणात्मक पूर्णांक जो वापसी
हम आम तौर पर ठीक है, एक हैशकोड कहते हैं?
दूसरा टुकड़ा है जो एक सरणी है प्रकार हम के भंडारण के डेटा के लिए सक्षम
डेटा संरचना में जगह चाहते हैं।
हम पर पकड़ लेंगे अब के लिए सूची तत्व से जुड़े
और सिर्फ एक के मूल के साथ शुरू इसके चारों ओर अपने सिर को पाने के लिए मेज हैश,
और फिर हम शायद उड़ा देंगे अपने मन में एक छोटा सा जब हम
एक साथ सरणियों और लिंक सूचियों गठबंधन।
>> मूल विचार है, हालांकि हम कुछ डेटा ले रहा है।
हम जानते हैं कि डेटा के माध्यम से चलाने हैश समारोह।
और इसलिए डेटा संसाधित किया जाता है और यह ठीक है, एक नंबर बाहर spits?
और फिर उस नंबर के साथ हम सिर्फ डाटा स्टोर
हम में संग्रहीत करना चाहते हैं उस स्थान पर सरणी।
तो उदाहरण के लिए हम शायद है तार के इस हैश तालिका।
यह ऐसा है, तो उस में 10 तत्वों मिल गया है हम इसे में 10 तार फिट कर सकते हैं।
>> हम जॉन हैश करने के लिए कहना चाहते हैं।
जॉन तो डेटा के रूप में हम सम्मिलित करना चाहते हैं कहीं न कहीं इस हैश तालिका में।
हम कहाँ रखा है?
खैर, आम तौर पर के साथ एक सरणी अब तक हम शायद
सरणी स्थान 0 में इसे रखा जाएगा।
लेकिन अब हम इस नए हैश समारोह है।
>> और चलो हम जॉन चलाने का कहना है कि चलो इस हैश समारोह के माध्यम से
और यह 4 बाहर spits है।
हम कर रहे हैं, जहां अच्छा है कि है जॉन डाल करना चाहते करने के लिए जा रहा है।
हम सरणी स्थान में जॉन डाल करना चाहते हैं 4, हम again-- जॉन हैश क्योंकि अगर
के बाद हम हम कहते हैं खोज और देखना चाहते हैं
जॉन इस हैश में मौजूद है हम सब करने की ज़रूरत table--
एक ही हैश के माध्यम से चलाया जाता है समारोह, 4 नंबर बाहर निकलना
और जॉन खोजने के लिए सक्षम होना तुरंत हमारे डेटा संरचना में।
वो काफ़ी अच्छा है।
>> हम अब यह कर हम कहते हैं फिर, हम पॉल हैश करने के लिए चाहते हैं।
हम पॉल को जोड़ना चाहते हैं इस हैश तालिका में।
चलो इस बार हम चलाने का कहना है कि हैश समारोह के माध्यम से पॉल,
उत्पन्न होता है कि हैशकोड 6 है।
खैर अब हम पॉल डाल सकते हैं सरणी स्थान 6 में।
और हम हैं कि क्या देखने की जरूरत है, तो पॉल इस हैश तालिका में है,
हम सब करने की ज़रूरत पॉल चलाया जाता है हैश समारोह के माध्यम से फिर से
और हम फिर से बाहर 6 पाने के लिए जा रहे हैं।
>> और फिर हम बस देखो सरणी स्थान 6 पर।
पॉल है?
यदि हां, तो वह हैश तालिका में है।
पॉल नहीं है?
उन्होंने कहा कि हैश तालिका में नहीं है।
यह बहुत स्पष्ट है।
>> अब कैसे आप एक हैश समारोह परिभाषित करते हैं?
खैर के लिए वास्तव में कोई सीमा नहीं है संभव हैश कार्यों की संख्या।
वास्तव में से एक नंबर, वहाँ वास्तव में इंटरनेट पर वास्तव में अच्छे लोगों को।
की एक संख्या है, वास्तव में नहीं है इंटरनेट पर बहुत बुरा वाले।
यह भी बहुत आसान है एक बुरा एक लिखने के लिए।
>> तो क्या एक अच्छा बनाता है ऊपर हैश समारोह, है ना?
वैसे एक अच्छा हैश कार्य करना चाहिए केवल डेटा hashed किया जा रहा उपयोग करते हैं,
और डेटा के सभी hashed जा रहा है।
इसलिए हम anything-- का उपयोग नहीं करना चाहते हैं हम कुछ भी शामिल नहीं है
डेटा के अलावा अन्य।
और हम सभी डेटा के उपयोग करना चाहते हैं।
हम सिर्फ एक टुकड़े का उपयोग नहीं करना चाहते हैं इसके बारे में, हम इसके बारे में सभी का उपयोग करना चाहते हैं।
एक हैश कार्य करना चाहिए यह भी निश्चयात्मक हो।
इसका क्या मतलब है?
खैर इसका मतलब यह है कि हर बार हम डेटा की सटीक एक ही टुकड़े से पारित
हैश समारोह में हम हमेशा एक ही हैशकोड बाहर निकलते हैं।
मैं में जॉन गुजरती हैं हैश समारोह मैं 4 बाहर निकलते हैं।
मुझे लगता है कि ऐसा करने में सक्षम होना चाहिए 10,000 बार और मैं हमेशा 4 मिल जाएगा।
तो कोई यादृच्छिक संख्या को प्रभावी ढंग से हमारे हैश में शामिल किया जा सकता tables--
हमारे हैश कार्यों में।
>> एक हैश समारोह भी चाहिए समान रूप से डेटा वितरित।
हर बार जब आप के माध्यम से डेटा चलाते हैं हैश समारोह में आप, हैशकोड 0 मिल
कि ठीक है, शायद इतना बड़ा नहीं है?
आपको शायद यह बड़ा करना चाहते हैं हैश कोड की एक सीमा होती है।
इसके अलावा बातें फैल सकता है तालिका भर में बाहर।
और यह भी कि यह वास्तव में अगर बहुत अच्छा होगा जॉन और जोनाथन की तरह समान डेटा,
शायद वजन करने के लिए बाहर फैल रहे थे हैश तालिका में विभिन्न स्थानों।
यह एक अच्छा लाभ होगा।
>> यहाँ एक हैश समारोह का एक उदाहरण है।
जैसा कि मैंने पहले इस एक को लिखा था।
यह एक विशेष रूप से नहीं है अच्छा हैश समारोह
वास्तव में ऐसा नहीं है कि कारणों के लिए अब सही में जा रहा सहन।
लेकिन तुम यहाँ क्या हो रहा है देखते हैं?
हम एक चर घोषित कर रहे हैं ऐसा लगता है जैसे योग और 0 के बराबर इसे स्थापित करने का आह्वान किया।
और फिर जाहिरा तौर पर मैं कुछ कर रहा हूँ इतने लंबे समय strstr [जम्मू] बराबर नहीं है के रूप में
0 Backslash करने के लिए।
मैं वहाँ क्या कर रहा हूँ?
>> यह मूल रूप से सिर्फ एक है [लागू करने का तरीका है? Strl?]
आप है और जब पता लगाने स्ट्रिंग के अंत पर पहुंच गया।
इसलिए मैं वास्तव में करने के लिए नहीं है स्ट्रिंग की लंबाई की गणना,
मैं मारा जब मैं बस का उपयोग कर रहा हूँ बैकस्लैश 0 चरित्र मुझे पता है
मैं स्ट्रिंग के अंत में पहुँच गए हैं।
और फिर मैं रखने के लिए जा रहा हूँ कि तार के माध्यम से पुनरावृति,
strstr [जम्मू] जोड़ने में तो राशि है, और करने के लिए दिन के अंत योग आधुनिक वापस जा रहा
HASH_MAX।
>> असल में यह सब हैश समारोह को जोड़ कर रही है
के ASCII मूल्यों के सभी मेरे स्ट्रिंग, और फिर यह है
कुछ हैशकोड लौटने HASH_MAX द्वारा modded।
यह शायद आकार है मेरी सरणी की, है ना?
मैं हैश हो रही हो नहीं करना चाहते हैं कोड अपने सरणी आकार 10 का है,
मैं हो रही हो नहीं करना चाहते हैं बाहर हैश कोड 11, 12,
13, मैं चीजों में नहीं डाल सकते हैं सरणी के उन स्थानों,
कि गैरकानूनी होगा।
मैं एक विभाजन गलती पीड़ित था।
>> अब यहाँ एक और जल्दी अलग है।
आम तौर पर आप शायद करने के लिए नहीं जा रहे हैं अपने खुद के हैश कार्यों लिखना चाहते हैं।
यह वास्तव में एक सा है एक कला है, एक विज्ञान नहीं।
और उन में चला जाता है कि एक बहुत कुछ है।
जैसा मैंने कहा इंटरनेट, भरा हुआ है, वास्तव में अच्छा हैश कार्यों की,
और आप के लिए इंटरनेट का उपयोग करना चाहिए यह सच है, क्योंकि हैश कार्यों मिल
बस की तरह एक अनावश्यक समय की बर्बादी के लिए अपने स्वयं के बनाने के लिए।
>> आप साधारण लोगों को लिख सकते हैं परीक्षण प्रयोजनों के लिए।
लेकिन अगर आप वास्तव में करने जा रहे हैं जब डेटा hashing और यह भंडारण शुरू
आप कर रहे हैं एक हैश तालिका में शायद चाहते करने जा
उत्पन्न किया गया था कि कुछ समारोह का उपयोग करने के लिए आप के लिए, कि इंटरनेट पर मौजूद है।
आप बस सुनिश्चित करते हैं अपने सूत्रों का हवाला देते।
वहाँ कोई कारण नहीं है यहाँ कुछ भी plagiarize।
>> कंप्यूटर विज्ञान समुदाय है निश्चित रूप से मूल्यों बढ़ रही है, और वास्तव में
खुला स्रोत है, और यह वास्तव में महत्वपूर्ण है अपने सूत्रों का हवाला देते हैं ताकि लोग
के लिए रोपण प्राप्त कर सकते हैं वे कर रहे हैं कि काम
समुदाय के लाभ के लिए कर रही है।
तो हमेशा sure-- होना और न सिर्फ हैश के लिए
काम करता है, लेकिन आम तौर पर जब आप एक बाहरी स्रोत से कोड का उपयोग,
हमेशा अपने स्रोत का हवाला देते हैं।
किया है जो व्यक्ति को ऋण देने काम के कुछ है ताकि आप की जरूरत नहीं है।
>> ठीक है तो चलो इस पर फिर से आना चलो एक पल के लिए हैश तालिका।
हम छोड़ दिया, जहां यह है हम डाला के बाद बंद
इस हैश तालिका में जॉन और पॉल।
आप यहाँ एक समस्या देखते हैं?
आप दो देख सकते हैं।
लेकिन विशेष रूप से, आप करते हैं इस संभावित समस्या देखते हैं?
>> क्या मैं रिंगो हैश, और अगर यह बाद के प्रसंस्करण पता चला है कि
हैश समारोह के माध्यम से उस डेटा रिंगो भी हैशकोड 6 उत्पन्न।
मैं पहले से ही पर डेटा मिल गया है hashcode-- सरणी स्थान 6।
तो यह शायद एक सा होने जा रहा है अब मेरे लिए एक समस्या की, है ना?
>> हम एक टकराव कहते हैं।
और टकराव जब दो होता है डेटा के टुकड़े ही हैश के माध्यम से चलाने
समारोह में एक ही हैशकोड निकलेगा।
मुमकिन है कि हम अभी भी दोनों प्राप्त करना चाहते हैं हैश तालिका में डेटा के टुकड़े,
अन्यथा हम रिंगो चल नहीं किया जाएगा मनमाने ढंग से हैश समारोह के माध्यम से।
हम संभवतः प्राप्त करना चाहते हैं उस सरणी में रिंगो।
>> हम हालांकि यह कैसे करते हो, यदि वह और पॉल दोनों उपज हैशकोड 6?
हम पॉल के ऊपर लिख नहीं करना चाहते हैं, हम पॉल भी वहाँ रहना चाहता हूँ।
तो हम पाने के लिए एक रास्ता खोजने की जरूरत हैश तालिका में तत्वों कि
अभी भी हमारे त्वरित बरकरार रखता है प्रविष्टि और त्वरित देखो ऊपर।
और इसके साथ सौदा करने के लिए एक तरह से करने के लिए है जांच कर रही रैखिक बुलाया कुछ करो।
>> हम एक है, तो इस विधि का प्रयोग टक्कर, ठीक है, हम क्या करें?
खैर, हम सरणी स्थान में उसे नहीं डाल सकते हैं 6, या जो कुछ भी हैशकोड उत्पन्न किया गया था,
के हैशकोड प्लस 1 में उसे डाल दिया।
और कहा कि पूरा चलो अगर हैशकोड प्लस 2 में डाल दिया।
इस होने का लाभ है कि वह अगर नहीं वास्तव में हम वह है जहां आपको लगता है,
और हम खोज शुरू कर दिया है, शायद हम बहुत दूर जाने की जरूरत नहीं है।
शायद हम खोज करने की जरूरत नहीं है हैश तालिका के सभी n तत्वों।
शायद हम खोज करने के लिए उनमें से एक जोड़ी।
>> और इसलिए हम अभी भी ओर प्रवृत्त कर रहे हैं औसत के मामले एक के करीब बनाम जा रहा है कि
एन के करीब है, तो हो सकता है कि काम करेंगे।
तो चलो यह कैसे देखते हैं वास्तविकता में बाहर काम हो सकता है।
और हो सकता है कि हम पता लगा सकते हैं, तो चलो देखते हैं यहां हो सकता है कि समस्या।
>> हम बार्ट हैश कहते हैं।
तो अब हम एक नया सेट चलाने के लिए जा रहे हैं हैश समारोह के माध्यम से तार की,
और हम हैश के माध्यम से बार्ट चलाने समारोह में, हम हैशकोड 6 मिलता है।
हम एक बार देख ले, हम 6 देखना खाली है, इसलिए हम वहाँ बार्ट डाल सकते हैं।
>> अब हम लिसा और हैश यह भी हैशकोड 6 उत्पन्न करता है।
खैर अब हम इस का उपयोग कर रहे हैं कि रेखीय, हम 6 बजे शुरू विधि की जांच कर रही
हम 6 भरा है कि देखते हैं।
हम 6 में लिसा नहीं डाल सकते हैं।
तो हम कहाँ जाते हो?
7 के लिए चलते हैं।
7 खाली है, इसलिए काम करता है।
तो चलो देखते लिसा डाल दिया।
>> अब हम होमर हैश और हम 7 मिलता है।
ठीक है अच्छी तरह हम जानते हैं कि 7 की पूरी कि अब, इसलिए हम वहाँ होमर नहीं डाल सकते हैं।
तो चलो 8 के लिए चलते हैं।
8 उपलब्ध है?
हाँ, और 7 से 8 के करीब है, यदि ऐसा है तो हम हम कर रहे हैं खोज शुरू करने के लिए है
बहुत दूर जाने की जरूरत नहीं जा रहा।
और तो 8 पर होमर डाल दिया।
>> अब हम हैश मैगी और 3 देता है, भगवान का शुक्र है
हम सिर्फ वहाँ मैगी डाल करने में सक्षम हो।
हम कोई भी कार्य करने की जरूरत नहीं है एक तरह से उस के लिए जांच कर रही है।
अब हम मार्ज हैश, और मार्ज भी 6 रिटर्न।
>> खैर 6, 8 भरा है, 7 भरा है, पूर्ण है 9, सब ठीक 9 खाली है, भगवान का शुक्र है।
मैं 9 पर मार्ज डाल सकते हैं।
पहले से ही हम हम शुरू कर रहे हैं कि देख सकते हैं हम कर रहे हैं, जहां अब इस समस्या के लिए
तरह बातें फैलाने के लिए शुरू कर के दूर दूर उनके हैश कोड से।
और 1 के कि थीटा, कि औसत लगातार समय होने के मामले,
एक छोटे more-- पाने के लिए शुरू कर रहा है एक छोटे से अधिक करते हैं करने के लिए शुरू
n के थीटा की ओर।
हम जानते हैं कि कम करने के लिए शुरू कर रहे हैं हैश तालिकाओं का लाभ।
>> हम सिर्फ देखा है कि यह समस्या क्लस्टरिंग कहा जाता है।
और सच के बारे में बुरा क्या है क्लस्टरिंग कि आप एक बार अब है
पक्ष हैं कि दो तत्वों से है यह इसे और भी अधिक होने की संभावना बनाता पक्ष,
आप डबल है मौका है, आप जा रहे हैं कि
एक और टक्कर के लिए है कि क्लस्टर के साथ,
और क्लस्टर एक के द्वारा विकसित होगा।
और अगर आप बढ़ रही है और बढ़ रहा रखेंगे एक टक्कर होने की संभावना।
और अंत में यह बस के रूप में बुरा है के रूप में सभी डेटा छँटाई नहीं।
>> दूसरी समस्या यह है कि हम है अभी भी, और अब तक इस बात के लिए,
हम बस की तरह किया गया है एक हैश तालिका में क्या है, समझ
हम अभी भी केवल 10 तार के लिए कमरा है।
हम हैश करने के लिए जारी रखना चाहते हैं स्प्रिंगफील्ड के नागरिकों,
हम केवल वहाँ में उनमें से 10 प्राप्त कर सकते हैं।
और हम कोशिश करते हैं और एक 11 वीं या 12 वीं जोड़ने अगर हम उन्हें डाल करने के लिए एक जगह की जरूरत नहीं है।
हम बस में चारों ओर कताई किया जा सकता है हलकों, एक खाली जगह खोजने की कोशिश
और हम शायद अटक जाते हैं एक अनंत लूप में।
>> तो विचार को उधार देता है की इस तरह कुछ की श्रंखला का आह्वान किया।
और यह हम लाने के लिए जा रहे हैं, जहां है वापस तस्वीर में लिंक सूचियों।
क्या होगा अगर बजाय सिर्फ संचय के लिए सरणी में डेटा ही,
सरणी के प्रत्येक तत्व सकता है कई टुकड़े डेटा की पकड़?
अच्छा है कि ठीक है, मतलब नहीं है?
हम जानते हैं कि एक सरणी ही पता कर सकते हैं एक सरणी के प्रत्येक तत्व hold--
केवल एक टुकड़ा पकड़ कर सकते हैं कि डेटा प्रकार के डेटा की।
>> लेकिन क्या है कि अगर डेटा प्रकार एक लिंक सूची है, सही?
तो क्या हुआ अगर हर सरणी का तत्व था
एक लिंक सूची के सिर के लिए एक संकेत?
और फिर हम निर्माण कर सकता है उन लिंक सूचियों
और, मनमाने ढंग से उन्हें विकसित लिंक सूचियों अनुमति है, क्योंकि
हमें आगे बढ़ने और एक बहुत अधिक हटना करने के लिए एक सरणी करता है लचीले ढंग से।
तो क्या अब हम का उपयोग करते हैं, हम सही, इस का लाभ उठाने?
हम इन जंजीरों विकसित करने के लिए शुरू इन सरणी स्थानों से बाहर।
>> अब हम एक अनंत फिट कर सकते हैं डेटा की राशि, या अनंत नहीं,
की एक मनमाना राशि डेटा, हमारे हैश तालिका में
कभी में चल रहे बिना टक्कर की समस्या।
हम भी समाप्त कर दिया है ऐसा करके क्लस्टरिंग।
और अच्छी तरह से हम सम्मिलित करते हैं कि पता एक लिंक सूची में, यदि आपको याद है
अकेले, लिंक सूचियों पर हमारे वीडियो से लिंक सूचियों और दोगुना लिंक सूचियों,
यह एक निरंतर समय ऑपरेशन है।
हम बस सामने से जोड़ रहे हैं।
>> और देखो ऊपर के लिए, अच्छी तरह से हम जानते हैं कि एक लिंक सूची में ऊपर देखो
ठीक है, एक समस्या हो सकती है?
हम के माध्यम से खोज करने के लिए शुरू से ही इसे समाप्त करने के लिए।
कोई यादृच्छिक नहीं है एक लिंक सूची में पहुँच।
लेकिन यदि बजाय एक होने के लिंक्ड एक देखने एन हे होगा जहां सूची,
हम अब 10 लिंक सूचियों है, या 1,000 लिंक सूचियों,
अब यह 10 से विभाजित n के हे, या एन हे 1,000 से विभाजित।
>> और हम बात कर रहे थे, जबकि सैद्धांतिक रूप से जटिलता के बारे में
हम वास्तविक में, स्थिरांक उपेक्षा इन बातों को वास्तव में कोई फर्क दुनिया,
है ना?
हम वास्तव में नोटिस जाएगा ऐसा होता है कि
तेजी से 10 बार चलाने के लिए, या 1,000 गुना तेजी से,
हम लंबे समय से एक का वितरण कर रहे हैं, क्योंकि 1,000 छोटे चेन पार श्रृंखला।
और इसलिए हम हर बार खोज करने के लिए हम कर सकते हैं उन श्रृंखलाओं में से एक के माध्यम से
हम परवाह नहीं है 999 चेन की अनदेखी के बारे में है, और सिर्फ इतना है कि एक खोज करते हैं।
>> जो करने के लिए औसत पर है 1,000 बार कम हो।
और इसलिए हम अभी भी एक तरह से कर रहे हैं इस औसत के मामले की ओर प्रवृत्त
की लगातार समय से किया जा रहा है, लेकिन केवल हम लाभ कर रहे हैं, क्योंकि
कुछ बड़ी निरंतर पहलू से विभाजित।
यह कैसे हो सकता है चलो देखते हैं वास्तव में, हालांकि देखो।
तो यह है कि हम था हैश तालिका था हम एक हैश तालिका घोषित करने से पहले कि
10 तार भंडारण के लिए सक्षम था।
हम अब और ऐसा करने के लिए नहीं जा रहे हैं।
हम पहले से ही पता कि विधि की सीमाओं।
अब हमारी हैश तालिका होने जा रहा है 10 नोड्स, संकेत की एक सरणी
लिंक सूचियों के प्रमुखों को।
>> और अभी यह रिक्त है।
उन 10 संकेत से हर एक रिक्त है।
कुछ भी नहीं है हमारे में नहीं है अब सही तालिका हैश।
>> अब हम कुछ डाल करने के लिए शुरू करते हैं इस हैश तालिका में बातें।
और हम इस पद्धति है कि कैसे देखते हैं हमें एक छोटा सा फायदा होने जा रहा।
चलो अब जॉय हैश करते हैं।
हम स्ट्रिंग जॉय के माध्यम से चलेंगे करेंगे एक हैश समारोह और हम 6 वापसी।
खैर अब हम क्या करते हैं?
>> खैर अब लिंक सूचियों के साथ काम कर रहे हैं, हम सरणियों के साथ काम नहीं कर रहे।
और हम काम कर रहे हैं लिंक सूचियों के साथ हम
हम गतिशील शुरू करने की जरूरत है अंतरिक्ष और निर्माण चेन का आवंटन।
उस तरह की उन प्रमुख हैं how-- है एक लिंक की गई सूची के निर्माण के तत्वों।
तो गतिशील चलो जॉय के लिए जगह आवंटित,
और उसके बाद की श्रृंखला के लिए उसे जोड़ दें।
>> तो अब हम क्या किया है देखो।
हम जॉय हैश जब हम हैशकोड 6 मिला है।
सरणी स्थान 6 पर अब सूचक एक लिंक सूची के सिर पर बताते हैं,
और अभी यह केवल एक लिंक सूची के तत्व।
और उस में नोड लिंक सूची जॉय है।
>> हम जॉय को देखने की जरूरत है तो अगर बाद में, हम तो बस फिर जॉय हैश,
हम अपने क्योंकि फिर 6 मिलता है हैश समारोह निर्धारक है।
और फिर हम सिर पर शुरू लिंक सूची का इशारा
सरणी स्थान के आधार पर करने के लिए 6, और हम पुनरावृति कर सकते हैं
जॉय खोजने की कोशिश है कि भर में।
और हम का निर्माण करता है, तो हमारे प्रभावी ढंग से मेज हैश,
और हमारे हैश समारोह को प्रभावी ढंग से अच्छी तरह से डेटा को वितरित करने के लिए,
औसत पर उन लोगों में से प्रत्येक से जुड़े हर सरणी स्थान पर सूचियां
यदि का आकार 1/10 होगी हम सिर्फ एक ही विशाल के रूप में यह था
यह सब कुछ के साथ लिंक सूची।
>> हम विशाल जुड़ा हुआ है कि वितरित 10 लिंक सूचियों भर सूची
प्रत्येक सूची 1/10 आकार का हो जाएगा।
और इस तरह 10 बार तेज के माध्यम से खोज करने के लिए।
तो चलो फिर से यह करते हैं।
चलो अब रॉस हैश करते हैं।
>> और चलो हम ऐसा जब रॉस, हम कहते हैं हम वापस मिल हैश कोड 2 है।
खैर अब हम गतिशील रूप से एक का आवंटन नए नोड, हम उस नोड में रॉस डाल
और हम सरणी स्थान अब कहते हैं 2, शून्य की ओर इशारा करते बजाय,
एक लिंक्ड के सिर करने के लिए अंक जिसका केवल नोड सूची रॉस है।
और हम, हम इस एक बार और क्या कर सकते हैं राहेल हैश और हैशकोड 4 प्राप्त कर सकते हैं।
में राहेल डाल दिया, एक नया नोड malloc नोड, और एक सरणी स्थान का कहना है
4 अब सिर करने के लिए अंक जिसका एक लिंक सूची की
केवल तत्व राहेल होना होता है।
>> ठीक है, लेकिन क्या होता है अगर हम एक टकराव है?
हम टक्करों संभाल कैसे देखते हैं अलग श्रृंखलन विधि के प्रयोग से।
के चांद हैश करते हैं।
हम हैशकोड 6 मिलता है।
हमारे पिछले उदाहरण में हम सिर्फ थे सरणी में तार भंडारण।
यह एक समस्या थी।
>> हम पीटना नहीं करना चाहते हैं जॉय, और हम पहले से ही है
हम कुछ क्लस्टरिंग प्राप्त कर सकते हैं कि देखा समस्याओं हम कोशिश करते हैं और अगर कदम
के माध्यम से और जांच।
लेकिन क्या करता है, तो हम बस की तरह यह सही है, उसी तरह से व्यवहार करता है?
यह सिर्फ एक तत्व जोड़ने की तरह है एक लिंक सूची के सिर पर।
चांद के लिए चलो बस malloc अंतरिक्ष करते हैं।
>> हम चांद की अगली सूचक अंक कहूँगा लिंक सूची के पुराने सिर करने के लिए,
और फिर 6 बस के लिए अंक लिंक सूची के नए प्रमुख के।
और अब हम में चांद बदल दिया है, देखो।
अब हम दो स्टोर कर सकते हैं हैशकोड 6 के साथ तत्वों,
और हम किसी भी समस्या नहीं है।
>> यही कारण है कि बहुत ज्यादा सब है श्रृंखलन के लिए नहीं है।
और श्रृंखलन निश्चित रूप से है है कि विधि
अगर आप के लिए सबसे अधिक प्रभावी होने जा रहा आप एक हैश तालिका में डेटा भंडारण कर रहे हैं।
लेकिन के इस संयोजन सरणियों और लिंक सूचियों
एक साथ वास्तव में एक हैश तालिका के लिए फार्म का नाटकीय ढंग से अपनी क्षमता में सुधार
डेटा की बड़ी मात्रा में स्टोर, और करने के लिए बहुत जल्दी और कुशलता से खोज
कि डेटा के माध्यम से।
>> एक और अभी भी है वहाँ से बाहर आंकड़ा संरचना
कि यह भी एक सा हो सकता है गारंटी देने के मामले में बेहतर
कि हमारी प्रविष्टि, हटाने, और देखो बार भी तेजी से कर रहे हैं।
और हम कोशिश करता है पर एक वीडियो में देखेंगे।
मैं डौग लॉयड हूँ, इस CS50 है।