[અવાજ].
હેશ કોષ્ટકો માં ડાઇવિંગ પહેલાં, ચાલો
પ્રથમ કેટલાક ગુણદોષ સમીક્ષા
સરળ માહિતી માળખાં સાથે શરૂ
એરે.
એરે અમને સંગ્રહવા માટે પરવાનગી આપે છે યાદ
એક માહિતી પ્રકાર તત્વો
નજીકના મેમરીમાં.
દરેક તત્વ સાથે સંકળાયેલ છે કારણ કે
ઇન્ડેક્સ, અથવા સ્થાન,
અમે બધા માટે રેન્ડમ ઍક્સેસ
ઝાકઝમાળ તત્વો છે.
અન્ય શબ્દોમાં, આપણે કોઈ પણ તત્વ ઍક્સેસ કરી શકો છો
આ માં ક્રમાંકિત દ્વારા એક પગલું
પણ દર્શાવે છે.
આ એક મોટો સોદો છે કારણ કે ગાણિતીક નિયમો
દ્વિસંગી શોધ જેવા રેન્ડમ પર આધાર રાખે છે
વપરાશ.
એરે એક નુકસાન કે તેમના કદ
સુધારેલ છે.
એરે સ્ટોર માહિતી નજીકના કારણ કે
મેમરી, તમે એક એરે માપ સ્પષ્ટ કરવો જ પડશે
તમે એરે જાહેર છે.
તમે અસરકારક રીતે સંચાલન પૂછે છે
યોગ્ય રકમ અનામત સિસ્ટમ
એરે તત્વો માટે મેમરી.
કોઇ ખાતરી છે કે વધુ મેમરી,
તમારા એરે અડીને, ઉપલબ્ધ હશે
પછી ઉપયોગ માટે.
તેથી એરે સરળતાથી ન થઈ શકો છો.
અમે કડી વિશે શીખી યાદ કે
પ્રગતિ કરી શકે છે, જે યાદી, કારણ કે તેમના
તત્વો મેમરીમાં સંલગ્ન નથી.
એક કડી થયેલ યાદીમાં દરેક નોડને સમાવતું
અમે સંગ્રહ કરવા માંગો તે તત્વ છે, સાથે સાથે
માં અનુગામી તત્વ માટે નિર્દેશક
યાદી.
દુર્ભાગ્યે, અમે માટે ચૂકવણી કરી છે કિંમત
ગતિશીલ માપ રેન્ડમ એક્સેસ છે
તત્વો છે.
ચોક્કસ તત્વ ઍક્સેસ માટે,
તે સમગ્ર પસાર જરૂરી છે
જરૂરી તત્વ છે ત્યાં સુધી યાદી
પહોંચી ગયા છે.
હું 9 નંબર શોધી રહ્યો છું, તેથી જો, હું હો
ગાંઠ પરથી બીજા ગાંઠ પર પોઇંટરો અનુસરો,
ચકાસણી કે શું દરેક નોડ ની કિંમત
9 ને સમાન હોય છે.
આ રીતે, સૌથી ખરાબ કિસ્સામાં, છે જુઓ
અત્યાર સુધી અસરકારક છે જે ઓ (એન),.
અમે કંઈપણ કરતા વધુ સારી રીતે કરી શકે છે (એન) છે, જ્યારે હજુ પણ
અમારી માહિતી માળખું પર પ્રગતિ માટે પરવાનગી આપે છે
સમય?
હેશ કોષ્ટકો ઉકેલ આપે છે.
હેશ કોષ્ટકો ઉપયોગ થાય છે જ્યારે ઝડપી
નિવેશ, દૂર કરવાનું, અને લુકઅપ
તત્વો અગ્રતા છે.
સિદ્ધાંત, નિવેશ, ઘટાડા અને લુકઅપ
પણ સતત પરિપૂર્ણ કરી શકાય છે
સમય.
તેથી, હેશ ટેબલ કોઈપણ રીતે શું છે?
એક હેશ કોષ્ટક જોડી માત્ર એક વ્યૂહરચના છે
અમે હેશ કહી શકશો કે જે કાર્ય, સાથે
કાર્ય કરે છે.
આ હેશ વિધેય માહિતી એક ભાગ લે છે
ઇનપુટ પ્રમાણે, અમે કી આ કહી, અને પડશે
સામાન્ય રીતે ઓળખવામાં આવે છે પૂર્ણાંક, આઉટપુટ
હેશ કિંમત તરીકે.
આ હેશ કિંમત એક અમારી કી નકશા
હેશ કોષ્ટકમાં ચોક્કસ ઇન્ડેક્સ.
તમે શરૂઆતમાં હેશ વિધેય ઉપયોગ હો
જ્યાં હેશ કોષ્ટકમાં માટે નક્કી
આપેલ કી સ્ટોર કરે છે.
બાદમાં, તમે એ જ હેશ વિધેય વાપરવા માંગો છો
જ્યાં હેશ કોષ્ટકમાં માટે નક્કી કરવા માટે
આપેલ કી શોધવા.
આ કારણોસર, તે નિર્ણાયક છે કે હેશ
કાર્ય સતત અને આઉટપુટ વર્તે
સમાન કીઓ માટે જ હેશ કિંમત.
હેશ કોષ્ટકો માટે વાપરી શકાય છે તે જાણી
તમામ પ્રકારની માહિતીને સંગ્રહો.
પરંતુ બધી વસ્તુઓ સરળ બનાવવા માટે, અમે પર ધ્યાન કેન્દ્રિત પડશે
હવે માટે શબ્દમાળાઓ.
અહીં શબ્દમાળાઓ માટે એક સરળ હેશ વિધેય છે.
આ હેશ વિધેય હેશ ગણતરી
આ પ્રથમ અક્ષર પર આધારિત કાર્ય
કી.
"સફરજન" પત્ર "એ" સાથે શરૂ થાય છે, તેથી તે છે
હેશ કોષ્ટકમાં 0 અનુક્રમણિકા માટે માપ થયેલ.
એ જ રીતે, "કેળા" અનુક્રમણિકા 1 માટે માપ થયેલ છે
અને "બિલાડી" 2 અનુક્રમણિકા માટે માપ થયેલ છે.
શબ્દ "કૂતરો" છે કે નહીં તે એક મિત્ર પૂછે છે
ટેબલ, અમે હેશ માં ઇનપુટ "કૂતરો" પડશે
કાર્ય, જે કરશે આઉટપુટ હેશ કિંમત
3.
"કૂતરો" 3 અનુક્રમણિકા પર સંગ્રહ થયું નથી, કારણ કે અમે
"કૂતરો" નથી કે વિશ્વાસ સાથે કહી શકો છો
કોષ્ટકમાં,
અમે માત્ર એક ચકાસાયેલ છે, છતાં પણ
ટેબલ 26 સૂચકાંક હેશ.
વસ્તુઓ એક સાધન ફેંકવું સમય.
અમે માં "કીડી" સંગ્રહ કરવા માંગો તો શું
ટેબલ સાથે સાથે?
"કીડી" માત્ર "સફરજન" હતી, કારણ કે ઇન્ડેક્સ 0 થી હેશો.
આ અથડામણ એક ઉદાહરણ છે, જે
એ જ માટે હેશીંગ બે કીઓ પરિણામ
ઇન્ડેક્સ.
તમારા હેશ ટેબલ કરતાં પણ મોટો છે તો પણ
તમારા ડેટાને સુયોજિત કરો, અને તમે એક સારા પસંદ કર્યું
કાર્ય હેશ,
તમે હજુ પણ સાથે કામ કરવા માટે એક યોજના જરૂર
અથડામણમાં, જ્યારે અને જો તેઓ પેદા થાય છે.
બે અને પક્ષ વિપક્ષ ચર્ચા કરો
અથડામણમાં ઉકેલવા માટે સામાન્ય પદ્ધતિ:
રેખીય ચકાસણી અને અલગ અલગ chaining.
કી હેશ જો રેખીય, ચકાસણી સાથે
અગાઉ સંગ્રહ તરીકે જ અનુક્રમણિકા
કી, તે આગામી ઉપલબ્ધ સોંપેલ
કોષ્ટકમાં સ્લોટ.
તેથી, "કીડી" હવે થી, 3 અનુક્રમણિકા પર સંગ્રહ કરવામાં આવે છે
સૂચકાંક 0, 1, અને 2 પહેલેથી ઉપયોગમાં હતા.
અને અમે ત્રીજા શબ્દ સંગ્રહ કરવા પ્રયાસ કરો કે
પત્ર "એ" સાથે શરૂ થાય છે, તે સોંપાયેલ છે
ઇન્ડેક્સ 4, કારણ સૂચકાંક 0, 1, 2, અને 3
સંપૂર્ણ છે.
જો તમે આ સરળ પણ જોઈ શકો છો
ઉદાહરણ તરીકે, એક વખત ટક્કર, તમે થાય
નોંધપાત્ર તકો વધારે છે
અન્ય અથડામણ જ થશે
વિસ્તાર.
આ ક્લસ્ટરીંગ કહેવાય છે, અને તે એક છે છે
ગંભીર ખામી ચકાસણી રેખીય છે.
વધુમાં, ખરાબ કેસ દાખલ, રદ કરવા,
અને લુકઅપ વખત, ઓ (એન) ફરજ સોંપણી છે
આગામી ઉપલબ્ધ સ્લોટ કરી શકે છે, કારણ કે
સંભવિત કોષ્ટકમાં છેલ્લા સ્લોટ રહી.
કદાચ અલગ અલગ chaining વધુ આપશે
અનિવાર્ય ઉકેલ.
પાંચ અલગ અલગ chaining મોડેલ માં, હેશ
ટેબલ ખરેખર પોઇન્ટર ઝાકઝમાળ છે
સંલગ્ન યાદીઓ.
જ્યારે અથડામણ થાય છે, કી બની શકે છે
વડા પર સતત સમય ઉમેરાશે
યોગ્ય કડી થયેલ યાદી.
અમે "સફરજન" માટે શોધ હવે જ્યારે શું થાય
હેશ કોષ્ટકમાં?
સૌથી ખરાબ કિસ્સામાં, અમે પસાર જ જોઈએ
0 અનુક્રમણિકા પર શરૂ સમગ્ર કડી થયેલ યાદી.
હેશ માટે ખરાબ કેસ લૂકઅપ સમય
અલગ અલગ chaining ઉપયોગ કરે છે ટેબલ છે
તેથી કે આ છે જ્યાં ઓ (એન / કે),
હેશ કોષ્ટક માપ.
બીજી રાહ જુઓ, કે એક સતત છે.
તેથી ઓ (એન / કે), ખરેખર માત્ર ઓ (એન) છે
માટે સૌથી ખરાબ કેસ લૂકઅપ સમય હતો જે
એક કડી થયેલ યાદી.
અમે ખરેખર તમામ પસાર થઈ છે
હેશ કોષ્ટકો વિશે શીખવાની મુશ્કેલી
અમે શરૂ જ્યાં માત્ર પાછા અંત?
કે સૈદ્ધાંતિક ના કેસ થઈ શકે છે
પરિપ્રેક્ષ્ય, પરંતુ વાસ્તવિક વિશ્વમાં,
ઓ (એન / કે) પર એક વિશાળ સુધારો કરી શકે છે
ઓ (એન).
તે આ રીતે વિચારો: કે 'કે' છે ધારે
10 - જો તમે તેના બદલે 100 સેકન્ડ રાહ જુઓ છો
અથવા 100 / k?
સમાપ્ત કરવા માટે માઈક્રોસોફ્ટ વર્ડ થી 10 સેકન્ડ
તમારા દસ્તાવેજ ચકાસણી ગાળો.
તમે માત્ર જોઈ ગયા તેમ, અથડામણમાં ઉકેલવા
એક રેખીય શોધ જેવું અથવા કાર્ય
નીચે વસ્તુઓ ધીમો પડી જાય છે, જે અન્ય,
નોંધપાત્ર.
તેથી, તમે હેશ પસંદ કરવા માંગો છો પડશે
શક્યતા ઘટાડે છે તે કાર્ય
પ્રથમ સ્થાને આવી અથડામણમાં.
અહીં સારી હેશ કેટલાક ગુણધર્મો છે
ધ્યાનમાં રાખો કાર્ય કરે છે.
સારી હેશ વિધેય ઉપયોગ કરે છે કરીશું
આપેલ કી દ્વારા પૂરી પાડવામાં આવેલ તમામ માહિતી
સંખ્યા વધારવા માટે
શક્ય હેશ કિંમતો.
ઉદાહરણ તરીકે, અમે બે શબ્દમાળાઓ હતું "બિલાડી"
અને "કેટરપિલર", અમે તેમને હેશ કરવા માંગો છો છો
ટેબલ પર વિવિધ સ્થળોએ છે.
હેશ વિધેય માત્ર ધ્યાનમાં લીધો તો
પ્રથમ એક, બે, અથવા તો ત્રણ અક્ષરો
આ શબ્દમાળાઓ, અથડામણ ઉત્પન્ન થઇ શકે છે,
આ બંને શબ્દો એક જ સાથે શરૂઆત થી
ત્રણ અક્ષરો.
હેશ કિંમતો બધે સમાન જોઈએ
હેશ ટેબલ તરફ.
આ કડી લંબાઈ ઘટાડો કરશે
યાદીઓ અથડામણમાં થાય છે જોઈએ.
તે પણ એક સારો સંકેત છે જો તમારા હેશ કિંમત
ખૂબ જ અલગ પેદા કરવા સક્ષમ છે
સમાન કીઓ માટે કિંમતો હેશ,
ખૂબ ઓછી અથડામણમાં બનાવે છે.
અમારો ધ્યેય ઝડપી નિવેશ, કાઢી નાંખવાનું છે,
અને લુકઅપ.
આ હેશ વિધેય માં મહત્વની ભૂમિકા બજાવે છે
આ પ્રક્રિયા દરેક અને હશે
ખૂબ વારંવાર કહેવામાં આવે છે.
તેથી, ખાતરી કરો કે તે ખૂબ જ રોજગારી કરો
સરળ, ઝડપી કામગીરી રન ઘટાડવા માટે
સમય.
હું તમને આ ટૂંકા આનંદ કર્યું આશા
કોષ્ટકો હેશ પરિચય.
મારું નામ લોરેન છે, અને આ CS50 છે.