[సంగీతాన్ని] డౌ LLOYD: ఇప్పుడు ద్వారా మీరు శ్రేణుల గురించి చాలా తెలుసు, మరియు మీరు లింక్ జాబితాలు గురించి చాలా తెలుసు. మరియు మేము చర్చించడానికి చేసిన రెండింటికీ, మేము చేసిన జాబితాలు లింక్ చర్చించారు పెద్ద మరియు చిన్న పొందవచ్చు, కానీ వారు ఎక్కువ పరిమాణం పడుతుంది. శ్రేణుల మరింత సూటిగా ఉంటాయి ఉపయోగిస్తాయి, కానీ వారు చాలా మితమైన ఉన్నాము మేము పరిమాణం సెట్ కలిగి చాలా ప్రారంభంలో శ్రేణి మరియు తర్వాత మేము అది ఇరుక్కుపోయి ఉన్నాం. 

కానీ మేము చాలా చక్కని చేసిన, వార్తలు మా అంశాలు అన్ని అయిపోయిన లింక్ జాబితాలు మరియు శ్రేణుల గురించి. లేదా మేము ఉందా? బహుశా మేము ఏదో ఒకటి చెయ్యాలి మరింత సృజనాత్మక. ని ఇస్తుంది ఆ విధమైన ఒక హాష్ పట్టిక ఆలోచన. 

సో ఒక హాష్ పట్టిక లో మేము ప్రయత్నించండి చూడాలని ఒక లింక్ జాబితాను వ్యూహం మిళితం. మేము ప్రయోజనాలు తీసుకుని వెళుతున్నాం యెరే యొక్క, రాండమ్ యాక్సెస్ వంటి, కేవలం శ్రేణి వెళ్ళి సామర్థ్యం మూలకం 4 లేదా శ్రేణి మూలకం 8 అంతటా iterate చేయకుండా. కుడివైపు, అందంగా ఫాస్ట్? 

కానీ మేము కూడా మా డేటా కలిగి అనుకుంటున్నారా నిర్మాణం పెరుగుతాయి మరియు కుదించే చెయ్యగలరు. మేము లేదు, అవసరం లేదు నిరోధించబడుతుంది అనుకుంటున్నారా. మరియు మేము చెయ్యగలరు అనుకుంటున్నారా జోడించవచ్చు మరియు విషయాలను తొలగించాలి చాలా సులభంగా, మీరు గుర్తు ఉంటే, వ్యూహం తో చాలా సంక్లిష్టంగా ఉంటుంది. మరియు మేము ఈ కాల్ చేయవచ్చు కొత్త విషయం ఒక హాష్ పట్టిక. 

మరియు ఉంటే, సరిగ్గా అమలు మేము విధమైన వేస్తున్నాము రెండు డేటా యొక్క ప్రయోజనాలు మీరు ఇప్పటికే చూసిన నిర్మాణాలు, శ్రేణుల మరియు అనుసంధాన జాబితాలు. చొప్పించడం ప్రారంభించవచ్చు 1 తీటా వైపు ఉంటాయి. తీటా మేము నిజంగా చర్చించారు లేదు, కానీ తీటా కేవలం సగటు సందర్భంలో, ఏమి నిజానికి జరిగే అవకాశముంది. మీరు ఎల్లప్పుడూ వెళ్ళి లేదు చెత్త దృష్టాంత కలిగి, మరియు మీరు ఎల్లప్పుడూ ఏమీ ఉండదని చేస్తున్నారు ఉత్తమ దృష్టాంతంలో, కాబట్టి ఏమిటి సగటు దృష్టాంతంలో? 

బాగా సగటున చొప్పించడం ఒక హాష్ పట్టిక లోకి దగ్గరగా స్థిరంగా సమయం ను ప్రారంభించవచ్చు. మరియు తొలగింపు పొందవచ్చు స్థిరంగా సమయం దగ్గరగా. మరియు లుక్అప్ పొందవచ్చు స్థిరంగా సమయం దగ్గరగా. That's-- మేము ఒక డేటా లేదు నిర్మాణం ఇంకా ఆ ఆ చేయవచ్చు, అందువలన ఈ అప్పటికే ధ్వనులు ఒక అందమైన గొప్ప దానిలా. మేము నిజంగా తగ్గించవచ్చని చేసిన దాని స్వంత ప్రతి అప్రయోజనాలు. 

ఈ ప్రదర్శన పొందుటకు అయితే మేము అప్గ్రేడ్ మేము జోడించడానికి ఎలా పునరాలోచనలో అవసరం నిర్మాణాన్ని డేటా. ముఖ్యంగా మేము కావలసిన డేటా స్వయంగా మాకు చెప్పడం అది ఎక్కడ నిర్మాణం లో వెళ్ళాలి. అప్పుడు మేము అది ఉంటే చూడండి అవసరం ఉంటే నిర్మాణం, మేము దానిని కనుగొనేందుకు అవసరం ఉంటే, మేము డేటా వద్ద వెళ్లాలనుకుంటున్నాను మళ్లీ సమర్థవంతంగా చెయ్యగలరు, డేటా ఉపయోగించి, యాదృచ్చికంగా అది యాక్సెస్. జస్ట్ చూడటం ద్వారా డేటా మేము ఉండాలి ఖచ్చితంగా మేము ఉన్నాము పేరు ఒక ఆలోచన హాష్ పట్టిక లో దానిని కనుగొనేందుకు వెళ్ళడం. 

ఒక హాష్ ఇప్పుడు ఇబ్బంది పట్టిక వారు నిజంగా ఉన్నట్లు ఉంది ఆర్దరింగ్ లేదా డేటా సార్టింగ్ వద్ద అందంగా చెడు. నిజానికి, మీరు మొదలు ఉంటే ఆర్డర్ లేదా విధమైన వాటిని ఉపయోగించడానికి డేటా మీరు అన్ని కోల్పోతారు ప్రయోజనాలు గతంలో మీరు చొప్పించడం మరియు తొలగింపు పరంగా వచ్చింది. సమయానికి దగ్గరగా అవుతుంది n యొక్క తీటా, మరియు మేము ప్రధానంగా చేసిన ఒక లింక్ జాబితా వెనుకబడ్డ. అందువలన మేము మాత్రమే హాష్ ఉపయోగించడానికి కావలసిన పట్టికలు మేము గురించి శ్రద్ధ లేకపోతే డేటా క్రమబద్ధీకరించబడింది లేదో. సందర్భానికి దీనిలో మీరు CS50 వాటిని ఉపయోగిస్తాము మీరు బహుశా పట్టించుకోను డేటా క్రమబద్ధీకరించబడింది ఆ. 

సో ఒక హాష్ పట్టిక కలయిక రెండు విభిన్న ముక్కలు తో మేము తెలిసి. మొదటి ఒక ఫంక్షన్, ఇది మేము సాధారణంగా ఒక హాష్ ఫంక్షన్ కాల్. మరియు హాష్ ఫంక్షన్ను అన్నారు కొన్ని కాని ప్రతికూల పూర్ణాంక తిరిగి ఇది మేము సాధారణంగా సరే, ఒక హ్యాష్కోడ్ కాల్? రెండవ ముక్క ఇది వ్యూహం ఉంది రకం మనం యొక్క నిల్వ డేటా సామర్థ్యం డేటా నిర్మాణాన్ని ఉంచాలనుకుంటే. మేము ఆపి చేస్తాము ఇప్పుడు జాబితాలో మూలకం లింక్ మరియు కేవలం ఒక పునాదులను ప్రారంభం అది చుట్టూ మీ తల పొందడానికి పట్టిక హాష్, ఆపై మేము ఉండవచ్చు వీచు చేస్తాము మీ మనస్సు కొద్దిగా ఉన్నప్పుడు మేము కలిసి శ్రేణుల మరియు లింక్ జాబితాలు కలిపి. 

ప్రాథమిక ఆలోచన అయితే మేము కొన్ని డేటా పడుతుంది ఉంది. మేము ఆ డేటా ద్వారా అమలు హాష్ ఫంక్షన్. అందువలన డేటా ప్రాసెస్ మరియు అది సరే, ఒక సంఖ్య ఉమ్మి వేస్తారు? ఆపై ఆ సంఖ్య మేము కేవలం డేటా నిల్వ మేము నిల్వ అనుకుంటున్నారా ఆ స్థానంలో శ్రేణి. ఉదాహరణకు మేము ఉండవచ్చు కలిగి తీగలను యొక్క ఈ హాష్ పట్టిక. అది, అది 10 అంశాలను సంపాదించి మేము అది 10 తీగలను ఇముడుతుంది. 

యొక్క మేము జాన్ హాష్ అనుకుందాం. జాన్ కాబట్టి డేటా వంటి మేము ఇన్సర్ట్ అనుకుంటే ఎక్కడో ఈ హాష్ పట్టిక లోకి. మనం ఎక్కడ ఉంచగలను? బాగా సాధారణంగా ఒక అర్రే ఇప్పటివరకు మేము బహుశా శ్రేణి స్థానంలో 0 లో ఉంచుతాడు. కానీ ఇప్పుడు మేము ఈ కొత్త హాష్ ఫంక్షన్ కలిగి. 

మరియు మేము జాన్ అమలు అని పిలవబడు ఈ హాష్ ఫంక్షన్ ద్వారా మరియు అది 4 ఉమ్మి వేస్తారు లో. మేము ఉన్నాము పేరు బాగా ఆ జాన్ ఉంచాలి కావలసిన వెళుతున్న. మేము శ్రేణి ప్రదేశంలో జాన్ ఉంచాలి కావలసిన 4, మేము మళ్ళీ జాన్ హాష్ ఉంటే ఎందుకంటే యొక్క తరువాత మేము చెప్పటానికి వీలు అన్వేషణ మరియు చూడాలనుకుంటే దీనిద్వారా హాష్ ఉన్నట్లయితే మేము చెయ్యాల్సిన అన్ని పట్టిక అదే హాష్ ద్వారా అమలు ఉంటుంది ఫంక్షన్, సంఖ్య 4 నుంచి మరియు జాన్ కనుగొనేందుకు చెయ్యగలరు వెంటనే మా డేటా నిర్మాణం. ఆ అందమైన మంచి వార్తలు. 

యొక్క మేము ఇప్పుడు దీన్ని పిలవబడు మళ్ళీ, మేము పాల్ హాష్ అనుకుంటున్నారా. మేము పాల్ జోడించాలనుకుంటే ఈ హాష్ పట్టిక లోకి. యొక్క ఈ సమయంలో మేము అమలు అని పిలవబడు హాష్ ఫంక్షన్ ద్వారా పాల్, ఉత్పత్తి అని హ్యాష్కోడ్ 6 ఉంది. Well ఇప్పుడు మేము పాల్ ఉంచవచ్చు అర్రే నగర 6 లో. మరియు మేము అని చూసేందుకు అవసరం ఉంటే పాల్ ఈ హాష్ పట్టిక ఉంది, మేము చెయ్యాల్సిన అన్ని పాల్ నడుపుతుంది హాష్ ఫంక్షన్ ద్వారా మళ్ళీ మరియు మేము మళ్లీ 6 పొందడానికి వెళుతున్న. 

మరియు తర్వాత మేము కేవలం చూడండి అర్రే నగర 6. పాల్ ఉంది? ఇలా అయితే, అతను హాష్ పట్టిక ఉంది. పాల్ లేదు? అతను హాష్ పట్టిక లో కాదు. ఇది చాలా సూటిగా ఉంది. 

ఇప్పుడు ఎలా మీరు ఒక హాష్ ఫంక్షన్ నిర్వచించే చెయ్యాలి? బాగా నిజంగా ఏ పరిమితి లేదు సాధ్యం హాష్ విధులు సంఖ్య. నిజానికి ఒక సంఖ్య, నిజంగా ఉంది ఇంటర్నెట్ లో మంచి వాటిని. ఒక సంఖ్య, నిజంగా ఉంది ఇంటర్నెట్ లో నిజంగా చెడు వాటిని. ఇది కూడా అందంగా సులభం ఒక చెడ్డ రాయడానికి. 

సో వాట్ ఒక మంచి అప్ చేస్తుంది హాష్ ఫంక్షన్, కుడి? Well ఒక మంచి హాష్ ఫంక్షన్ను తప్పక మాత్రమే డేటా హ్యాష్ చేస్తున్నారు ఉపయోగించండి మరియు డేటా యొక్క అన్ని హ్యాష్ చేస్తున్నారు. కాబట్టి మేము ఏదైనా ఉపయోగించడానికి వద్దు మేము ఏదైనా పొందుపరచడానికి లేదు డేటా కంటే ఇతర else. మరియు మేము డేటా అన్ని ఉపయోగించాలనుకుంటున్నాను. మేము కేవలం ఒక భాగాన్ని ఉపయోగించడానికి వద్దు అది, మేము అది అన్ని ఉపయోగించాలనుకుంటున్నాను. ఒక హాష్ ఫంక్షన్ను తప్పక కూడా నిర్ణాయక ఉండాలి. ఆ అర్థం ఏమిటి? బాగా అర్థం ప్రతిసారీ మేము డేటా యొక్క ఖచ్చితమైన అదే ముక్క పాస్ హాష్ ఫంక్షన్ మేము ఎల్లప్పుడూ అదే హ్యాష్కోడ్ అవుట్. నేను లోకి జాన్ పాస్ ఉంటే హాష్ ఫంక్షన్ను నేను 4 అవుట్. నేను అలా ఉండాలి 10,000 సార్లు మరియు నేను ఎల్లప్పుడూ 4 పొందుతారు. కాబట్టి ఎటువంటి యాదృచ్ఛిక సంఖ్యలు సమర్థవంతంగా మా హాష్ చేరి ఉంటాయి tables-- మా హాష్ విధులు. 

ఒక హాష్ ఫంక్షన్ను కూడా ప్రార్థించాలి ఒకే డేటా పంపిణీ. ప్రతిసారీ మీరు ద్వారా డేటాను అమలు చేస్తే హాష్ ఫంక్షన్ను మీరు హ్యాష్కోడ్ 0 పొందడానికి ఆ కుడి, బహుశా చాలా గొప్పది కాదు? మీరు బహుశా పెద్ద కావలసిన హాష్ సంకేతాలు శ్రేణులు. కూడా విషయాలు వ్యాప్తి చేయవచ్చు పట్టిక అంతటా. మరియు కూడా ఉంటే నిజంగా గొప్ప విషయం జాన్ మరియు జోనాథన్ ఇట్లాంటి డేటా, బహుశా బరువును వ్యాపించి చేశారు హాష్ పట్టిక లో వివిధ ప్రాంతాల్లో. ఒక nice ప్రయోజనం ఉంటుంది. 

ఇక్కడ ఒక హాష్ ఫంక్షన్ యొక్క ఒక ఉదాహరణ ఉంది. నేను ముందు ఈ ఒక అప్ రాశారు. ఇది ఒక ముఖ్యంగా కాదు మంచి హాష్ ఫంక్షన్ నిజంగా చేయలేని కారణాల ప్రస్తుతం వెళ్లడానికి భరించలేదని. కానీ మీరు ఇక్కడ ఏం జరగబోతోంది చూస్తారు? మేము ఒక వేరియబుల్ ప్రకటించారు చేస్తున్న ఉన్నట్లు కనిపిస్తోంది మొత్తం మరియు 0 సమానంగా సెట్ అని. ఆపై స్పష్టంగా నేను ఏదో చేయడం వెబ్ చాలా కాలం strstr [j] సమానం కాదు 0 బ్యాక్స్లాష్ కు. నేను అక్కడ ఏమి చేస్తున్నాను? 

ఈ ప్రాథమికంగా కేవలం మరొక [అమలు మార్గం? strl?] మీరు చేసిన ఎప్పుడు గుర్తించే స్ట్రింగ్ ముగింపు చేరుకుంది. నేను నిజానికి లేదు స్ట్రింగ్ యొక్క పొడవు లెక్కించవచ్చు, నేను తాకినప్పుడు నేను కేవలం ఉపయోగించి వెబ్ బాక్ స్లాష్ 0 పాత్ర నాకు తెలుసు నేను స్ట్రింగ్ ముగింపు చేరుకున్నారు. ఆపై నేను ఉంచడానికి వెళుతున్న ఆ స్ట్రింగ్ ద్వారా iterating, strstr [j] జోడించడం అప్పుడు సంకలనం, మరియు రోజు చివరిలో మొత్తం mod తిరిగి వెళుతున్న HASH_MAX. 

ప్రధానంగా అన్ని ఈ హాష్ ఫంక్షన్ జోడించడం చేస్తోంది యొక్క ASCII విలువలు అన్ని నా స్ట్రింగ్, మరియు అప్పుడు అది కొన్ని హ్యాష్కోడ్ తిరిగి HASH_MAX ద్వారా modded. ఇది బహుశా పరిమాణం నా శ్రేణి, కుడి? నేను హాష్ పంపబడతాయి వద్దు సంకేతాలు నా అర్రే పరిమాణం 10 యొక్క ఉంటే, నేను పొందుతున్నాను ఉండాలనుకుంటున్నాను లేదు బయటకు హాష్ సంకేతాలు 11, 12, 13 నేను లోకి విషయాలు చాలు కాదు అర్రే ఆ స్థానాలు, ఆ అక్రమ ఉంటుంది. నేను ఒక విభజన లోపంగా బాధపడుతున్నారు ఇష్టం. 

ఇప్పుడు ఇక్కడ మరొక శీఘ్ర పక్కన ఉంటుంది. సాధారణంగా మీరు బహుశా వెళ్ళడం లేదు చేస్తున్నాం మీ స్వంత హాష్ విధులు రాయాలనుకుంటున్నాను. ఇది నిజానికి ఒక బిట్ ఉంది ఒక కళ, ఒక శాస్త్రం. మరియు వాటిని లోకి వెళ్ళిపోతుంది ఆ చాలా ఉంది. నేను అన్నాడు వంటి ఇంటర్నెట్, పూర్తి నిజంగా మంచి హాష్ విధులు, మరియు మీరు ఇంటర్నెట్ వాడాలి ఇది నిజంగా ఎందుకంటే హాష్ విధులు కేవలం రకమైన ఒక అనవసరమైన సమయం వేస్ట్ మీ సొంత సృష్టించడానికి. 

మీరు సాధారణ వాటిని వ్రాయగలరు పరీక్ష ప్రయోజనాల కోసం. కానీ మీరు నిజంగా వెళుతున్న చేసినప్పుడు డేటా హ్యాషింగ్ మరియు అది నిల్వ మొదలు మీరు ఒక హాష్ పట్టిక లోకి బహుశా కావలసిన వెళుతున్న ఉత్పత్తి చేశారు కొన్ని ఫంక్షన్ ఉపయోగించడానికి మీరు ఈ, ఆ ఇంటర్నెట్ లో వున్నది. మీరు కేవలం ఖచ్చితంగా లేకపోతే మీ మూలాలను పేర్కొనండి. ఎటువంటి కారణం ఉంది ఇక్కడ ఏదైనా Plagiarize. 

కంప్యూటర్ సైన్స్ కమ్యూనిటీ ఖచ్చితంగా విలువలు పెరుగుతున్న, మరియు నిజంగా ఓపెన్ సోర్స్, మరియు అది నిజంగా ముఖ్యం మీ మూలాలను పేర్కొనండి కాబట్టి ప్రజలు కోసం ఆపాదింపు పొందవచ్చు వారు ఉన్నట్లు పని సమాజ లాభం చేస్తున్న. కాబట్టి ఎల్లప్పుడూ sure-- ఉంటుంది మరియు కేవలం హాష్ కోసం విధులు, కానీ సాధారణంగా ఉన్నప్పుడు మీరు బాహ్య మూలం నుండి కోడ్ ఉపయోగించండి ఎల్లప్పుడూ మీ మూలం cite. చేసిన వ్యక్తి క్రెడిట్ ఇవ్వాలని పని కొన్ని కాబట్టి మీరు కలిగి లేదు. 

సరే అలా యొక్క ఈ సందర్శించండి వీలు రెండవ హాష్ పట్టిక. మేము వదిలి ఇక్కడ ఈ ఉంది మేము చేర్చబడ్డ తర్వాత ఆఫ్ ఈ హాష్ పట్టిక లోకి జాన్ మరియు పాల్. మీరు ఇక్కడ ఒక సమస్య చూస్తారు? మీరు రెండు చూడవచ్చు. కానీ ముఖ్యంగా, మీరు ఈ సాధ్యం సమస్య చూడండి? 

నేను రింగో హాష్, మరియు అది ఉంటే తర్వాత ప్రాసెసిసంగ్ అవుతుంది హాష్ ఫంక్షన్ ద్వారా డేటా రింగో కూడా హ్యాష్కోడ్ 6 ఉత్పత్తి. నేను ఇప్పటికే వద్ద డేటా పొందాను hashcode-- శ్రేణి నగర 6. కనుక ఇది బహుశా ఒక బిట్ చేస్తాడు ఇప్పుడు నాకు ఒక సమస్య కారణంగా, కుడి? 

మేము ఢీకొట్టడంతో కాల్. మరియు తాకిడి రెండు సంభవిస్తుంది డేటా ముక్కలు అదే హాష్ ద్వారా అమలు ఫంక్షన్ అదే హ్యాష్కోడ్ కారణమవుతాయి. బహుశా మేము ఇప్పటికీ రెండు పొందాలనుకోవడం హాష్ పట్టిక లోకి డేటా ముక్కలు, లేకుంటే మేము రింగో నడుస్తున్న కాదు ఏకపక్ష హాష్ ఫంక్షన్ ద్వారా. మేము బహుశా పొందాలనుకోవడం ఆ శ్రేణి రింగో. 

మేము అయితే దీన్ని ఎలా, అతడికి మరియు పాల్ రెండు దిగుబడి హ్యాష్కోడ్ 6? మేము పాల్ తిరిగి రాస్తుంది వద్దు, మేము పౌలు కూడా అక్కడ ఉండాలనుకుంటున్నాను. కాబట్టి మేము పొందుటకు ఒక మార్గం కనుగొనేందుకు అవసరం హాష్ పట్టిక లోకి అంశాలు ఇప్పటికీ మా శీఘ్ర సంరక్షిస్తుంది చొప్పించడం మరియు శీఘ్ర లుక్ అప్. మరియు అది ఎదుర్కోవటానికి ఒక మార్గం ఉంది ఛేదించి సరళ అని ఏదో ఒకటి. 

మేము ఒక కలిగి ఉంటే ఈ పద్ధతిని ఉపయోగించి తాకిడి, బాగా, మేము ఏమి చేస్తారు? మనము శ్రేణి నగర అతడిని కాదు 6, లేదా సంసార హ్యాష్కోడ్ ఉత్పత్తి, యొక్క హ్యాష్కోడ్ ప్లస్ 1 వద్ద అతడిని తెలియజేయండి. మరియు ఆ పూర్తి లెట్స్ ఉంటే హ్యాష్కోడ్ ప్లస్ 2 లో అతడిని. ఈ జీవి యొక్క ప్రయోజనం ఉంటే సరిగ్గా మేము అతను భావించే పేరు మరియు మేము శోధించవచ్చు ఉంటాయి, బహుశా మేము చాలా దూరం వెళ్ళి లేదు. బహుశా మేము శోధించడానికి కలిగి లేదు హాష్ పట్టిక అన్ని n మూలకాలు. బహుశా మేము శోధించడానికి కలిగి వాటిని ఒక జంట. 

కాబట్టి మేము ఇంకా వైపు తీర్చ చేస్తున్నారు సగటు కేసు 1 దగ్గరగా vs ఉండటం n కు దగ్గరగా, కాబట్టి బహుశా ఆ పని చేస్తాము. కాబట్టి యొక్క ఈ ఎలా చూద్దాం వాస్తవానికి బయటకు పనిచేయవచ్చు. మరియు బహుశా మేము గుర్తించడం లేదో యొక్క చూసేలా ఇక్కడ జరగవచ్చు ఆ సమస్య. 

యొక్క మేము బార్ట్ హాష్ అనుకోండి. కాబట్టి ఇప్పుడు మేము ఒక కొత్త సెట్ అమలు చూడాలని హాష్ ఫంక్షన్ ద్వారా తంత్రుల మరియు మేము హాష్ ద్వారా బార్ట్ అమలు ఫంక్షన్, మేము హ్యాష్కోడ్ 6 పొందండి. మేము పరిశీలించి, మేము 6 చూడండి ఖాళీ, కాబట్టి మేము అక్కడ బార్ట్ ఉంచవచ్చు. 

ఇప్పుడు మేము లిసా మరియు హాష్ కూడా హ్యాష్కోడ్ 6 ఉత్పత్తి. Well ఇప్పుడు మేము ఈ ఉపయోగించి చేస్తున్న సరళ మేము 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 వ జోడిస్తే మేము వాటిని ఉంచడానికి లేదు. మేము కేవలం చుట్టూ తిరుగుతూ కాలేదు వృత్తాలు, ఒక ఖాళీ ప్రదేశం కనుగొనేందుకు ప్రయత్నిస్తున్న మరియు మేము ఉండవచ్చు కూరుకుపోయి ఒక అనంతమైన లూప్. 

సో ఆలోచన ఇస్తుంది ఈ విధమైన ఏదో కూర్పికం అని. మరియు ఈ మేము తీసుకుని వెళుతున్న ఉంది తిరిగి రంగంమీదికి లింక్ జాబితాలు. ఏం బదులుగా కేవలం నిల్వ శ్రేణి లో డేటా కూడా అర్రే ప్రతి మూలకం అనుకొనుట బహుళ ముక్కలు డేటా పట్టుకోండి? Well ఆ కుడి, అర్ధవంతం లేదు? మేము ఒక అర్రే మాత్రమే తెలుసు వ్యూహం యొక్క ప్రతి మూలకం hold-- ఒకే ముక్క జరపవచ్చని డేటా రకం డేటా. 

కానీ ఏం డేటా రకం ఒక లింక్ జాబితా, కుడి ఉంది? సో వాట్ ఉంటే ప్రతి శ్రేణి యొక్క మూలకం ఉంది ఒక లింక్ జాబితా యొక్క తల ఒక పాయింటర్ ఉంది? మరియు తర్వాత మేము నిర్మించేందుకు ఆ లింక్ జాబితాలు మరియు, నిరంకుశంగా పెరుగుతాయి లింక్ జాబితాలు అనుమతిస్తుంది ఎందుకంటే మాకు పెరుగుతాయి మరియు మరింత చాలా తగ్గిపోవటం వ్యూహం చేస్తుంది తేలికగా కంటే. కాబట్టి మనం ఇప్పుడు ఉపయోగిస్తే, మేము కుడి, ఈ పరపతి? మేము ఈ గొలుసులు పెరగడం ప్రారంభమవుతుందని ఈ అర్రే స్థానాలను బయటకు. 

ఇప్పుడు మేము ఒక అనంతం ఇముడుతుంది మొత్తం డేటా లేదా అనంతం కాదు, స్వతంత్రమైన మొత్తం డేటా మా హాష్ పట్టిక లోకి ఎప్పుడూ నడుస్తున్నట్లు లేకుండా తాకిడి సమస్య. మేము కూడా తొలగించింది చేసిన ఇలా చేయడం ద్వారా క్లస్టరింగ్. బాగా మేము ఇన్సర్ట్ ఉన్నప్పుడు తెలుసు ఒక లింక్ జాబితా, మీరు గుర్తు ఉంటే ఒక్కొక్కటిగా లింక్ జాబితాలు మా వీడియో నుండి లింక్ జాబితాలు మరియు రెట్టింపైన అనుసంధాన జాబితాలు అది స్థిరమైన సమయం ఆపరేషన్ ఉంది. మేము ముందు జోడించడం చేస్తున్నారు. 

మరియు లుక్ అప్ కోసం, బాగా మేము తెలుసు ఒక లింక్ జాబితాలో చూసేందుకు కుడి, ఒక సమస్య కావచ్చు? మేము శోధించుటకు అవకాశం ప్రారంభం నుండి అంతం. ఎటువంటి యాదృచ్ఛిక ఉంది అనుసందానించబడ్డ జాబితాలో యాక్సెస్. కానీ బదులుగా ఒక కలిగి అనుసంధాన ఒక లుక్అప్ n యొక్క O ఉండగల జాబితా మేము ఇప్పుడు 10 అనుసంధాన జాబితాలు ఉన్నాయి, లేదా 1,000 అనుసంధాన జాబితాలు ఇప్పుడు అది 10 ద్వారా విభజించబడింది n యొక్క O, లేదా n యొక్క O 1,000 ద్వారా విభజించబడింది. 

మరియు మేము మాట్లాడుతూ ఉండగా సిద్ధాంతపరంగా సంక్లిష్టత గురించి మేము నిజమైన లో, స్థిరాంకాలు పట్టించుకోకుండా ఈ విషయాలు నిజానికి పట్టింపు ప్రపంచ కుడి? మేము నిజానికి గమనించే జరుగుతుందంటే వేగంగా 10 సార్లు అమలు, లేదా 1,000 సార్లు వేగంగా, మేము దీర్ఘ ఒక పంపిణీ ఉన్నందున 1,000 చిన్న గొలుసులు అంతటా గొలుసు. కాబట్టి మనం ప్రతిసారీ శోధించడానికి మేము ఆ గొలుసులు ఒకటి ద్వారా మేము పట్టించుకోను 999 గొలుసులు పట్టించుకోకుండా గురించి, మరియు కేవలం ఒక శోధన. 

ఇది సగటున ఉంది 1,000 సార్లు తక్కువ ఉంటుంది. కాబట్టి మేము ఇంకా విధమైన ఉంటాయి ఈ సగటు కేసు వైపు తీర్చ నిరంతరం సమయం ఉండటం, కానీ మాత్రమే మేము పరపతి ఎందుకంటే కొన్ని భారీ స్థిరమైన అంశం ద్వారా విభజించడం. ఎలా ఈ ఉండవచ్చు చూద్దాం అయితే వాస్తవానికి చూడండి. కాబట్టి ఈ మేము కలిగి హాష్ పట్టిక ఉంది మేము ఒక హాష్ పట్టిక ప్రకటించక ముందు ఆ 10 తీగలను నిల్వ సామర్థ్యాన్ని కలిగి ఉంది. మేము ఇకపై ఆ చేయబోవడం లేదు. మేము ఇప్పటికే తెలుసు ఆ పద్ధతి యొక్క పరిమితులు. ఇప్పుడు మా హాష్ పట్టిక చేస్తాడు 10 నోడ్స్, గమనికలు యొక్క వ్యూహం లింక్ జాబితాలు ముఖ్యులకు. 

మరియు ప్రస్తుతం అది శూన్య. ఆ 10 గమనికలు ప్రతి ఒకటి NULL. ఏమీ మా లో ఉంది ప్రస్తుతం పట్టిక హాష్. 

ఇప్పుడు కొన్ని చాలు ప్రారంభిద్దాం ఈ హాష్ పట్టిక లోకి విషయాలు. మరియు యొక్క ఈ పద్ధతి ఎలా ఉందో ఇప్పుడు చూద్దాం మాకు కొద్దిగా ప్రయోజనం వెళ్తున్నారు. ఇప్పుడు జోయి హాష్ లెట్. మేము స్ట్రింగ్ జోయి ద్వారా అమలు చేస్తాము ఒక హాష్ ఫంక్షన్ మరియు మేము 6 తిరిగి. మనము ఇప్పుడు ఏమి చేస్తారు? 

Well ఇప్పుడు లింక్ జాబితాలు పని, మేము శ్రేణుల పని లేదు. మరియు మేము పని చేసినప్పుడు లింక్ జాబితాలు మేము మేము డైనమిక్ ప్రారంభించడానికి అవసరం తెలుసు స్పేస్ మరియు భవనం గొలుసులు పెడుతోంది. ఆ విధమైన ఆ ప్రధానమైనవి లేదు ఎలా వార్తలు ఒక లింక్ జాబితా నిర్మించే అంశాలు. కాబట్టి డైనమిక్ చేసుకుందాం జోయి స్థలాన్ని కేటాయించాలని, ఆపై యొక్క గొలుసు అతన్ని జోడించడానికి అనుమతిస్తుంది. 

కాబట్టి ఇప్పుడు మేము చేసిన ఏమి చూడండి. మేము జోయి హాష్ చేసినప్పుడు మేము హ్యాష్కోడ్ 6 వచ్చింది. అర్రే నగర 6 వద్ద ఇప్పుడు పాయింటర్ ఒక లింక్ జాబితా యొక్క తల పాయింట్లు, మరియు ప్రస్తుతం ఇది మాత్రమే ఒక లింక్ జాబితా మూలకం. మరియు ఆ నోడ్ లింక్ జాబితా జోయి ఉంది. 

మేము జోయి చూడవలసిన అవసరం చేస్తే తరువాత, మేము మళ్ళీ జోయి హాష్, మేము మా ఎందుకంటే మళ్ళీ 6 పొందండి హాష్ ఫంక్షన్ నిర్ణయించలేము. మరియు తర్వాత మేము తల వద్ద మొదలు లింక్ జాబితా చూపారు అర్రే నగర ద్వారా 6, మరియు మేము iterate చేయవచ్చు జోయి కనుగొనేందుకు ప్రయత్నిస్తున్న ఆ అంతటా. మరియు మేము నిర్మించడానికి ఉంటే మా సమర్థవంతంగా పట్టిక హాష్, మరియు మా హాష్ ఫంక్షన్ను సమర్థవంతంగా బాగా డేటా పంపిణీ, సగటున ఆ ప్రతి లింక్ ప్రతి శ్రేణి స్థానంలో జాబితాలు ఉంటే యొక్క పరిమాణం 1/10 ఉంటుంది మేము కేవలం ఒకే ఒక్క పెద్ద గా వచ్చింది అది ప్రతిదీ ముడిపడి జాబితా. 

మేము భారీ ముడిపడి పంపిణీ ఉంటే 10 అనుసంధాన జాబితాలు అంతటా జాబితా ప్రతి జాబితా 1/10 పరిమాణం ఉంటుంది. అందుచేత 10 సార్లు వేగంగా ద్వారా అన్వేషణ. కాబట్టి మళ్ళీ దీన్ని చూద్దాం. ఇప్పుడు రాస్ హాష్ లెట్. 

మరియు మేము అలా ఉన్నప్పుడు రాస్, పిలవబడు మేము తిరిగి హాష్ కోడ్ను 2. Well ఇప్పుడు మేము డైనమిక్ ఒక కేటాయించాలని కొత్త నోడ్, మేము ఆ నోడ్ లో రాస్ చాలు మేము శ్రేణి నగర ఇప్పుడు చెప్పండి 2, శూన్యం సూచించే బదులుగా, ఒక లింక్ యొక్క తల చూపాడు దీని మాత్రమే నోడ్ జాబితా రోస్. మరియు మేము ఈ మరొకసారి చేయవచ్చు రాచెల్ హాష్ మరియు హ్యాష్కోడ్ 4 పొందవచ్చు. రాచెల్ పెట్టి, ఒక కొత్త నోడ్ malloc నోడ్, మరియు ఒక శ్రేణి నగర చెప్పటానికి 4 ఇప్పుడు తల చూపాడు దీని ఒక లింక్ జాబితా మాత్రమే మూలకం రాచెల్ నిర్మాణము. 

సరే కానీ ఏం జరుగుతుంది మేము ఢీకొట్టడంతో? యొక్క మేము ప్రమాదాలలో నిర్వహించడానికి ఎలా చూద్దాం ప్రత్యేక కూర్పికం పద్ధతి ఉపయోగించి. యొక్క ఫోబ్ హాష్ లెట్. మేము హ్యాష్కోడ్ 6 పొందండి. మా మునుపటి ఉదాహరణలో మేము కేవలం ఉన్నాయి శ్రేణి లో తీగలను నిల్వ. ఈ సమస్య ఏర్పడింది. 

మేము clobber వద్దు జోయి, మరియు మేము ఇప్పటికే చేసిన మేము కాస్తుందని పొందవచ్చు చూసిన సమస్యలు మేము ప్రయత్నించండి ఉంటే మరియు అడుగు ద్వారా మరియు ప్రోబ్. కానీ ఏం మేము కేవలం రకమైన ఈ కుడి, అదే విధంగా చికిత్స? ఇది కేవలం ఒక మూలకం జోడించడం వంటిది ఒక లింక్ జాబితా యొక్క తల. ఫోబ్ కోసం లెట్స్ కేవలం malloc స్పేస్ తెలియజేయండి. 

మేము ఫోబ్ యొక్క తదుపరి పాయింటర్ పాయింట్లు సే చేస్తాము లింక్ జాబితా యొక్క పాత తల, ఆపై 6 కేవలం చూపాడు లింక్ జాబితా కొత్త తల. మరియు ఇప్పుడు మేము ఫోబ్ మార్చారు, చూడండి. మేము ఇప్పుడు రెండు నిల్వ చేయవచ్చు హ్యాష్కోడ్ 6 తో మూలకాలు, మరియు మేము ఏ సమస్యలు లేదు. 

ఇది చాలా చక్కని అన్ని వార్తలు కూర్పికం ఉంది. మరియు కూర్పికం ఖచ్చితంగా ఉంది ఆ పద్ధతి మీరు ఉంటే అత్యంత సమర్థవంతంగా వెళ్తున్నారు మీరు ఒక హాష్ పట్టిక లో డేటా నిల్వ ఉంటాయి. కానీ ఈ కలయిక శ్రేణుల మరియు అనుసంధాన జాబితాలు కలిసి నిజంగా ఒక హాష్ పట్టిక ఏర్పాటు నాటకీయంగా మీ సామర్థ్యాన్ని మెరుగుపరుస్తుంది డేటా పెద్ద మొత్తంలో నిల్వ, మరియు చాలా త్వరగా మరియు సమర్ధవంతంగా అన్వేషణ ఆ డేటా ద్వారా. 

మరో ఇప్పటికీ ఉంది అక్కడ డేటా నిర్మాణం కూడా ఒక బిట్ కావచ్చు హామీ పరంగా మంచి మా చొప్పించడం, తొలగింపు, మరియు చూసేందుకు సార్లు కూడా వేగంగా ఉంటాయి. మరియు మేము ప్రయత్నాలు వీడియోలో చూస్తారు. నేను డౌ లాయిడ్ ఉన్నాను, ఈ CS50 ఉంది.