[સંગીત વગાડવાનો] ડો LLOYD: હવે તમે એરે વિશે ઘણું જાણે છે, અને તમે સંલગ્ન યાદીઓ વિશે ઘણું જાણો છો. અને અમે ચર્ચા કરી છે સારી અને ખરાબ વિપક્ષ, અમે કર્યું યાદીઓ કડી થયેલ છે કે ચર્ચા મોટા અને નાના મળી શકે છે, પરંતુ તેઓ વધુ કદ લે છે. એરે વધુ સરળ છે વાપરવા માટે, પરંતુ તેઓ ખૂબ જ પ્રતિબંધિત છો અમે માપ સુયોજિત કરવા માટે હોય છે ખૂબ શરૂઆતમાં એરે અને પછી અમે તેની સાથે અટકી રહ્યા છો. 

પરંતુ અમે ખૂબ ખૂબ કર્યું છે, અમારા વિષયો તમામ ખાલી કડી યાદીઓ અને એરે વિશે. અથવા આપણે છે? કદાચ આપણે કંઈક કરી શકો છો પણ વધુ સર્જનાત્મક. અને પૂરું પાડે છે કે આનાથી સૉર્ટ કરો હેશ ટેબલ વિચાર. 

તેથી હેશ કોષ્ટકમાં અમે પ્રયાસ કરવા જઈ રહ્યાં છો એક કડી થયેલ યાદી સાથે ઝાકઝમાળ ભેગા કરો. અમે લાભ લેવા જઈ રહ્યાં છો એરે, રેન્ડમ એક્સેસ જેવી, માત્ર એરે પર જવા માટે સક્ષમ હોવા તત્વ 4 અથવા એરે તત્વ 8 સમગ્ર ફરી વળવું કર્યા વગર. તે સાચું છે, ખૂબ ઝડપી છે? 

પરંતુ અમે પણ અમારી માહિતી હોય માંગો છો માળખું વૃદ્ધિ પામે છે અને સંકોચો સમક્ષ રજુ કરવાનો પ્રયત્ન. અમે નથી, જરૂર નથી પ્રતિબંધિત કરવા માંગો છો. અને અમે રજુ કરવાનો પ્રયત્ન કરવા માંગો છો ઉમેરો અને વસ્તુઓ દૂર કરવા માટે ખૂબ જ સરળતાથી, જે તમે યાદ તો, એક એરે સાથે ખૂબ જ જટિલ છે. અને અમે આ કૉલ કરી શકો છો નવી વસ્તુ હેશ કોષ્ટક. 

અને જો યોગ્ય રીતે અમલમાં અમે પ્રકારના લઇ રહ્યા છીએ બંને માહિતી ફાયદા જો તમે પહેલાથી જ જોઇ માળખાં, એરે અને સંલગ્ન યાદીઓ. દાખલ કરવા માટે શરૂ કરી શકો છો 1 થીટા તરફ વલણ ધરાવે છે. થીટા અમે ખરેખર નથી ચર્ચા છે, પરંતુ થીટા માત્ર સરેરાશ કેસ છે, શું ખરેખર શું ચાલી રહ્યું છે. તમે હંમેશા માટે નથી જતા રહ્યાં છો સૌથી ખરાબ કેસ દૃશ્ય હોય છે, અને તમે હંમેશા માટે છે જવું કરી રહ્યાં છો શ્રેષ્ઠ કેસ દૃશ્ય, તેથી શું છે સરેરાશ દૃશ્ય? 

વેલ સરેરાશ નિવેશ હેશ કોષ્ટક માં બંધ સતત સમય મેળવવા માટે શરૂ કરી શકો છો. અને નિરાકરણ મેળવી શકો છો સતત સમય માટે બંધ કરો. અને લુકઅપ મેળવી શકો છો સતત સમય માટે બંધ કરો. That's-- અમે માહિતી નથી માળખું હજુ સુધી કે કરી શકો છો, અને તેથી આ પહેલેથી જ લાગે છે એક સુંદર મહાન વસ્તુ ગમે છે. અમે ખરેખર ઘટાડી કર્યું તેના પોતાના પર દરેક ગેરફાયદા. 

આ પ્રદર્શન વિચાર , જોકે અમે સુધારો અમે ઉમેરવા કે કેવી રીતે પુનવિર્ચાર જરૂર બંધારણ માં માહિતી. ખાસ કરીને અમે માંગો છો માહિતી પોતે અમને જણાવો જ્યાં તે માળખામાં જવું જોઈએ. અને અમે તે પછી તે જોવા માટે જો જરૂર હોય તો આ માળખું, અમે તેને શોધી કરવાની જરૂર છે, તો અમે માહિતી જોવા માંગો છો ફરીથી અને અસરકારક રીતે કરવા માટે સક્ષમ હોઇ શકે છે, માહિતી મદદથી રેન્ડમ ઍક્સેસ. જસ્ટ જોઈને માહિતી અમે હોવી જોઇએ બરાબર અમે છો જ્યાં એક વિચાર હેશ કોષ્ટકમાં તે શોધવા માટે જઈ રહી છે. 

હેશ હવે નુકસાન ટેબલ તેઓ ખરેખર છો છે ઓર્ડર અથવા માહિતી સૉર્ટ ખૂબ ખરાબ. અને હકીકતમાં, તમે શરૂ કરો, તો ઓર્ડર અથવા સૉર્ટ તેમને વાપરવા માટે માહિતી તમે બધા ગુમાવી લાભ અગાઉ તમે નિવેશ અને નિરાકરણ દ્રષ્ટિએ હતી. સમય નજીક બની જાય છે n ના થીટા, અને અમે મૂળભૂત રીતે કર્યું એક કડી થયેલ યાદી માં regressed. અને તેથી અમે માત્ર હેશ ઉપયોગ કરવા માંગો છો કોષ્ટકો અમે વિશે કાળજી નથી, તો માહિતી છટણી કરવામાં આવે છે કે કેમ. આ સંદર્ભ માટે જે તમે CS50 તેમને ઉપયોગ કરશો તમે કદાચ કાળજી નથી માહિતી સૉર્ટ થાય છે. 

તેથી હેશ ટેબલ સંયોજન છે બે અલગ ટુકડાઓ જેની સાથે આપણે પરિચિત છો. પ્રથમ કાર્ય છે, કે જે અમે સામાન્ય રીતે હેશ વિધેય કૉલ કરો. અને તે હેશ વિધેય રહ્યું છે કેટલાક બિન નકારાત્મક પૂર્ણાંક પાછા જે અમે સામાન્ય રીતે ઠીક છે, એક હૅશકોડ કૉલ? બીજા ભાગ છે, જે એક એરે છે, પ્રકાર અમે સ્ટોર માહિતી માટે સક્ષમ માહિતી માળખામાં મૂકવા માંગો છો. અમે પર બંધ પકડી પડશે હવે યાદી તત્વ કડી અને માત્ર એક મૂળભૂત સાથે શરૂ તેની આસપાસ તમારી વડા વિચાર કરવા માટે કોષ્ટક હેશ, અને પછી અમે કદાચ તમાચો પડશે તમારા મન થોડો ત્યારે અમે સાથે મળીને એરે અને લિંક યાદીઓ ભેગા કરો. 

મૂળભૂત વિચાર છતાં અમે કેટલાક માહિતી લેવા છે. અમે તે માહિતી દ્વારા ચલાવવામાં હેશ વિધેય. અને તેથી માહિતી પ્રક્રિયા છે અને તે ઠીક છે, એક નંબર બહાર spits? અને પછી તે નંબર સાથે અમે ફક્ત માહિતી સંગ્રહ અમે સંગ્રહ કરવા માંગો છો તે સ્થાન પર દર્શાવે છે. તેથી, ઉદાહરણ તરીકે અમે કદાચ છે શબ્દમાળાઓ આ હેશ કોષ્ટક. તે, તેથી તે 10 તત્વો મળી છે અમે તેને 10 શબ્દમાળાઓ ફિટ થઈ શકે છે. 

અમે જ્હોન હેશ કરવા માંગો છો કહે છે. જ્હોન તેથી માહિતી તરીકે અમે સામેલ કરવા માંગો છો ક્યાંક આ હેશ કોષ્ટક માં. જ્યાં અમે તે મૂકી શકું? વેલ ખાસ કરીને સાથે એરે અત્યાર સુધી અમે કદાચ એરે સ્થાન 0 તે મૂકવામાં આવશે. પરંતુ હવે અમે આ નવા હેશ વિધેય હોય છે. 

અને અમે જ્હોન ચલાવવા કહે છે કે દો આ હેશ વિધેય દ્વારા અને તે 4 બહાર spits છે. અમે છો જ્યાં વેલ કે છે જ્હોન મૂકેલ જઈ રહી છે. અમે એરે સ્થાન જ્હોન મૂકેલ 4, અમે again-- જ્હોન હેશ કારણ કે જો પાછળથી અમે કહી દો શોધ અને જોવા માંગો છો જ્હોન આ હેશ અસ્તિત્વમાં હોય તો અમે શું કરવાની જરૂર બધા table-- જ હેશ મારફતે ચાલે છે કાર્ય, નંબર 4 બહાર વિચાર અને જ્હોન શોધવા માટે સક્ષમ હોઈ શકે છે તરત જ અમારી માહિતી બંધારણ છે. તે ખૂબ સારી છે. 

અમે હવે આ શું કહે છે ફરીથી, આપણે પાઊલની હેશ કરવા માંગો છો. પાઊલે ઍડ કરવા માંગો છો આ હેશ કોષ્ટક માં. આ સમય અમે ચલાવવા કહો કે હેશ વિધેય મારફતે પાઉલ, પેદા થાય છે કે હૅશકોડ 6 છે. વેલ હવે આપણે પાઊલની મૂકી શકો છો એરે સ્થાન 6. અને અમે કે શું જોવા માટે જરૂર હોય તો પાઊલે હેશ ટેબલ છે, અમે શું કરવાની જરૂર બધા પોલ ચાલે છે હેશ વિધેય મારફતે ફરી અને અમે બહાર ફરી 6 વિચાર જઈ રહ્યાં છો. 

અને પછી અમે માત્ર જોવા એરે સ્થાન 6. પોલ છે? જો આમ હોય, તે હેશ કોષ્ટકમાં છે. પોલ ન હોય? તેમણે હેશ કોષ્ટકમાં નથી. તે ખૂબ સરળ છે. 

હવે તમે કેવી રીતે એક હેશ વિધેય વ્યાખ્યાયિત કરી શકું? વેલ ખરેખર કોઈ મર્યાદા છે શક્ય જટિલ કાર્ય સંખ્યા. હકીકતમાં, એક નંબર ખરેખર છે ઇન્ટરનેટ પર ખરેખર સારી રાશિઓ. એક નંબર છે, ત્યાં ખરેખર છે ઇન્ટરનેટ પર ખરેખર ખરાબ રાશિઓ. તે પણ ખૂબ જ સરળ છે એક ખરાબ લખવા માટે. 

તેથી શું એક સારો બનાવે છે હેશ વિધેય, અધિકાર? વેલ સારી હેશ વિધેય જોઈએ માત્ર માહિતી hashed કરવામાં આવી રહી વાપરવા માટે, અને માહિતી તમામ hashed આવી રહી છે. તેથી અમે કંઈપણ ઉપયોગ કરવા માંગો છો નથી આપણે કંઈ સમાવિષ્ટ થતી નથી માહિતી કરતાં અન્ય બીજું. અને અમે માહિતી તમામ વાપરવા માંગો છો. અમે હમણાં જ એક ભાગ ઉપયોગ કરવા માંગો છો નથી તે, અમે તે બધા વાપરવા માંગો છો. એક હેશ વિધેય જોઈએ પણ નિર્ધારિત છે. કે શું અર્થ છે? વેલ તે અર્થ એ થાય કે દર વખતે આપણે માહિતી ચોક્કસ જ ટુકડો પસાર હેશ વિધેય માં અમે હંમેશા એ જ હૅશકોડ નીકળી જાય છે. હું માં જ્હોન પાસ કરો તો હેશ વિધેય હું 4 નીકળી જાય છે. હું તે કરવા માટે સમર્થ હોવું જોઈએ 10,000 સમય અને હું હંમેશા 4 મળશે. તેથી કોઈ રેન્ડમ નંબર અસરકારક અમારા હેશ સામેલ કરી શકાય છે tables-- અમારા હેશ કાર્યો છે. 

એક હેશ વિધેય પણ જોઈએ એકસરખી માહિતી વિતરિત કરે છે. દરેક વખતે જ્યારે તમે મારફતે માહિતી ચલાવો, તો હેશ વિધેય તમે હૅશકોડ 0 વિચાર તે હક, કદાચ એટલા મહાન નથી? તમે કદાચ મોટા કરવા માંગો છો હેશ કોડ શ્રેણી. પણ વસ્તુઓ ફેલાવો કરી શકાય છે ટેબલ દરમિયાન. અને તે પણ જો ખરેખર મહાન હશે જ્હોન અને જોનાથન જેવી સમાન માહિતી, કદાચ તોલવું ફેલાય હતા હેશ કોષ્ટકમાં જુદા જુદા સ્થળોએ. તે એક સરસ લાભ હશે. 

અહીં એક હેશ વિધેય એક ઉદાહરણ છે. હું અગાઉ આ એક લખ્યું હતું. તે ખાસ કરીને નથી સારી હેશ વિધેય ખરેખર નથી કે કારણો માટે હમણાં જવા સહન. પરંતુ તમે અહીં શું થઈ રહ્યું છે જુઓ છો? અમે એક ચલ જાહેર કરી રહ્યાં છો એવું લાગે છે રકમ અને 0 થી સમાન સુયોજિત કહેવાય છે. અને પછી દેખીતી રીતે હું કંઈક કરી રહ્યો છું જેથી લાંબા strstr [J] બરાબર નથી કારણ કે 0 બેકસ્લેશ. હું ત્યાં શું કરી રહ્યો છું? 

આ મૂળભૂત રીતે માત્ર અન્ય છે [અમલીકરણ રીતે? strl?] તમે કર્યું ત્યારે અને શોધવા શબ્દમાળા ઓવરને સુધી પહોંચી હતી. તેથી હું ખરેખર ન હોય આ શબ્દમાળા લંબાઈ ગણતરી, હું હિટ જ્યારે હું માત્ર ઉપયોગ કરું છું બેકસ્લેશ 0 પાત્ર મને ખબર હું શબ્દમાળા ઓવરને પહોંચી ગયા છો. અને પછી હું રાખવા જાઉં છું કે જેઓ શબ્દમાળા વારો, strstr [J] ઉમેરીને પછી ટૂંકમાં, અને દિવસ ઓવરને અંતે રકમ ફેરફારની પાછા જઈ HASH_MAX. 

મૂળભૂત રીતે આ બધા હેશ કાર્ય ઉમેરો કરવાનું છે ના ASCII કિંમતો તમામ મારા શબ્દમાળા છે, અને પછી તે કેટલાક હૅશકોડ પરત HASH_MAX દ્વારા modded. તે કદાચ માપ છે મારા એરે છે, અધિકાર? હું હેશ મેળવવામાં આવશે નહિં માંગો કોડ મારા એરે કદ 10 છે, તો હું મેળવવામાં પ્રયત્ન કરવા માંગો છો નથી હેશ કોડ 11, 12, 13, હું વસ્તુઓ મૂકી શકતા નથી એરે તે સ્થળો, કે ગેરકાયદે હશે. હું એક સેગ્મેન્ટેશન ક્ષતિમાં ભોગ છો. 

હવે અહીં અન્ય ઝડપી કોરે છે. સામાન્ય રીતે તમે કદાચ નથી જઈ રહ્યાં છો તમારા પોતાના જટિલ કાર્ય લખવા માંગો છો. તે ખરેખર એક બીટ છે એક કલા છે, નથી વિજ્ઞાન. અને તેમને જાય છે ઘણો છે. હું જણાવ્યું હતું કે, જેમ કે ઈન્ટરનેટ, સંપૂર્ણ છે ખરેખર સારા જટિલ કાર્ય છે, અને તમે ઇન્ટરનેટ ઉપયોગ કરવો જોઈએ તે ખરેખર છે, કારણ કે જટિલ કાર્ય શોધવા માત્ર પ્રકારની બિનજરૂરી સમય કચરો તમારા પોતાના બનાવવા માટે. 

તમે સરળ રાશિઓ લખી શકો છો ચકાસણી હેતુઓ માટે. પરંતુ તમે ખરેખર કરવા જઇ રહ્યા છે ત્યારે માહિતી હેશીંગ અને સ્ટોર શરૂ તમે છો એક હેશ કોષ્ટક માં કદાચ માંગો છો જઈ પેદા કરવામાં આવી હતી કે જે અમુક કાર્ય વાપરવા માટે તમે માટે, કે ઇન્ટરનેટ પર હાજર છે. તમે માત્ર તેની ખાતરી કરી હોય તો તમારા સ્રોતને અવતરિત. કોઈ કારણ છે અહીં કંઈપણ બીજા કોઈના લખાણ કે વિચારને પોતાના મૌલિક લખાણ કે વિચાર તરીકે રજૂ કરવા. 

કોમ્પ્યુટર વિજ્ઞાન સમુદાય છે ચોક્કસપણે કિંમતો વધતી, અને ખરેખર ઓપન સોર્સ, અને તે ખરેખર મહત્વનું છે તમારા સ્રોતને અવતરિત કે જેથી લોકો માટે એટ્રિબ્યુશન મેળવી શકો છો તેઓ કે કામ સમુદાય લાભ કરી. તેથી હંમેશા sure-- હોઈ અને માત્ર હેશ માટે કાર્યો, પરંતુ સામાન્ય રીતે જ્યારે તમે બહાર સ્ત્રોત માંથી કોડ વાપરો હંમેશા તમારા સ્રોત દાખવી. હતી જે વ્યક્તિ ક્રેડિટ આપે છે કામ કેટલાક જેથી તમે નથી. 

ઠીક છે, જેથી ચાલો આ ફોટાઓની દો એક બીજા માટે હેશ કોષ્ટક. અમે બાકી છે આ છે અમે દાખલ પછી બંધ આ હેશ કોષ્ટક માં જ્હોન અને પોલ. તમે અહીં એક સમસ્યા જુઓ છો? તમે બે દેખાઈ શકે છે. પરંતુ ખાસ કરીને, તમે શું આ શક્ય સમસ્યા જુઓ છો? 

શું હું રીંગો હેશ, અને તે જો પછી પ્રક્રિયા કે બહાર વળે હેશ વિધેય મારફતે માહિતી રીંગો પણ હૅશકોડ 6 પેદા થાય છે. હું પહેલેથી જ ડેટા મળી છે hashcode-- એરે સ્થાન 6. તેથી તે કદાચ થોડી હશે હવે મારા માટે એક સમસ્યા, અધિકાર? 

અમે એક અથડામણ આ ફોન કરો. અને અથડામણ જ્યારે બે થાય છે માહિતી ટુકડાઓ જ હેશ મારફતે ચલાવવા કાર્ય એ જ હૅશકોડ પેદા. કદાચ અમે હજુ પણ બંને વિચાર કરવા માંગો છો હેશ કોષ્ટક માં ડેટા ટુકડાઓ, અન્યથા અમે રીંગો ચાલી શકાય તેમ ન હતી આપખુદ હેશ વિધેય દ્વારા. અમે કદાચ વિચાર કરવા માંગો છો કે જે એરે રીંગો. 

અમે જોકે તેને કેવી રીતે કરવું, તે તો અને પૌલ બંને ઉપજ હૅશકોડ 6? અમે પોલ ઉપર લખવા માંગો છો નથી, આપણે પાઊલની પણ ત્યાં હોઈ માંગો છો. તેથી અમે વિચાર કરવા માટે એક માર્ગ શોધવા માટે જરૂર છે હેશ કોષ્ટક માં તત્વો કે હજુ પણ અમારી ઝડપી સાચવે નિવેશ અને ઝડપી દેખાવ. અને તેની સાથે વ્યવહાર કરવા માટે એક માર્ગ છે ચકાસણી રેખીય કહેવાય કંઈક. 

અમે એક હોય તો આ પદ્ધતિનો ઉપયોગ કરીને અથડામણ, સાથે સાથે, અમે શું કરવું? વેલ અમે એરે સ્થાન તેને ન મૂકી શકો છો 6, અથવા ગમે હૅશકોડ પેદા કરવામાં આવી હતી, માતાનો હૅશકોડ વત્તા 1 તેને મૂકી દો. અને તે સંપૂર્ણ ચાલો તો હૅશકોડ વત્તા 2 તેમને મૂકો. આ હોવા લાભ તેમણે તો નથી બરાબર અમે તે લાગે છે, જ્યાં અને અમે શોધી શરૂ કરવા માટે હોય છે, કદાચ આપણે પણ અત્યાર સુધી જવા માટે નથી. કદાચ અમે શોધવા માટે નથી હેશ ટેબલ તમામ n તત્વોના. કદાચ અમે શોધવા માટે હોય છે તેમને એક દંપતિ. 

અને તેથી અમે હજુ તરફ પ્રવૃત્ત કરી રહ્યાં છો સરેરાશ કેસ 1 નજીક વિ હોવા કે એ નજીક છે, તેથી કદાચ કે કામ કરીશું. તેથી આપણે કેવી રીતે આ જોવા દો વાસ્તવિકતા બહાર કામ કરી શકે છે. અને કદાચ આપણે શોધી શકે છે જો માતાનો જોવા દો અહીં થાય છે કે જે કદાચ સમસ્યા નથી. 

અમે બાર્ટ હેશ કહે છે. તેથી હવે અમે એક નવો સેટ ચલાવવા માટે જઈ રહ્યાં છો હેશ વિધેય મારફતે શબ્દમાળાઓ, અને અમે હેશ દ્વારા બાર્ટ ચલાવવા કાર્ય, અમે હૅશકોડ 6 છે. અમે એક નજર, અમે 6 જુઓ ખાલી છે, તેથી અમે ત્યાં બાર્ટ મૂકી શકો છો. 

હવે અમે લિસા અને કે હેશ પણ હૅશકોડ 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 ઉમેરો અમે તેમને મૂકી સ્થળ નથી. અમે હમણાં જ આસપાસ ફરતો કરી શકાય છે વર્તુળો, એક ખાલી હાજર શોધવા માટે પ્રયાસ કરી અને અમે કદાચ અટવાઇ મળી એક અનંત લૂપ છે. 

તેથી તે વિચાર કરવા માટે પૂરું પાડે છે આ પ્રકારની કંઈક chaining કહેવાય છે. અને આ અમે લાવવા જઈ રહ્યાં છો જ્યાં છે પાછા ચિત્ર સંલગ્ન યાદીઓ. તો શું તેના બદલે માત્ર સ્ટોર એરે માહિતી પોતે, એરે દરેક તત્વ શકે ઘણા ટુકડાઓ માહિતી ધરાવે છે? વેલ કે અધિકાર, અર્થમાં બનાવવા નથી? અમે તે એક એરે માત્ર કરી શકો છો એક એરે દરેક તત્વ hold-- માત્ર એક જ ટુકડો પકડી શકે છે કે માહિતી પ્રકાર માહિતી. 

પરંતુ શું કે જો ડેટા પ્રકાર એક કડી થયેલ યાદી છે, અધિકાર છે? તેથી શું જો દરેક એરે તત્વ હતી એક કડી થયેલ યાદી વડા માટે નિર્દેશક? અને પછી અમે બિલ્ડ કરી શકે છે તે કડી થયેલ યાદીઓ અને, આપખુદ તેમને વૃદ્ધિ કડી થયેલ યાદીઓ માટે પરવાનગી આપે છે કારણ કે અમને વધવા અને વધુ ઘણો સંકોચો ઝાકઝમાળ કરે સરળતાથી કરતાં. તેથી શું આપણે હવે ઉપયોગ જો, અમે આ લાભ? અમે આ સાંકળો વધવા માટે શરૂ આ એરે સ્થળો બહાર. 

હવે અમે એક અનંત ફિટ થઈ શકે છે માહિતી જથ્થો, અથવા અનંત નથી, એક મનસ્વી રકમ માહિતી અમારા હેશ કોષ્ટક માં ક્યારેય ચાલી વગર અથડામણ સમસ્યા. અમે પણ દૂર કર્યું આ કરવાથી ક્લસ્ટરીંગ. અને સાથે સાથે આપણે સામેલ હોય છે ખબર છે કે એક કડી થયેલ યાદી માં, તમે યાદ તો એકલા, સંલગ્ન યાદીઓ પર અમારા વિડિઓ કડી યાદીઓ અને સમયમાં બમણું કડી થયેલ યાદીઓ, તે સતત સમય કામગીરી છે. અમે હમણાં જ આ બોલ પર ઉમેરી રહ્યાં છીએ. 

અને જુઓ માટે, સાથે સાથે અમે ખબર નથી કે એક કડી થયેલ યાદીમાં લુકઅપ અધિકાર, એક સમસ્યા બની શકે? અમે મારફતે શોધવા માટે હોય છે શરૂઆતથી તે અંત. કોઈ રેન્ડમ છે એક કડી થયેલ યાદીમાં ઍક્સેસ. પરંતુ જો તેના બદલે એક કર્યા કડી એક લુકઅપ n ના ઓ હશે જ્યાં યાદી, આપણે હવે 10 કડી થયેલ યાદીઓ હોય છે, અથવા 1,000 કડી યાદીઓ, હવે તે 10 ભાગ્યા n ના ઓ છે, અથવા n ના ઓ 1,000 દ્વારા વિભાજિત. 

અને અમે વાત કરવામાં આવી હતી જ્યારે સૈદ્ધાંતિક જટિલતા વિશે અમે વાસ્તવિક, સ્થિરાંકો અવગણી આ વસ્તુઓ ખરેખર તો કોઈ વાંધો વિશ્વમાં, અધિકાર? અમે ખરેખર નોટિસ કરશે આવું થાય કે 10 વખત ઝડપી ચલાવવા માટે, અથવા 1,000 વખત ઝડપી, અમે લાંબા એક વિતરણ કરી રહ્યાં છો કારણ કે 1000 નાના સાંકળો સમગ્ર સાંકળ. અને તેથી અમે દરેક વખતે શોધવા માટે અમે કરી શકો છો તે સાંકળો એક મારફતે અમે કાળજી નથી 999 સાંકળો અવગણો વિશે, અને કે જે હમણાં જ એક શોધ. 

જે સરેરાશ છે 1,000 વખત ટૂંકા હોય છે. અને તેથી અમે હજુ પણ પ્રકારના હોય છે આ સરેરાશ કેસ તરફ પ્રવૃત્ત સતત સમય છે, પરંતુ માત્ર અમે ઉચ્ચાલન છે, કારણ કે કેટલાક વિશાળ સતત પરિબળ દ્વારા ભાગાકાર. કેવી રીતે આ કદાચ માતાનો જોવા દો ખરેખર છતાં જુઓ. તેથી આ અમે હતી હેશ ટેબલ હતી અમે એક હેશ ટેબલ જાહેર પહેલાં 10 શબ્દમાળાઓ સ્ટોર કરવા સક્ષમ હતી. અમે હવે તે કરવા માટે જઈ રહ્યાં છો. અમે પહેલાથી જ ખબર કે પદ્ધતિ મર્યાદાઓ. હવે અમારા હેશ ટેબલ હોઈ ચાલે છે 10 ગાંઠો, પોઇંટરો ઝાકઝમાળ કડી થયેલ યાદીઓ હેડ. 

અને હમણાં તે નલ છે. તે 10 પોઇન્ટર દરેક એક નલ છે. આપણા માં છે હમણાં ટેબલ હેશ. 

હવે કેટલાક મૂકી શરૂ કરીએ આ હેશ કોષ્ટક માં વસ્તુઓ. અને આ પદ્ધતિ છે કે કેવી રીતે જોવા દો અમને થોડો લાભ જઈ રહી છે. હવે જોય હેશ દો. અમે શબ્દમાળા જોય મારફતે ચલાવવા પડશે હેશ વિધેય અને અમે 6 આવો. વેલ અમે હવે શું કરવું? 

વેલ હવે કડી થયેલ યાદીઓ સાથે કામ કરે છે, અમે એરે સાથે કામ નથી કરી રહ્યાં છો. અને અમે કામ કરી રહ્યા છીએ ત્યારે કડી થયેલ યાદીઓ સાથે અમે અમે ગતિશીલ શરૂ કરવાની જરૂર છે ખબર જગ્યા અને મકાન સાંકળો ફાળવણી. કે આનાથી સૉર્ટ કરો તે મુખ્ય છે how-- છે એક કડી થયેલ યાદી બિલ્ડિંગ તત્વો છે. તેથી ગતિશીલ ચાલો જોય માટે જગ્યા ફાળવી શકે છે, અને પછી સાંકળ તેને ઉમેરો દો. 

તેથી હવે અમે કંઇ કર્યું છે તે જુઓ. અમે જોય હેશ ત્યારે અમે હૅશકોડ 6 મળી. એરે સ્થાન 6 હવે નિર્દેશક એક કડી થયેલ યાદી વડા નિર્દેશ, અને હમણાં તે માત્ર છે એક કડી થયેલ યાદી તત્વ હોય. અને તે નોડ કડી થયેલ યાદી જોય છે. 

અમે જોય જોવાની જરૂર તેથી જો પાછળથી, અમે હમણાં જ ફરી જોય હેશ, અમે અમારા કારણ કે ફરીથી 6 છે હેશ વિધેય નિર્ધારિત છે. અને પછી અમે વડા ખાતે શરૂ આ યાદીની લિંક નિર્દેશ એરે સ્થાન દ્વારા 6, અને અમે ફરી વળવું કરી શકો છો જોય શોધવા માટે પ્રયાસ કરી છે કે સમગ્ર. અને અમે બિલ્ડ જો અમારા અસરકારક રીતે ટેબલ હેશ, અને અમારા હેશ વિધેય અસરકારક સારી માહિતી વિતરિત કરવા માટે, સરેરાશ તે દરેક કડી દરેક એરે સ્થાન પર યાદીઓ જો માપ 1/10 જશે માત્ર એક જ વિશાળ, કે હતી તે બધું સાથે કડી થયેલ યાદી. 

અમે વિશાળ કડી થયેલ છે કે વિતરિત તો 10 કડી થયેલ યાદીઓ સમગ્ર યાદી દરેક યાદી 1/10 માપ હશે. અને આમ 10 વખત ઝડપી મારફતે શોધવા માટે. તેથી આપણે ફરી આ કરવા દો. હવે રોસ હેશ દો. 

અને અમે તે કરવા જ્યારે રોસ, કહે દો અમે પાછા મેળવવા હેશ કોડ 2 છે. વેલ હવે અમે ગતિશીલ ફાળવણી નવા નોડ, અમે કે નોડ રોસ મૂકી અને અમે એરે સ્થાન હવે કહે 2, null પોઇન્ટ બદલે, એક કડી થયેલ વડા નિર્દેશ જેની માત્ર નોડ યાદી રોસ છે. અને અમે, અમે આ વધુ એક વખત કરી શકો છો રશેલ હેશ અને હૅશકોડ 4 મેળવી શકો છો. રચેલ મૂકી, એક નવા નોડ malloc નોડ, અને એરે સ્થાન કહે છે 4 હવે માથા પર નિર્દેશ જેની એક કડી થયેલ યાદી માત્ર તત્વ રચેલ બને છે. 

ઠીક પરંતુ શું થાય છે જો અમે એક અથડામણ છે? અમે અથડામણમાં કેવી રીતે હેન્ડલ જોવા દો અલગ chaining પદ્ધતિનો ઉપયોગ કરીને. માતાનો ફોબિ હેશ દો. અમે હૅશકોડ 6 છે. અમારા અગાઉના ઉદાહરણમાં આપણે જ હતા એરે માં શબ્દમાળાઓ સ્ટોર. આ એક સમસ્યા હતી. 

અમે clobber કરવા માંગો છો નથી જોય, અને અમે પહેલાથી જ કર્યું છે અમે કેટલાક ક્લસ્ટરીંગ મેળવી શકો છો કે જે જોઈ સમસ્યાઓ અમે પ્રયાસ અને જો પગલું દ્વારા અને ચકાસણી. પરંતુ શું જો અમે ફક્ત પ્રકારની આ અધિકાર, એ જ રીતે સારવાર? તે માત્ર એક તત્વ ઉમેરવા જેવું છે એક કડી થયેલ યાદી વડા છે. ફોબિ માટે આપણે માત્ર malloc જગ્યા દો. 

અમે ફોબિ આગામી નિર્દેશક પોઇન્ટ કહેવું પડશે કડી થયેલ યાદી ને જૂની માથા પર, અને પછી 6 માત્ર નિર્દેશ યાદીની લિંક નવા વડા. અને હવે અમે ફોબિ બદલ્યું, જુઓ. હવે અમે બે સ્ટોર કરી શકો છો હૅશકોડ 6 તત્વો, અને અમે કોઈ સમસ્યા નથી. 

કે ખૂબ ખૂબ બધા છે સાંકળ ત્યાં છે. અને સાંકળ ચોક્કસપણે છે કે પદ્ધતિ જો તમે માટે સૌથી વધુ અસરકારક હોઈ ચાલે તમે હેશ કોષ્ટકમાં માહિતી સ્ટોર કરવામાં આવે છે. પરંતુ આ મિશ્રણ એરે અને સંલગ્ન યાદીઓ સાથે મળીને ખરેખર હેશ ટેબલ રચવા માટે નાટકીય રીતે તમારા ક્ષમતા સુધારે છે માહિતી મોટા પ્રમાણમાં સંગ્રહ, અને ખૂબ જ ઝડપથી અને અસરકારક રીતે શોધવા કે માહિતી દ્વારા. 

એક હજુ પણ વધુ છે ત્યાં ત્યાં બહાર માહિતી બંધારણ તે પણ એક બીટ હોઈ શકે છે બાંયધરી બાબતમાં વધુ સારા કે અમારા નિવેશ, ઘટાડા અને લુકઅપ વખત પણ ઝડપી છે. અને અમે પ્રયત્નોમાં પર એક વિડિઓ છે કે જે જોશો. હું ડો લોયડ છું, આ CS50 છે.