[శబ్దం].
హాష్ పట్టికలు లోకి డైవింగ్ ముందు, లెట్స్
మొదటి కొన్ని రెండింటికీ సమీక్షించి
సరళమైన డేటా నిర్మాణాలు, ప్రారంభమయ్యే
శ్రేణుల.
శ్రేణుల మాకు స్టోర్ చేయడానికి అనుమతిస్తుంది గుర్తుచేసుకున్నారు
ఒక డేటా రకమైన మూలకాలను
పక్కపక్కన మెమరీలో.
ప్రతి మూలకం సంబంధం ఎందుకంటే
ఒక ఇండెక్స్, లేదా నగర,
మేము అన్ని రాండమ్ యాక్సెస్ కలిగి
వ్యూహంలో అంశాలు.
ఇతర మాటల్లో చెప్పాలంటే, ఏ మూలకం యాక్సెస్ చేయవచ్చు
లో సూచి ద్వారా ఒకే దశలో
శ్రేణి.
ఈ, ఒక పెద్ద ఒప్పందం ఎందుకంటే అల్గోరిథంలు
బైనరీ శోధన వంటి యాదృచ్ఛిక ఆధారపడి
యాక్సెస్.
శ్రేణుల యొక్క ఒక ఇబ్బంది అని వారి పరిమాణం
పరిష్కరించబడింది.
శ్రేణుల స్టోర్ డేటా పక్కపక్కన లో ఎందుకంటే
మెమరీ, మీరు వ్యూహం పరిమాణం పేర్కొనాలి
మీరు శ్రేణి ప్రకటిస్తాయి.
మీరు సమర్థవంతంగా ఆపరేటింగ్ అడుగుతున్నారు
తగిన మొత్తం రిజర్వ్లో వ్యవస్థ
శ్రేణి యొక్క అంశాలకు మెమరీ.
సంఖ్య హామీ ఉంది మరింత మెమరీ,
మీ శ్రేణి ప్రక్కన, అందుబాటులో ఉంటుంది
తర్వాత ఉపయోగానికి.
కాబట్టి శ్రేణుల సులభంగా పెరుగుతాయి కాదు.
మేము కూడా లింక్ నేర్చుకున్న గుర్తుచేసుకున్నారు
పెరుగుతాయి ఇది జాబితాలు, ఎందుకంటే వారి
అంశాలు మెమరీలో ఆనుకొని కాదు.
అనుబంధ జాబితా లో ప్రతి నోడ్ కలిగి
మేము నిల్వ కావలసిన మూలకం, అలాగే
తదుపరి మూలకం ఒక పాయింటర్
జాబితా.
దురదృష్టవశాత్తు, మేము కోసం చెల్లించిన ధర
డైనమిక్ పరిమాణం రాండమ్ యాక్సెస్ ఉంది
అంశాలు.
ఒక నిర్దిష్ట మూలకం యాక్సెస్ చేయడానికి,
అది మొత్తం ప్రయాణించేందుకు అవసరం
కావలసిన ఎలిమెంట్ వరకు జాబితా
చేరుకుంది.
నేను సంఖ్య 9 కోసం చూస్తున్నాను అయితే,, హ
నోడ్ నుండి నోడ్ గమనికలు అనుసరించండి,
తనిఖీ అని ప్రతి నోడ్ యొక్క విలువ
9 సమానం.
అందుకని, చెత్త సందర్భంలో, ఉంది వెతకండి
చాలా సమర్థవంతంగా నుండి ఇది O (n),.
మేము O కంటే మెరుగైన చేయవచ్చు (n) ఇప్పటికీ
మా డేటా నిర్మాణం పెరుగుతాయి అనుమతిస్తుంది
సమయం?
హాష్ పట్టికలు ఒక పరిష్కారాన్ని.
హాష్ పట్టికలు ఉపయోగించినప్పుడు వేగవంతమైన
చొప్పించడం, తొలగింపు, మరియు శోధన
అంశాలు ప్రధానం.
సిద్ధాంతంలో, చొప్పించడం, తొలగింపు, మరియు శోధన
కూడా స్థిరంగా లో పొందవచ్చు
సమయం.
కాబట్టి, ఒక హాష్ పట్టిక ఏమైనప్పటికీ ఏమిటి?
ఒక హాష్ పట్టిక కలిసి కేవలం ఒక శ్రేణి
మేము హాష్ కాల్ చేస్తాము ఒక విధి, తో
ఫంక్షన్.
హాష్ ఫంక్షన్ డేటా యొక్క భాగం పడుతుంది
ఇన్పుట్, మేము ఒక కీ ఈ కాల్, మరియు చేస్తాము
సాధారణంగా సూచిస్తారు పూర్ణాంకం, అందిస్తుంది
ఒక హాష్ విలువ.
హాష్ విలువ ఒక మా కీ మాన
హాష్ పట్టిక లో నిర్దిష్ట సూచిక.
మీరు మొదట హాష్ ఫంక్షన్ ఉపయోగించే ఇష్టం
పేరు హాష్ పట్టిక లో గుర్తించడానికి
ఒక కీ నిల్వ.
తరువాత, మీరు అదే హాష్ ఫంక్షన్ను ఉపయోగించడానికి ఇష్టం
పేరు హాష్ పట్టిక లో గుర్తించడానికి
ఒక కీ కోసం శోధించండి.
ఈ కారణంగా, కీలకమైన అని ఒక హాష్
ఫంక్షన్ నిలకడగా మరియు ప్రతిఫలాన్ని ప్రవర్తిస్తుంది
ఒకేలా కీలు కోసం అదే హాష్ విలువ.
హాష్ పట్టికలు ఉపయోగించవచ్చు తెలుసు
అన్ని రకాల స్టోర్ డేటా.
కానీ సడలించడం, మేము దృష్టి చేస్తాము
ఇప్పుడు కోసం తీగలను.
ఇక్కడ తీగలను కోసం సాధారణ హాష్ ఫంక్షన్ను ఉంది.
ఈ హాష్ విధి ఒక హాష్ కంప్యూట్
మొదటి లేఖ ఆధారంగా ఫంక్షన్
కీ.
"ఆపిల్" లేఖ "ఒక" తో ప్రారంభమవుతుంది, కాబట్టి ఇది
హాష్ పట్టిక లో ఇండెక్స్ 0 మ్యాప్.
అదేవిధంగా, "అరటి", ఇండెక్స్ 1 మాప్చేయాలి
మరియు "cat" ఇండెక్స్ 2 మాప్చేయాలి.
పదం "కుక్క" లో ఉంటే స్నేహితుడికి అడుగుతుంది ఉంటే
పట్టిక, మేము హాష్ ఇన్పుట్ "కుక్క" చేస్తాము
ఫంక్షన్, ఇది అవుట్పుట్ ఒక హాష్ విలువ
3.
"కుక్క" ఇండెక్స్ 3 వద్ద నిల్వ లేదు నుండి, మేము
"కుక్క" కాదని ధైర్యంగా చెప్పగలను
పట్టికలో,
మేము మాత్రమే ఒకటి తనిఖీ చేసిన అయినప్పటికీ
పట్టిక యొక్క 26 సూచీలు హాష్.
విషయాలు ఒక రెంచ్ విసిరే సమయంలో.
మేము లోకి "చీమ" నిల్వ మీరు ఏం
పట్టిక అదే?
"చీమ" కేవలం "ఆపిల్" చేసినట్లుగానే, ఇండెక్స్ 0 hashes.
ఈ ఢీకొన్న ఒక ఉదాహరణ,
అదే హ్యాషింగ్ రెండు కీలను ఫలితంగా
ఇండెక్స్.
మీ హాష్ పట్టిక కంటే పెద్ద అయినా
మీ డేటాను సెట్, మరియు మీరు ఒక మంచి ఎంపిక చేసిన
ఫంక్షన్ హాష్,
మీరు ఇప్పటికీ వ్యవహరించడానికి ఒక ప్రణాళిక అవసరం
ప్రమాదాలలో, ఉంటే మరియు ఉత్పన్నమవుతున్నాయి.
యొక్క రెండు యొక్క లాభాలు మరియు నష్టాలు చర్చిద్దాం
ప్రమాదాలలో పరిష్కరించటానికి విధానములను:
సరళ ఛేదించి మరియు ప్రత్యేక కూర్పికం.
కీలక hashes ఉంటే సరళ, ఛేదించి తో
గతంలో నిల్వ అదే ఇండెక్స్
కీ, అది తదుపరి అందుబాటులో కేటాయించిన
పట్టికలో స్లాట్.
కాబట్టి, "చీమ" ఇప్పుడు నుండి, ఇండెక్స్ 3 వద్ద నిల్వ ఉంది
సూచికలు 0, 1, 2 మరియు ఇప్పటికే వినియోగంలో ఉన్నాయి.
మరియు మేము మూడవ పదాన్ని నిల్వ చేయడానికి ప్రయత్నించండి ఉంటే
లేఖ "ఒక" తో మొదలవుతుంది, ఇది కేటాయించిన యొక్క
ఇండెక్స్ 4, నుండి సూచీలు 0, 1, 2, మరియు 3
పూర్తి.
మీరు ఈ సాధారణ నుండి కూడా గమనిస్తే
ఉదాహరణకు, ఒకసారి ఒక తాకిడి, మీరు సంభవిస్తుంది
గణనీయంగా అవకాశాలు పెంచే
మరో తాకిడి అదే జరుగుతుంది
ప్రాంతం.
ఈ క్లస్టరింగ్ అని మరియు అది ఒక ఉంది ఉంది
తీవ్రమైన లోపం పరిశీలించకుండా సరళ కు.
అంతేకాకుండా, దారుణమైన చొప్పించడం, తొలగింపు,
మరియు శోధన సార్లు, O (n) పరిధిలోకి చేశారు
తదుపరి అందుబాటులో స్లాట్ కలిగి వంటి
సమర్థవంతంగా పట్టిక లో గత స్లాట్.
బహుశా ప్రత్యేక కూర్పికం ఒక ఎక్కువ ఇస్తుంది
సమగ్ర పరిష్కారం.
ప్రత్యేక కూర్పికం నమూనాలో, హాష్
పట్టిక గమనికలు యొక్క వ్యూహం ఉంది
లింక్ జాబితాలు.
ఢీకొట్టడంతో సంభవించినప్పుడు, కీ ఉంటుంది
తల స్థిరంగా సమయంలో చేర్చబడుతుంది
తగిన అనుబంధ జాబితా.
మేము "ఆపిల్" కోసం శోధించినప్పుడు నిఖానామా
హాష్ పట్టిక లో?
చెత్త సందర్భంలో, మేము అడ్డంగా ఉండాలి
ఇండెక్స్ 0 వద్ద ప్రారంభమై మొత్తం లింక్ జాబితా,.
ఒక హాష్ కోసం దారుణమైన శోధన సమయం
ప్రత్యేక కూర్పికం ఉపయోగించే పట్టిక ఉంది
అందువలన k ఉన్న O (n / k),
హాష్ పట్టిక పరిమాణం.
రెండవ వేచి, k ఒక స్థిరాంకం.
కాబట్టి O (n / k), నిజంగా కేవలం O (n) ఉంది
కోసం దారుణమైన శోధన సారి ఇది
అనుబంధ జాబితా.
మేము నిజంగా అన్ని ద్వారా గాన్
హాష్ పట్టికలు గురించి తెలుసుకున్న ఇబ్బంది
మేము ప్రారంభించారు మాత్రమే తిరిగి వదులుకోవడానికి?
సైద్ధాంతిక నుండి కేసు కావచ్చు
కోణం, కాని నిజ ప్రపంచంలో,
O (n / k) భారీ అభివృద్ధి ఉంటుంది
O (n).
అది ఈ విధంగా థింక్: ఆ k భావించవచ్చును
10 - మీరు 100 సెకన్లు వేచి ఉంటుంది
లేదా 100 / k?
పూర్తి Microsoft Word నుండి 10 సెకన్లు
మీ పత్రం తనిఖీ స్పెల్.
మీరు చూసిన, ప్రమాదాలలో పరిష్కరించడంలో
ఒక సరళ శోధన విధమైన లేదా అనివార్యం
డౌన్ విషయాలు తగ్గిస్తుంది ఇది మరొక,
గణనీయంగా.
అందువలన, మీరు ఒక హాష్ ఎంచుకోండి చెయ్యవచ్చును
అవకాశం తగ్గించాలి ఫంక్షన్
మొదటి స్థానంలో సంభవించే ప్రమాదాలలో.
ఇక్కడ మంచి హాష్ కొన్ని లక్షణాలు ఉంటాయి
గుర్తుంచుకోండి విధులు.
ఒక మంచి హాష్ ఫంక్షన్ ఉపయోగం చేయాలి
ఒక కీ అందించిన సమాచారం
సంఖ్య పెంచుకోవడానికి
సాధ్యం హాష్ విలువ.
ఉదాహరణకు, మేము రెండు తీగలను కలిగి ఉంటే, "పిల్లి"
మరియు "గొంగళి", మేము వాటిని హాష్ అనుకుంటున్నారా
పట్టిక వివిధ ప్రదేశాలకు.
హాష్ విధి ఖాతాలోకి చేపడితే
మొదటి ఒకటి, రెండు, లేదా మూడు అక్షరాలు
తంత్రుల ఢీకొన్న సంభవించవచ్చు,
రెండు పదాలు అదే ప్రారంభం నుండి
మూడు అక్షరాలు.
హాష్ విలువ సమానంగా విస్తరించాలి
హాష్ పట్టిక అంతటా.
ఈ లింక్ పొడవు తగ్గిస్తుంది
జాబితాలు ప్రమాదాలలో జరగాలి.
ఇది కూడా ఒక మంచి సైన్ ఉంది ఉంటే మీ హాష్ విలువ
వేర్వేరు ఉత్పత్తి సామర్ధ్యం కలిగి ఉంటుంది
ఇలాంటి కీలు కోసం విలువలు హాష్,
చాలా తక్కువ అవకాశం ప్రమాదాలలో తయారు.
మా లక్ష్యం త్వరగా చొప్పించడం, తొలగింపు ఉంది,
మరియు శోధన.
హాష్ ఫంక్షన్ లో ఒక కీలక పాత్ర పోషిస్తుంది
ఈ ప్రక్రియలు ప్రతి మరియు ఉంటుంది
చాలా తరచుగా అని.
అందువలన, అది చాలా ఉద్యోగులున్నారు తయారు
సాధారణ, శీఘ్ర కార్యకలాపాలు పరుగుల తగ్గించడానికి
సమయం.
నేను మీరు ఈ సంక్షిప్త ఆనందించారు చేసిన ఆశిస్తున్నాము
పట్టికలు హాష్ ఇంట్రడక్షన్.
నా పేరు లారెన్ ఉంది, మరియు ఈ CS50 ఉంది.