[இசை]
>> டக் LLOYD: இப்போது நீங்கள் அணிகளை பற்றி நிறைய தெரியும்,
நீங்கள் இணைக்கப்பட்ட பட்டியல்கள் பற்றி நிறைய தெரியும்.
நாம் விவாதிக்க போயிருக்கிறோம் சாதக, நாம் நான்
பட்டியல்கள் இணைக்கப்பட்ட என்று விவாதிக்கப்படும் பெரிய மற்றும் சிறிய பெற முடியும்,
ஆனால் அவர்கள் இன்னும் அளவு எடுத்து.
வரிசைகள் மிகவும் ஒளிவு உள்ளன பயன்படுத்த, ஆனால் அவர்கள், மிகவும் கட்டுப்படுத்தப்பட்ட இருக்கிறோம்
நாம் அளவு அமைக்க வேண்டும் என ஆரம்பத்தில் வரிசை
பின்னர் நாம் அதனை மாட்டிக்கொண்டிருக்கிறோம்.
>> ஆனால் நாம் அழகான மிகவும் இருக்கிறது, இருக்கிறது எங்கள் தலைப்புகள் அனைத்து தீர்ந்துவிட்டது
இணைக்கப்பட்ட பட்டியல்கள் மற்றும் அணிகளை பற்றி.
அல்லது நாம் வேண்டும்?
ஒருவேளை நாம் ஏதாவது செய்ய முடியும் இன்னும் படைப்பு.
மேலும் வழங்கியிருக்கிறது அந்த மாதிரி ஒரு ஹாஷ் அட்டவணை யோசனை.
>> எனவே ஒரு ஹாஷ் அட்டவணை நாங்கள் முயற்சி செய்ய போகிறோம் ஒரு இணைக்கப்பட்ட பட்டியலில் ஒரு வரிசை இணைக்க.
நாம் நன்மைகள் எடுக்க போகிறோம் வரிசை, ரேண்டம் அக்சஸ் போன்ற,
வெறும் வரிசை செல்ல முடியும் உறுப்பு 4 அல்லது அணி உறுப்பு 8
முழுவதும் மீண்டும் கூறு இல்லாமல்.
அந்த உரிமை, அழகான வேகமாக?
>> ஆனால் நாங்கள் எங்கள் தரவு வேண்டும் கட்டமைப்பு வளர மற்றும் சுருக்க முடியும்.
நாம் நாம் செய்ய தேவையில்லை தடை செய்ய வேண்டும்.
நாம் முடியும் வேண்டும் சேர்க்க மற்றும் பொருட்களை நீக்க
மிக எளிதாக, இது நீங்கள் நினைவு என்றால், ஒரு வரிசை மிகவும் சிக்கலாக உள்ளது.
நாம் இந்த அழைக்க முடியும் புதிய விஷயம் ஒரு ஹாஷ் அட்டவணை.
>> என்றால், சரியாக செயல்படுத்தப்படவில்லை நாம் அப்படி எடுத்து வருகிறோம்
இரு தரவு நன்மைகள் நீங்கள் ஏற்கனவே பார்த்த கட்டமைப்புகள்,
வரிசைகள் மற்றும் தொடர்புடைய பட்டியல்கள்.
செருகும் ஆரம்பிக்க முடியும் 1, தீட்டா நோக்கி முனைகின்றன.
தீட்டா நாம் உண்மையில் விவாதிக்கப்பட்டது, ஆனால் தீட்டா வெறும் சராசரி வழக்கு,
என்ன உண்மையில் என்ன நடக்க போகிறது.
நீங்கள் எப்போதும் போவதில்லை மோசமான சூழ்நிலையில் வேண்டும்,
, எப்போதும் போவதில்லை சிறந்த வழக்கு சூழ்நிலையில், அதனால் என்ன
சராசரி சூழ்நிலையில்?
>> சரி சராசரியாக செருகும் ஒரு ஹாஷ் அட்டவணை
நெருங்கிய நேர மாறிலி பெற ஆரம்பிக்க முடியும்.
மற்றும் நீக்குதல் பெற முடியும் நேர மாறிலி அருகில்.
மற்றும் தேடல் பெற முடியும் நேர மாறிலி அருகில்.
அதைத்தான் நாம் ஒரு தரவு இல்லை அமைப்பு இன்னும் அந்த செய்ய முடியும் என்று,
எனவே இந்த ஏற்கனவே தெரிகிறது ஒரு அழகான பெரிய விஷயம் போல்.
நாம் உண்மையில் மட்டுப்படுத்தப்படுகிறது விட்டேன் அதன் சொந்த ஒவ்வொரு தீமைகள்.
>> இந்த செயல்திறன் பெற , எனினும் நாம் மேம்படுத்த
நாம் சேர்க்க எப்படி முடிவை மறு பரிசீலனை செய்ய வேண்டும் கட்டமைப்பாக தரவு.
குறிப்பாக நாம் விரும்பும் தரவு தன்னை எங்களுக்கு சொல்ல
அங்கு அது கட்டமைப்பில் செல்ல வேண்டும்.
மற்றும் நாம் அதை தான் நாம் பார்க்க வேண்டும் என்றால் கட்டமைப்பு, நாம் அதை கண்டுபிடிக்க வேண்டும் என்றால்,
நாங்கள் தரவு பார்க்க வேண்டும் மீண்டும் திறம்பட செய்ய முடியும்,
தரவு பயன்படுத்தி, தோராயமாக அதை அணுக.
வெறும் பார்த்து தரவு நாம் இருக்க வேண்டும்
சரியாக நாம் இருக்கிறோம் அங்கு ஒரு யோசனை ஹாஷ் அட்டவணை அதை கண்டுபிடிக்க போவதில்லை.
>> ஒரு ஹாஷ் இப்போது எதிர்மறையாக அட்டவணை அவர்கள் உண்மையிலேயே என்று ஆகிறது
வரிசைப்படுத்தும் அல்லது தரவை வரிசையாக்கம் மணிக்கு மோசமாக.
உண்மையில், நீங்கள் ஆரம்பித்தால் உத்தரவிடும் அல்லது வகையான அவற்றை பயன்படுத்த
தரவு நீங்கள் அனைத்து இழக்க நன்மைகள் முன்னர் நீங்கள்
செருகும் மற்றும் நீக்குதல் ஆகியவற்றில் இருந்து.
நேரம் அருகில் ஆகிறது n, தீட்டா, நாம் அடிப்படையில் போயிருக்கின்றன
ஒரு இணைக்கப்பட்ட பட்டியலில் பின்னடைவு.
எனவே நாம் மட்டும் புல பயன்படுத்த வேண்டும் அட்டவணைகள் நாம் பற்றி கவலை இல்லை என்றால்
தரவு வரிசையாக்கம் என்பதை.
சூழல் இதில் நீங்கள் CS50 அவற்றை பயன்படுத்த வேண்டும்
ஒருவேளை நீங்கள் கவலை இல்லை தரவு வரிசைப்படுத்தப்பட்ட என்று.
>> எனவே ஒரு ஹாஷ் அட்டவணை ஒரு கலவையாக உள்ளது இரண்டு வேறுபட்ட துண்டுகள்
இதில் நாம் நன்கு அறிவோம்.
முதல் ஒரு செயல்பாடு, இது நாம் பொதுவாக ஒரு ஹாஷ் சார்பு அழைக்க.
அந்த ஹாஷ் சார்பு போகிறது சில அல்லாத எதிர்மறை முழு திரும்ப இது
நாம் பொதுவாக சரி, ஒரு Hashcode அழைப்பு?
இரண்டாவது துண்டு இது ஒரு வரிசை, ஆகிறது வகை நாம் சேமித்து தரவு திறன்
தரவு அமைப்பு வைக்க வேண்டும்.
நாம் அன்று நடத்த வேண்டும் இப்போது பட்டியல் உறுப்பு இணைக்கப்பட்ட
மற்றும் ஒரு அடிப்படைகள் தொடங்கும் அதை சுற்றி உங்கள் தலையில் பெற அட்டவணை புல,
மற்றும் நாம் ஒருவேளை ஊதி வேண்டும் உங்கள் மனதில் சிறிது போது நாம்
ஒன்றாக வரிசைகள் மற்றும் இணைப்பு பட்டியல்கள் இணைக்க.
>> அடிப்படை யோசனை என்றாலும் நாம் சில தரவு எடுத்து உள்ளது.
நாம் என்று தரவு மூலம் இயக்க ஹாஷ் சார்பு.
எனவே தரவு பதப்படுத்தப்பட்ட அது சரி, ஒரு எண் வெளியே துப்பி?
பின்னர் அந்த எண் நாம் தான் தரவு சேமிக்க
நாம் சேமிக்க வேண்டும் அந்த இடத்தில் வரிசை.
எனவே எடுத்துக்காட்டாக நாம் ஒருவேளை வேண்டும் சரங்களை இந்த ஹாஷ் அட்டவணை.
அது, அது 10 உறுப்புகள் கிடைத்தது நாம் அது 10 சரங்களை பொருத்த முடியும்.
>> நாம் ஜான் புல வேண்டும் என்று சொல்கிறேன்.
ஜான் எனவே தரவு நாம் சேர்க்க வேண்டும் எங்காவது இந்த ஹாஷ் அட்டவணை.
நாங்கள் அதை எங்கே வைக்க வேண்டும்?
சரி பொதுவாக ஒரு வரிசை இதுவரை நாம் அநேகமாக
வரிசையில் இடம் 0 அதை வைக்க வேண்டும்.
ஆனால் இப்போது நாம் இந்த புதிய ஹாஷ் சார்பு.
>> மற்றும் நாம் ஜான் ரன் என்று சொல்கிறேன் இந்த ஹாஷ் செயல்பாடு மூலம்
மற்றும் 4 வெளியே துப்பி.
நாங்கள் இருக்கும் இடத்தில் சரி என்று தான் ஜான் வைக்க வேண்டும் போகிறது.
நாம் வரிசை இடம் உள்ள ஜான் வைக்க வேண்டும் 4, நாம் மீண்டும் ஜான் புல என்றால், ஏனெனில்
பின்னர் நாங்கள் சொல்கிறேன் தேடல் மற்றும் பார்க்க வேண்டும்
ஜான் இந்த ஹாஷ் உள்ளது என்றால் நாம் என்ன செய்ய வேண்டும் அனைத்து அட்டவணை
அதே ஹாஷ் மூலம் இயக்க விழாவில், எண் 4 வெளியே
மற்றும் ஜான் கண்டுபிடிக்க முடியும் உடனடியாக எங்கள் தரவு கட்டமைப்பு இல்லை.
அந்த அழகான நல்லது.
>> நாம் இப்போது இதை செய்ய சொல்கிறேன் மீண்டும், நாம் பால் புல வேண்டும்.
நாம் பால் சேர்க்க வேண்டும் இந்த ஹாஷ் அட்டவணை.
இந்த நேரத்தில் நாம் ரன் என்று சொல்கிறேன் ஹாஷ் சார்பு மூலம் பவுல்
உருவாக்கப்படும் என்று Hashcode 6 ஆகும்.
சரி இப்போது நாம் பால் வைக்க முடியாது வரிசையில் இடம் 6.
நாம் என்பதை பார்க்க வேண்டும் என்றால் பவுல் இந்த ஹாஷ் அட்டவணை உள்ளது,
நாம் என்ன செய்ய வேண்டும் அனைத்து பால் ரன் ஹாஷ் சார்பு மூலம் மீண்டும்
நாம் வெளியே மீண்டும் 6 பெற போகிறோம்.
>> மற்றும் நாம் இப்போது பார்க்க வரிசையில் இடம் 6.
பால் இருக்கிறதா?
அப்படியானால், அவர் ஹாஷ் அட்டவணை தான்.
பால் அங்கு இல்லையா?
அவர் ஹாஷ் அட்டவணை இல்லை.
அது மிகவும் நேரடியான தான்.
>> இப்போது எப்படி நீங்கள் ஒரு ஹாஷ் சார்பு வரையறை என்ன?
சரி உண்மையில் எல்லை இல்லை சாத்தியமான ஹாஷ் செயல்பாடுகளை எண்ணிக்கை.
உண்மையில் ஒரு எண், உண்மையில் இல்லை இணையத்தில் உண்மையில் நல்ல தான்.
ஒரு எண், உண்மையில் உள்ளது இணையத்தில் மிகவும் மோசமாக தான்.
இது மிகவும் எளிது ஒரு மோசமான ஒரு எழுத.
>> அதனால் என்ன ஒரு நல்ல வரை செய்கிறது ஹாஷ் சார்பு, சரியான?
சரி ஒரு நல்ல ஹாஷ் சார்பு வேண்டும் தரவு hashed வருகின்றன பயன்படுத்த,
மற்றும் தரவு அனைத்து தயார் செய்தனர்.
எனவே நாம் ஒன்றுமே பயன்படுத்த வேண்டும் நாம் எதையும் இணைத்துக்கொள்ள
தரவு தவிர வேறு.
நாம் தரவு அனைத்து பயன்படுத்த வேண்டும்.
நாம் ஒரு துண்டு பயன்படுத்த விரும்பவில்லை அது, நாம் அதை பயன்படுத்த வேண்டும்.
ஒரு ஹாஷ் சார்பு வேண்டும் மேலும் நிர்ணயிக்கப்பட்ட இருக்க.
அதற்கு என்ன பொருள்?
சரி அது அர்த்தம் என்று ஒவ்வொரு முறையும் நாம் தரவு அதே துண்டு கடந்து
ஹாஷ் சார்பு நாம் எப்போதும் அதே Hashcode வெளியே.
நான் ஒரு ஜான் கடந்து இருந்தால் ஹாஷ் சார்பு நான் 4 வெளியே.
நான் அதை செய்ய முடியும் 10,000 முறை நான் எப்போதும் 4 கிடைக்கும்.
எனவே எந்த சீரற்ற எண்கள் திறம்பட எங்கள் ஹாஷ் ஈடுபட்டு tables--
எங்கள் ஹாஷ் செயல்பாடுகளை.
>> ஒரு ஹாஷ் சார்பு மேலும் வேண்டும் சீராக தரவு விநியோகிக்கிறது.
ஒவ்வொரு முறையும் நீங்கள் மூலம் தரவு ரன் என்றால் ஹாஷ் சார்பு, Hashcode 0 கிடைக்கும்
அந்த உரிமை, ஒருவேளை மிக பெரிய இல்லை?
நீங்கள் ஒருவேளை பெரிய வேண்டும் புல குறியீடுகள் ஒரு எல்லை.
மேலும் விஷயங்களை பரவியது அட்டவணை முழுவதும்.
மேலும் இது என்றால் உண்மையில் நன்றாக இருக்கும் ஜான் மற்றும் ஜொனாதன் போன்ற ஒத்த தரவு,
ஒருவேளை எடையை வெளியே பரவியது ஹாஷ் அட்டவணை வெவ்வேறு இடங்களில்.
என்று ஒரு நல்ல நன்மை இருக்கும்.
>> இங்கே ஒரு ஹாஷ் சார்பு ஒரு எடுத்துக்காட்டு.
நான் முன்பு இந்த ஒரு வரை எழுதினார்.
இது ஒரு குறிப்பாக இல்லை நல்ல ஹாஷ் சார்பு
உண்மையில் இல்லை என்று காரணங்களுக்காக இப்போது செல்லும் தாங்க.
ஆனால் நீங்கள் இங்கே என்ன நடக்கிறது பார்க்க வேண்டும்?
நாம் ஒரு மாறி அறிவித்தார் போல் தெரிகிறது தொகை மற்றும் 0 சமமாக அதை அமைக்க அழைத்தார்.
பின்னர் வெளிப்படையாக நான் ஏதாவது செய்கிறேன் நான் எனவே நீண்ட strstr [ஜே] சமமாக இல்லை என
0 பின்சாய்வுக்கோடானது.
நான் அங்கு என்ன செய்து கொண்டிருக்கிறேன்?
>> இந்த அடிப்படையில் மற்றொரு ஆகிறது [செயல்படுத்தும் வழி? strl?]
வந்துவிடும்.ஓ போது கண்டறிவதை சரம் இறுதியில் அடைந்தது.
எனவே நான் உண்மையில் இல்லை சரம் நீளம் கணக்கிட,
நான் ஹிட் போது நான் தான் பயன்படுத்தி பின்சாய்வுக்கோடானது 0 பாத்திரம் எனக்கு தெரியும்
நான் சரம் இறுதியில் அடைந்தது.
பின்னர் நான் வைத்து போகிறேன் அந்த சரம் மூலம் தேடி,
strstr [ஜே] சேர்த்து பின்னர் தொகைக்கு, மற்றும் நாள் முடிவில் தொகை மோட் திரும்ப போகிறது
HASH_MAX.
>> அடிப்படையில் அனைத்து இந்த ஹாஷ் செயல்பாடு வரை சேர்த்து வருகிறது செய்து
என்ற ASCII மதிப்புகள் அனைத்து என் சரம், பின்னர் அது தான்
சில Hashcode திரும்பிய HASH_MAX மூலம் modded.
இது அநேகமாக அளவு தான் என் வரிசை, சரியான?
நான் ஹாஷ் பெற வேண்டும் விரும்பவில்லை குறியீடுகள் என் வரிசை அளவு 10 என்றால்,
நான் பெறுவது விரும்பவில்லை வெளியே புல குறியீடுகள் 11, 12,
13, நான் விஷயங்களை வைத்து முடியாது வரிசை அந்த இடங்களில்,
என்று சட்ட விரோதமாகும்.
நான் ஒரு அடுக்கு தவறு பாதிக்கப்படுகின்றனர் என்று.
>> இப்போது இங்கே மற்றொரு விரைவான ஒதுக்கி உள்ளது.
பொதுவாக ஒருவேளை நீங்கள் போவதில்லை உங்கள் சொந்த ஹாஷ் செயல்பாடுகளை எழுத வேண்டும்.
அது உண்மையில் ஒரு பிட் உள்ளது ஒரு கலை, ஒரு அறிவியல்.
அவர்களில் செல்கிறது என்று நிறைய இருக்கிறது.
நான் சொன்னது போல் இணைய, முழு உள்ளது உண்மையில் நல்ல ஹாஷ் செயல்பாடுகளை,
நீங்கள் இணைய பயன்படுத்த வேண்டும் அது உண்மையில் ஏனெனில் ஹாஷ் செயல்பாடுகளை கண்டுபிடிக்க
வெறும் வகையான ஒரு தேவையற்ற நேரம் கழிவு உங்கள் சொந்த உருவாக்க.
>> நீங்கள் எளிய தான் எழுத முடியும் சோதனை நோக்கங்களுக்காக.
ஆனால் நீங்கள் உண்மையில் போகிறோம் போது தரவு hashing மற்றும் அதை சேமித்து தொடங்க
நீங்கள் ஒரு ஹாஷ் அட்டவணை ஒருவேளை வேண்டும் போகிறீர்கள்
உருவாக்கப்படும் என்று சில செயல்பாடு பயன்படுத்த , என்று இணையத்தில் உள்ளது.
நீங்கள் உறுதியாக இருக்க என்றால் உங்கள் குரல்களை.
எந்த காரணமும் இல்லை இங்கே எதையும் காப்பி அடிக்கிறார்கள்.
>> கணினி அறிவியல் சமூகம் நிச்சயமாக மதிப்புகள் வளர்ந்து, மற்றும் உண்மையில்
திறந்த மூல, அது மிக முக்கியம் உங்கள் குரல்களை என்று மக்கள்
உரிப்பளிப்புகளின் பெற முடியும் அவர்கள் அந்த வேலை
பொது மக்களின் நன்மைக்காக செய்து.
எனவே எப்போதும் உறுதி இருக்க மற்றும் மட்டும் புல க்கான
செயல்பாடுகளை, ஆனால் பொதுவாக போது நீங்கள் வெளியில் இருந்து குறியீடு பயன்படுத்த,
எப்போதும் உங்கள் மூல மேற்கோள்.
செய்த நபர் கடன் கொடுக்க வேலை சில எனவே நீங்கள் இல்லை.
>> சரி எனவே இந்த மீண்டும் நாம் இரண்டாவது ஹாஷ் அட்டவணை.
நாம் விட்டு, அங்கு இது நாம் சேர்க்கப்பட்டது பிறகு ஆஃப்
இந்த ஹாஷ் அட்டவணை ஜான் பால்.
நீங்கள் இங்கே ஒரு பிரச்சினை பார்க்க வேண்டும்?
நீங்கள் இரண்டு பார்க்க வேண்டும்.
ஆனால் குறிப்பாக, நீங்கள் செய்ய இது சாத்தியம் பிரச்சனை பார்க்க?
>> என்ன நான் ரிங்கோ புல, அது என்றால் பின்னர் செயலாக்க என்று மாறிவிடும்
ஹாஷ் சார்பு மூலம் தரவு ரிங்கோ மேலும் Hashcode 6 உருவாக்கப்படும்.
நான் ஏற்கனவே தரவு கிடைத்துவிட்டது hashcode-- வரிசையில் இடம் 6.
அது அநேகமாக ஒரு பிட் இருக்கும் நடக்கிறது இப்போது எனக்கு ஒரு பிரச்சினை, சரியான?
>> நாம் ஒரு மோதல் அழைக்கிறோம்.
மற்றும் மோதல் போது இரண்டு ஏற்படுகிறது தரவு துண்டுகள் அதே ஹாஷ் மூலம் இயக்க
செயல்பாடு ஒன்று Hashcode விளைவிக்கும்.
மறைமுகமாக நாம் இன்னும் இரு பெற வேண்டும் ஹாஷ் அட்டவணை தரவு துண்டுகள்,
இல்லையெனில் நாம் ரிங்கோ இயங்கும் தன்னிச்சையாக ஹாஷ் சார்பு மூலம்.
நாம் மறைமுகமாக பெற வேண்டும் அந்த அணி மீது ரிங்கோ.
>> நாம் என்றாலும் அது எப்படி முடியும், அவர் என்றால் பவுலும் மகசூல் Hashcode 6?
நாம் பால் மேலெழுத விரும்பவில்லை, நாம் பால் மிகவும் அங்கு இருக்க வேண்டும்.
எனவே நாம் பெற ஒரு வழி கண்டுபிடிக்க வேண்டும் ஹாஷ் அட்டவணை உறுப்புகள் என்று
இன்னும் எங்கள் விரைவான காக்கிறது செருகும் மற்றும் விரைவான தோற்றத்தை.
மற்றும் அதை சமாளிக்க ஒரு வழி உள்ளது ஆய்வு லீனியர் என்று ஏதாவது செய்ய.
>> நாம் ஒரு இருந்தால் இந்த முறையை பயன்படுத்தி மோதல், நன்றாக, நாம் என்ன செய்ய வேண்டும்?
சரி நாம் வரிசையில் இடம் அவரை வைக்க முடியாது 6, அல்லது என்ன Hashcode உருவாக்கப்படும்,
தான் Hashcode பிளஸ் 1 அவரை வைத்து விடுங்கள்.
அந்த முழு நாம் என்றால் Hashcode பிளஸ் 2 அவரை வைத்து.
இதை சொல்லிக் நலனுக்காக அவர் என்றால் இல்லை சரியாக நாம் அவர் நினைப்பதை எங்கே,
மற்றும் நாம் தேடி தொடங்க வேண்டும், ஒருவேளை நாம் வெகு தூரம் போக வேண்டியது இல்லை.
ஒருவேளை நாம் தேட வேண்டும் ஹாஷ் அட்டவணை அனைத்து n உறுப்புகள்.
ஒருவேளை நாம் தேட வேண்டும் அவர்கள் ஒரு ஜோடி.
>> எனவே நாம் இன்னும் நோக்கி தன்மை சராசரி நிலை 1 நெருங்கிய எதிராக இருப்பது
n க்கு நெருக்கமான, அதனால் அந்த வேலை கிடைக்கும்.
எனவே எப்படி இந்த பார்ப்போம் யதார்த்தத்தில் வேலை என்று.
ஒருவேளை நாம் கண்டறிய முடியும் என்றால் நாம் பார்ப்போம் இங்கே நிகழலாம் என்று பிரச்சனை.
>> நாம் பார்ட் புல சொல்கிறேன்.
எனவே இப்போது நாம் ஒரு புதிய தொகுப்பு இயக்க போகிறீர்கள் ஹாஷ் சார்பு மூலம் சரங்களை,
நாம் புல மூலம் பார்ட் ரன் செயல்பாடு, நாம் Hashcode 6 கிடைக்கும்.
நாங்கள் பாருங்கள், நாம் 6 பார்க்க காலியாக எனவே அங்கு பார்ட் வைக்க முடியாது.
>> இப்போது நாம் லிசா மற்றும் அந்த புல மேலும் Hashcode 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--
ஒரே ஒரு துண்டு நடத்த முடியும் தரவு வகை தரவு.
>> ஆனால் என்ன தரவு வகை ஒரு இணைக்கப்பட்ட பட்டியலில், சரியா?
அதனால் என்ன என்றால், ஒவ்வொரு வரிசைக்கு உறுப்பு இருந்தது
ஒரு இணைக்கப்பட்ட பட்டியலில் தலையில் ஒரு சுட்டிக்காட்டி?
பின்னர் நாம் உருவாக்க முடியும் அந்த தொடர்புடைய பட்டியல்கள்
மற்றும், தன்னிச்சையாக அவர்கள் வளர தொடர்புடைய பட்டியல்கள் அனுமதிக்க ஏனெனில்
நாம் வளர மற்றும் இன்னும் நிறைய சுருக்க ஒரு வரிசை இல்லை விட.
அதனால் என்ன, நாம் இப்போது பயன்படுத்தினால், நாம் சரி, இந்த அந்நிய?
நாம் இந்த சங்கிலிகள் வளர ஆரம்பிக்கிறோம் இந்த வரிசை இடங்களில் இருந்து.
>> இப்போது நாம் ஒரு முடிவிலா பொருத்த முடியும் தரவு அளவு, அல்லது, எல்லையற்ற,
ஒரு தன்னிச்சையான தொகை தரவு, எங்கள் ஹாஷ் அட்டவணை
எப்போதும் எதுவும் இல்லாமல் மோதல் பிரச்சனை.
நாம் நீக்கப்பட்டிருக்கிறது இதை செய்து கொத்தாக்கலும்.
நன்றாக நாம் சேர்க்க போது என்று எனக்கு தெரியும் ஒரு இணைக்கப்பட்ட பட்டியலில், நீங்கள் நினைவு என்றால்
தனித்தனி இணைக்கப்பட்ட பட்டியல்கள், நம் வீடியோ இருந்து இணைக்கப்பட்ட பட்டியல்கள் மற்றும் இரட்டை இணைக்கப்பட்ட பட்டியல்கள்,
அது ஒரு மாறா நேரம் அறுவை சிகிச்சை தான்.
நாம் தான் முன் சேர்த்து வருகிறோம்.
>> மற்றும் பார் வரை, நன்கு நாங்கள் தெரிகிறோம் அந்த ஒரு இணைக்கப்பட்ட பட்டியலில் வரை பார்க்க
சரி, ஒரு பிரச்சினை இருக்க முடியும்?
நாம் மூலம் தேட வேண்டும் ஆரம்பத்தில் இருந்து அதை முடிவுக்கு.
எந்த சீரற்ற இருக்கிறது ஒரு இணைக்கப்பட்ட பட்டியலில் அணுகல்.
ஆனால் அதற்கு பதிலாக ஒரு கொண்ட இணைக்கப்பட்ட ஒரு தேடல் n, ஓ என்று அங்கு பட்டியலில்,
நாம் இப்போது 10 இணைக்கப்பட்ட பட்டியலில், அல்லது 1,000 இணைக்கப்பட்ட பட்டியல்கள்,
இப்போது அது 10 ஆல் வகுக்க n, ஓ, அல்லது n ஓ 1,000 வகுக்கப்பட்ட.
>> நாம் பேசிக்கொண்டிருக்கும்போதே கோட்பாட்டளவில் சிக்கலான பற்றி
நாம் உண்மையான உள்ள, மாறிலிகள் புறக்கணித்து இந்த விஷயங்கள் உண்மையில் ஒரு விஷயமே உலக,
சரியா?
நாம் உண்மையில் கவனிப்போம் இந்த நடக்கும் என்று
வேகமாக 10 முறை இயக்க வேண்டும், அல்லது 1000 மடங்கு அதிகமான,
நாங்கள் நீண்ட ஒரு விநியோகித்து ஏனெனில் 1,000 சிறிய சங்கிலிகள் முழுவதும் சங்கிலி.
எனவே நாம் ஒவ்வொரு முறை தேட நாம் முடியும் அந்த சங்கிலிகள் ஒரு வழியாக
நாங்கள் கவலைப்பட மாட்டோம் 999 சங்கிலிகள் புறக்கணிக்க பற்றி, மற்றும் அந்த வகையில் ஒரு தேடல்.
>> எந்த சராசரி உள்ளது 1000 மடங்கு குறைவாக இருக்கும்.
எனவே நாம் இன்னும், அப்படி இருக்கிறோம் இந்த சராசரி வழக்கு நோக்கி தன்மை
நிலையான நேரம் இருப்பது, ஆனால் மட்டுமே நாம் ஊக்கம் ஏனெனில்
சில பெரிய நிலையான காரணியாக பிளவு.
எப்படி இந்த வலிமை என்று பார்ப்போம், உண்மையில் என்றாலும் இருக்கிறது.
எனவே இந்த நேரத்தில் நாம் இருந்தது ஹாஷ் அட்டவணை இருந்தது நாம் ஒரு ஹாஷ் அட்டவணை அறிவித்தார் முன் அந்த
10 சரங்களை சேமித்து திறன் இருந்தது.
நாம் இனி அதை செய்ய போவதில்லை.
நாம் ஏற்கனவே தெரியும் அந்த முறையை வரம்புகள்.
இப்போது எங்கள் ஹாஷ் அட்டவணை இருக்கும் நடக்கிறது 10 முனைகளில் சுட்டிகள் ஒரு வரிசை
தொடர்புடைய பட்டியல்கள் தலைவர்கள்.
>> இப்போது அது வெற்று.
அந்த 10 சுட்டிகள் ஒவ்வொரு ஒரு பூஜ்ய உள்ளது.
எதுவும் எங்கள் இருக்கிறது இப்போது அட்டவணை புல.
>> இப்போது தான் சில வைத்து ஆரம்பிப்போம் இந்த ஹாஷ் அட்டவணை விஷயங்கள்.
மற்றும் இந்த முறை எப்படி பார்க்க அனுமதிக்க எங்களுக்கு கொஞ்சம் நன்மை செய்ய போகிறோம்.
இப்போது ஜோயி புல நாம்.
சரம் நாம் ஜோயி மூலம் இயக்க ஒரு ஹாஷ் சார்பு நாம் 6 திரும்ப.
சரி இப்போது நாம் என்ன செய்ய வேண்டும்?
>> சரி இப்போது இணைக்கப்பட்ட பட்டியல்கள் வேலை, நாம் வரிசைகள் வேலை.
நாம் பணிபுரியும் போது, இணைக்கப்பட்ட பட்டியல்கள் நாங்கள்
நாம் மாறும் தொடங்க வேண்டும் தெரிகிறது விண்வெளி மற்றும் கட்டிட சங்கிலிகள் ஒதுக்கீடு.
அந்த மாதிரியான அந்த மைய how-- தான் ஒரு இணைக்கப்பட்ட பட்டியலில் கட்டி உறுப்புகள்.
எனவே மாறும் நாம் ஜோயி இடத்தை ஒதுக்க,
பின்னர் சங்கிலி அவரை சேர்க்க.
>> எனவே இப்போது நாம் என்ன செய்தேன் பாருங்கள்.
நாங்கள் ஜோயி புல போது நாம் Hashcode 6 கிடைத்தது.
வரிசையில் இடம் 6 இப்போது சுட்டிக்காட்டி ஒரு இணைக்கப்பட்ட பட்டியலில் தலையில் காட்டுகிறார்,
இப்போது அதை மட்டும் தான் ஒரு இணைக்கப்பட்ட பட்டியலில் உறுப்பு.
அந்த முனை இணைக்கப்பட்ட பட்டியலில் ஜோயி உள்ளது.
>> நாங்கள் ஜோயி பார்க்க வேண்டும் என்றால் பின்னர், நாங்கள் தான் மீண்டும் ஜோயி புல,
நாங்கள் எங்கள் ஏனெனில் மீண்டும் 6 பெற ஹாஷ் சார்பு நிர்ணயிக்கப்பட்ட உள்ளது.
பின்னர் நாம் தலை மணிக்கு தொடங்கும் இணைக்கப்பட்ட பட்டியலில் சுட்டிக்காட்டினார்
வரிசையில் இடம் மூலம் 6, மற்றும் நாம் மீண்டும் கூறு முடியாது
ஜோயி கண்டுபிடிக்க முயற்சி என்று முழுவதும்.
நாம் கட்டினால் எங்கள் திறம்பட அட்டவணை புல,
மற்றும் எங்கள் ஹாஷ் சார்பு திறம்பட நன்கு தரவு விநியோகிக்க,
சராசரி அந்த ஒவ்வொரு இணைக்கப்பட்ட ஒவ்வொரு வரிசை இடத்தில் பட்டியல்கள்
என்றால் அளவு 1/10 இருக்கும் நாங்கள் ஒரு ஒற்றை பெரிய அதை இருந்தது
அது எல்லாம் இணைக்கப்பட்ட பட்டியல்.
>> நாம் பெரிய இணைக்கப்பட்ட அந்த விநியோகிக்க 10 இணைக்கப்பட்ட பட்டியல்கள் முழுவதும் பட்டியல்
ஒவ்வொரு பட்டியலில் 1/10 அளவு இருக்கும்.
இவ்வாறே 10 மடங்கு விரைவாக மூலம் தேட.
எனவே மீண்டும் இந்த செய்வோம்.
இப்போது ராஸ் புல நாம்.
>> மற்றும் நாம் செய்யும் போது ரோஸ், சொல்கிறேன் நாம் மீண்டும் ஹாஷ் குறியீடு 2.
சரி இப்போது நாம் மாறும் ஒரு ஒதுக்க புதிய கணு, நாம், அந்த முனை ரோஸ் வைத்தோம்
நாம் வரிசை இடம் இப்போது சொல்ல 2 பூஜ்ஜிய, அதற்கு பதிலாக,
ஒரு இணைக்கப்பட்ட தலைவர் சுட்டிக்காட்டுகிறது யாருடைய மட்டுமே முனை பட்டியலில் ரோஸ்.
நாம் செய்தால், நாம் இந்த ஒரு முறை செய்ய முடியும் ரேச்சல் புல மற்றும் Hashcode 4 பெற முடியும்.
ரேச்சல் வைத்து, ஒரு புதிய கணு malloc முனை, மற்றும் ஒரு வரிசையில் இடம் சொல்கிறது
4 இப்போது தலை சுட்டிக்காட்டினால் அதன் ஒரு இணைக்கப்பட்ட பட்டியலில்
ஒரே உறுப்பு ரேச்சல் இருக்கும் நடக்கிறது.
>> சரி ஆனால் என்ன நடக்கும் நாம் ஒரு மோதல் இல்லை?
நாம் மோதல்கள் கையாள எப்படி என்று பார்ப்போம் தனி பிணைப்பு முறையை பயன்படுத்தி.
தான் ஃபோ புல நாம்.
நாம் Hashcode 6 கிடைக்கும்.
எங்கள் முந்தைய எடுத்துக்காட்டாக நாம் இருந்தனர் வரிசை சரங்களை சேமிக்கும்.
இந்த பிரச்சனை இருந்தது.
>> நாம் மெழுகுதல் விரும்பவில்லை ஜோயி, மற்றும் நாம் ஏற்கனவே போயிருக்கின்றன
நாம் சில கொத்தாக்கலும் பெற முடியும் என்று நான் பிரச்சினைகள் நாங்கள் முயற்சி செய்தால் மற்றும் படி
மூலம் மற்றும் probe.
ஆனால் என்ன நாம் வெறும் வகையான இந்த உரிமை, அதே வழியில் நடத்துகிறாய்?
அது ஒரு உறுப்பு சேர்த்து போல ஒரு இணைக்கப்பட்ட பட்டியலில் தலையில்.
ஃபோ க்கான தான் malloc இடத்தில் நாம்.
>> நாம் ஃபோ அடுத்த சுட்டிக்காட்டி புள்ளிகள் சொல்ல வேண்டும் இணைக்கப்பட்ட பட்டியலில் பழைய தலையில்,
பின்னர் 6 வெறும் சுட்டிக்காட்டினால் இணைக்கப்பட்ட பட்டியலில் புதிய தலைவர்.
இப்போது நாம் ஃபோ மாறிவிட்டேன் இருக்கிறது.
நாம் இப்போது இரண்டு சேமிக்க முடியும் Hashcode 6 உறுப்புகள்,
மற்றும் நாம் எந்த பிரச்சினையும் இல்லை.
>> அந்த அழகான மிகவும் இருக்கிறது பிணைப்பு உள்ளது.
மற்றும் பிணைப்பு நிச்சயம் என்று முறை
நீங்கள் என்றால் மிகவும் பயனுள்ள இருக்க போகிறது நீங்கள் ஒரு ஹாஷ் அட்டவணை தரவு சேமித்து.
ஆனால் இந்த கலவையை வரிசைகள் மற்றும் தொடர்புடைய பட்டியல்கள்
ஒன்றாக உண்மையில் ஒரு ஹாஷ் அட்டவணை அமைக்க திடீரென்று உங்கள் திறனை அதிகரிக்கிறது
தரவு பெரிய அளவு சேமிக்க, மற்றும் மிகவும் விரைவாகவும் திறமையாகவும் தேட
தரவு மூலம்.
>> இன்னும் ஒரு இன்னும் இருக்கிறது அங்கு தரவு கட்டமைப்பு
என்று கூட ஒரு பிட் இருக்கலாம் உத்தரவாதம் அடிப்படையில் சிறந்த
என்று எங்கள் புகுத்தியது, நீக்கல், மற்றும் பார்க்க முறை கூட வேகமாக இருக்கும்.
மற்றும் நாம் முயற்சிகளின் ஒரு வீடியோ பார்க்க வேண்டும் என்று.
நான் டக் லாயிட் நான், இந்த CS50 உள்ளது.