[ஓசை].
புல அட்டவணைகள் டைவிங் முன், நாம்
முதல் சில சாதக ஆய்வு
எளிமையான தரவு கட்டமைப்புகள், தொடங்கி
வரிசைகள்.
வரிசைகள் எங்களுக்கு சேமிக்க அனுமதிக்கும் நினைவு
ஒரு தரவு வகை உறுப்புகள்
contiguously நினைவகத்தில்.
ஒவ்வொரு உறுப்பு தொடர்புடைய ஏனெனில்
ஒரு குறியீட்டு, அல்லது இடம்,
நாம் அனைத்து சீரற்ற அணுகல்
ஒரு அணியின் உறுப்புகள்.
வேறுவிதமாக கூறினால், நாம் எந்த உறுப்பு அணுக முடியும்
ஒரு அதுவொரு மூலம் ஒரு படி
வரிசை.
இந்த, ஒரு பெரிய ஒப்பந்தம் ஏனெனில் வழிமுறைகள்
இரும தேடல் போன்ற சீரற்ற சார்ந்தது
அணுகல்.
வரிசைகள் ஒரு எதிர்மறையாக உள்ளது என்று அவற்றின் அளவு
சரி செய்யப்பட்டது.
வரிசைகள் கடையில் தரவு contiguously ஏனெனில்
நினைவகம், நீங்கள் ஒரு வரிசை அளவு குறிப்பிட வேண்டும்
நீங்கள் அணி அறிவிக்க போது.
நீங்கள் திறம்பட இயக்க கேட்கிறாய்
சரியான அளவு ஒதுக்கி அமைப்பு
வரிசை கூறுகளை நினைவகம்.
உத்தரவாதம் இல்லை என்று இன்னும் நினைவு,
உங்கள் வரிசை அருகில், கிடைக்க வேண்டும்
பின்னர் பயன்படுத்த.
எனவே வரிசைகள் எளிதாக வளர முடியாது.
நாங்கள் இணைக்கப்பட்ட பற்றி கற்று அந்த நினைவு
வளர முடியும் பட்டியல்கள், ஏனெனில் அவர்கள்
உறுப்புகள் நினைவக ஒட்டியுள்ள இல்லை.
ஒரு இணைக்கப்பட்ட பட்டியலில் ஒவ்வொரு கணு கொண்டிருக்கிறது
நாம் சேமிக்க வேண்டும் என்று உறுப்பு, அதே போல்
அடுத்தடுத்த உறுப்பு ஒரு சுட்டிக்காட்டி
பட்டியலில்.
துரதிருஷ்டவசமாக, நாம் பணம் விலை
மாறும் அளவு சீரற்ற அணுகல் ஆகிறது
உறுப்புகள்.
ஒரு குறிப்பிட்ட உறுப்பு அணுக பொருட்டு,
அது முழு தொடரவேண்டும் தேவையான
விரும்பிய உறுப்பு ஆகும் வரை பட்டியலிட
அடைந்தது.
நான் எண் 9 தேடிக்கொண்டிருக்கிறேன் என்றால், நான் கூட
முனை இருந்து முனை சுட்டிகள் பின்பற்ற,
சோதனை என்பது ஒவ்வொரு கணு மதிப்பு
9 சமமாக இருக்கும்.
எனினும், மிக மோசமான நிலையில் உள்ளது, பார்க்க
இதுவரை திறமையான இருந்து இது ஓ (n),.
நாம் ஓ விட சிறப்பாக செய்ய முடியும் (N) போது இன்னும்
எங்கள் தரவு கட்டமைப்பு மேல் வளர அனுமதிப்பது
நேரம்?
புல அட்டவணைகள் ஒரு தீர்வு வழங்குகின்றன.
புல அட்டவணைகள் பயன்படுத்தப்படும் போது விரைவாக
புகுத்தியது, நீக்கல், மற்றும் பார்வை
உறுப்புகள் முன்னுரிமை உள்ளது.
கோட்பாடு, புகுத்தியது, நீக்கல், மற்றும் தேடல்
நிலையான அடைய முடியும்
நேரம்.
எனவே, ஒரு ஹாஷ் அட்டவணை எப்படியும் என்ன?
ஒரு ஹாஷ் அட்டவணை இணைந்து ஒரு வரிசை உள்ளது
நாம் புல அழைக்கிறேன் இது ஒரு செயல்பாடு,
செயல்பாடு.
ஹாஷ் சார்பு தரவு ஒரு துண்டு எடுக்கிறது
உள்ளீடு, நாம் ஒரு முக்கிய அழைப்பு, மற்றும் வேண்டும்
பொதுவாக ஒரு முழு, வெளியீடு
ஒரு ஹாஷ் மதிப்பு.
புல மதிப்பு ஒரு எங்கள் முக்கிய வரைபடங்கள்
ஹாஷ் அட்டவணை குறிப்பிட்ட குறியீட்டு.
நீங்கள் ஆரம்பத்தில் ஹாஷ் சார்பு பயன்படுத்த விரும்புகிறேன்
அங்கு ஹாஷ் அட்டவணை தீர்மானிக்க
ஒரு குறிப்பிட்ட முக்கிய சேமிக்க.
பின்னர், அதே ஹாஷ் சார்பு பயன்படுத்த விரும்புகிறேன்
அங்கு ஹாஷ் அட்டவணை தீர்மானிக்க
ஒரு குறிப்பிட்ட முக்கிய தேட.
இந்த காரணத்திற்காக, அது முக்கியமான விஷயம் என்று ஒரு ஹாஷ்
செயல்பாடு தொடர்ந்து மற்றும் வெளியீடுகளை செயல்படுகிறது
ஒரே சாவியை அதே ஹாஷ் மதிப்பு.
புல அட்டவணைகள் பயன்படுத்த முடியும் என்று எனக்கு தெரியும்
அனைத்து வகையான தரவுகள்.
ஆனால் பொருட்களை எளிமைப்படுத்த, நாம் கவனம் செலுத்த வேண்டும்
இப்போது சரங்களை.
இங்கே சரங்களை ஒரு எளிய ஹாஷ் சார்பு இருக்கிறது.
இந்த ஹாஷ் சார்பு ஒரு ஹாஷ் கணக்கிடுகிறது
முதல் கடிதம் அடிப்படையாக செயல்பாடு
முக்கிய.
"ஆப்பிள்" எழுத்து "அ" தொடங்குகிறது, அது தான்
ஹாஷ் அட்டவணை குறியீட்டு 0 ஒப்பிடப்படுகிறது.
இதேபோல், "வாழை", குறியீட்டு 1 ஒப்பிடப்படுகிறது
மற்றும் "cat" குறியீட்டு 2 ஒப்பிடப்படுகிறது.
வார்த்தை "நாய்" என்றால் ஒரு நண்பர் கேட்கிறார் என்றால்
அட்டவணை, நாம் புல உள்ளீடு "நாய்" டாஸ்மாக்
செயல்பாடு, இது நான் வெளியீடு ஒரு ஹாஷ் மதிப்பு
3.
"நாய்" குறியீட்டு 3 சேமிக்கப்படும் இல்லை என்பதால், நாம்
"நாய்" என்று நம்பிக்கையுடன் சொல்ல முடியும்
அட்டவணை,
நாம் ஒரு பார்த்துவிட்டேன் கூட
அட்டவணை 26 குறியீடுகள் புல.
விஷயங்களை ஒரு குறடு தூக்கி நேரம்.
நாம் ஒரு "எறும்பு" சேமிக்க வேண்டும் என்றால்
அட்டவணை அதே?
"எறும்பு" தான் "ஆப்பிள்" என, குறியீட்டு 0 hashes.
இந்த மோதல் ஒரு உதாரணம் ஆகும்,
அதே சுட்டுமுகவரியாக்கம்கட்டுப்பாட்டு இரண்டு விசைகளை விளைவாக
குறியீட்டு.
உங்கள் ஹாஷ் அட்டவணை விட பெரிய கூட
உங்கள் தரவை அமைக்க, மற்றும் நீங்கள் ஒரு நல்ல தேர்வு செய்த
செயல்பாடு ஹாஷ்,
நீங்கள் இன்னும் கையாள்வதில் ஒரு திட்டம் வேண்டும்
மோதல்கள், எப்போது என்று அவர்கள் எழுகின்றன.
இரண்டு சாதக விவாதிக்க நாம்
மோதல்கள் தீர்ப்பதற்கான பொதுவான முறைகள்:
நேரியல் ஆய்வு மற்றும் தனி சங்கிலியாக்கல்.
ஒரு முக்கிய hashes என்றால் நேர்கோட்டு, ஆய்வு மூலம்
முன்பே சேமிக்கப்பட்ட அதே குறியீட்டு
முக்கிய, அது அடுத்த ஒதுக்கப்படும்
அட்டவணையில் ஸ்லாட்.
எனவே, "எறும்பு" இப்போது முதல், குறியீட்டு 3 சேமிக்கப்படுகிறது
குறியீடுகள் 0, 1, 2 ஏற்கனவே பயன்பாட்டில் இருந்தன.
நாம் ஒரு மூன்றாவது வார்த்தை சேமிக்க முயற்சி செய்தால்
கடிதம் "ஒரு" உடன் தொடங்குகிறது, அது ஒதுக்கப்படுகின்றன
குறியீட்டு 4, என்பதால் குறியீடுகள் 0, 1, 2, மற்றும் 3
முழு இருக்கின்றன.
நீங்கள் இந்த எளிய இருந்து கூட பார்க்க முடியும் என
எடுத்துக்காட்டாக, ஒரு முறை மோதல், நீங்கள் ஏற்படுகிறது
கணிசமாக வாய்ப்புகளை அதிகரிக்கும் என்று
மற்றொரு மோதல் அதே ஏற்படும்
பகுதி.
இந்த தொகுப்பு என அழைக்கப்படும், மற்றும் அது ஒரு
தீவிர குறைபாடு ஆய்வு லீனியர் வேண்டும்.
மேலும், மோசமான புகுத்தியது, நீக்கல்,
மற்றும் தேடல் முறை, ஓ (n) பகிர்ந்தளிக்க வேண்டும்
அடுத்த கிடைக்க ஸ்லாட் வேண்டும் என
திறன் அட்டவணையில் கடைசி ஸ்லாட்.
ஒருவேளை தனி சங்கிலியாக்கல் ஒரு வழங்கும்
கட்டாய தீர்வு.
தனி சங்கிலியாக்கல் மாதிரியில், ஹாஷ்
அட்டவணை உண்மையில் சுட்டிகள் ஒரு வரிசை உள்ளது
தொடர்புடைய பட்டியல்கள்.
ஒரு மோதல் ஏற்படும் போது, முக்கிய இருக்க முடியும்
தலைமை மாறா நேரம் செருகிய
அதற்கான இணைக்கப்பட்ட பட்டியலில்.
நாம் "ஆப்பிள்" ஐ தேடும் போது என்ன நடக்கிறது?
ஹாஷ் அட்டவணை?
மோசமான நிலையில், நாம் பயணிக்க வேண்டும்
குறியீட்டு 0 தொடங்கும் முழு இணைக்கப்பட்ட பட்டியலில்,.
ஒரு ஹாஷ் மோசமான பார்வை நேரம்
தனி சங்கிலியாக்கல் பயன்படுத்தும் அட்டவணை உள்ளது
எனவே, k எங்கே ஓ (n / K),
ஹாஷ் அட்டவணை அளவு.
இரண்டாவது காத்திருக்க, k ஒரு நிலையாக இருக்கிறது.
எனவே ஓ (n / K), உண்மையில் தான் ஓ (n) ஆகும்
மோசமான பார்வை நேரம் இது
ஒரு இணைக்கப்பட்ட பட்டியலில்.
நாம் உண்மையில் அனைத்து அனுபவித்திருக்கிறேன்
புல அட்டவணைகள் பற்றி அறிந்து சிக்கல்
நாம் தொடங்கிய மட்டுமே மீண்டும் முடிவடையும்?
என்று ஒரு தத்துவார்த்த இருந்து வழக்கு இருக்கலாம்
முன்னோக்கு, ஆனால் நிஜ உலகில்,
ஓ (n / K) ஒரு பெரிய முன்னேற்றம் இருக்க முடியும்
ஓ (n).
அது இந்த வழி என்று: என்று கே நினைத்து
10 - நீங்கள் மாறாக 100 வினாடிகள் காத்திருக்க வேண்டும்
அல்லது 100 / k!
முடிக்க மைக்ரோசாப்ட் வேர்ட் இருந்து 10 விநாடிகள்
உங்கள் ஆவணம் சரிபார்ப்புக்கு.
நீங்கள் தான் பார்த்தேன், மோதல்கள் தீர்ப்பதற்கான
ஒரு நேர்கோட்டு தேடல் வகையான அல்லது தவிர்க்கமுடியாததாக்குகிகிறது
கீழே விஷயங்கள் தாமதப்படுத்தி இது மற்றொரு,
கணிசமாக.
எனவே, நீங்கள் ஒரு ஹாஷ் தேர்வு வேண்டும் என்று நான் நினைக்கிறேன்
வாய்ப்பை குறைக்கிறது என்று செயல்பாடு
முதல் இடத்தில் நிகழும் மோதல்கள்.
இங்கே நல்ல புல சில பண்புகள் இருக்கின்றன
மனதில் வைத்து செயல்படுகிறது.
ஒரு நல்ல ஹாஷ் சார்பு பயன்படுத்த வேண்டும்
ஒரு குறிப்பிட்ட முக்கிய வழங்கப்பட்ட அனைத்து தகவல்
எண்ணிக்கை அதிகரிக்க வேண்டும்
முடிந்தவரை ஹாஷ் மதிப்புகள்.
உதாரணமாக, நாம் இரண்டு சரங்களை இருந்தால், "பூனை"
மற்றும் "கேட்டர்பில்லர்", நாம் அவர்களை புல வேண்டும் என்று
மேஜையில் வெவ்வேறு இடங்களில்.
ஒரு ஹாஷ் சார்பு மட்டுமே கணக்கில் எடுத்து என்றால்
முதல் ஒன்று, இரண்டு, அல்லது மூன்று கடிதங்கள்
சரங்களை, ஒரு மோதல் ஏற்படும்,
இரு வார்த்தைகள் தொடங்க முதல்
மூன்று கடிதங்கள்.
ஹாஷ் மதிப்புகள் சமமாக பரப்ப வேண்டும்
ஹாஷ் அட்டவணை முழுவதும்.
இந்த இணைக்கப்பட்ட நீளம் குறைக்கும்
பட்டியல்கள் மோதல்கள் ஏற்படுகின்றன.
இது ஒரு நல்ல அறிகுறி உங்கள் ஹாஷ் மதிப்பு
மிகவும் வேறுபட்ட உருவாக்கும் திறன்
இதே போன்ற விசைகளை மதிப்புகள் ஹாஷ்,
மிகவும் குறைவான மோதல்கள் செய்யும்.
எங்கள் இலக்கு விரைவாக புகுத்தியது, நீக்கல் ஆகிறது,
மற்றும் தேடல்.
ஹாஷ் சார்பு ஒரு முக்கிய பங்கு வகிக்கிறது
இந்த செயல்முறைகள் ஒவ்வொரு இருக்கும்
மிகவும் அடிக்கடி அழைக்கும்.
எனவே, நிச்சயம் அது மட்டுமே மிக அமர்த்தியுள்ளது செய்ய
எளிய, விரைவான நடவடிக்கைகளை ரன் குறைக்க
நேரம்.
நான் இந்த குறுகிய அனுபவித்து நம்புகிறேன்
அட்டவணைகள் பங்குகள் அறிமுகம்.
என் பெயர் லாரன், மற்றும் இந்த CS50 உள்ளது.