[მუსიკის დაკვრა] DOUG LLOYD: ახლა თქვენ ვიცი, ბევრი რამ მასივები, და თქვენ იცით, ბევრი რამ უკავშირდება სიები. და ჩვენ განიხილავენ დადებითი და უარყოფითი მხარეები, ჩვენ განიხილეს, რომელიც უკავშირდება სიები შეგიძლიათ მიიღოთ უფრო დიდი და პატარა, მაგრამ მათ დასჭირდეს უფრო ზომა. მასივები, ბევრად უფრო მარტივია, რომ გამოყენება, მაგრამ ისინი შეზღუდულად იმდენი როგორც ჩვენ უნდა დააყენოთ ზომა მასივი თავიდანვე და მაშინ ჩვენ მოხდა ეს. მაგრამ ეს არის ის, რომ ჩვენ საკმაოდ ბევრი ამოწურა ყველა ჩვენი თემა დაკავშირებული სიები და მასივები. ან უნდა ჩვენ? იქნებ ჩვენ შეგვიძლია გავაკეთოთ რაღაც კიდევ უფრო შემოქმედებითი. და რომ ერთგვარი lends იდეა hash მაგიდა. ასე რომ hash მაგიდა, ჩვენ ვაპირებთ, რომ ცდილობენ გაერთიანდება მასივი უკავშირდება სიაში. ჩვენ ვაპირებთ, რომ მიიღოს უპირატესობა მასივი, როგორც შემთხვევითი წვდომის, რომელსაც შეუძლია მხოლოდ წასვლა მასივი ელემენტი 4 ან მასივი ელემენტს 8 გარეშე iterate მასშტაბით. ეს არის საკმაოდ სწრაფი, არა? მაგრამ ჩვენ ასევე გვინდა ჩვენი მონაცემებით სტრუქტურა შეძლებს იზრდება და მცირდება. ჩვენ არ გვჭირდება, ჩვენ არ გვინდა, რომ იყოს შეზღუდული. და ჩვენ გვინდა, რომ შეძლებს დამატება და წაშლა რამ ძალიან მარტივად, რომელიც თუ გავიხსენებთ, არის ძალიან რთული მასივი. და ჩვენ შეგვიძლია ვუწოდოთ ახალი რამ hash მაგიდა. და თუ განხორციელდა სწორად, ჩვენ ერთგვარი აღების უპირატესობა ორივე მონაცემები სტრუქტურები თქვენ უკვე ჩანს, კოლექტორები და დაკავშირებული სიები. Insertion შეიძლება დაიწყოს ტენდენცია თეტა 1. Theta ჩვენ ნამდვილად არ განიხილება, მაგრამ თეტა არის მხოლოდ საშუალო შემთხვევაში, რაც რეალურად მოხდება. თქვენ ყოველთვის არ აპირებს უარეს შემთხვევაში სცენარი, და თქვენ ყოველთვის არ აქვს საუკეთესო სცენარი, რა არის საშუალო სცენარი? ისე საშუალოდ ჩასმა შევიდა hash მაგიდა შეიძლება დაიწყოს მიიღოს ახლოს მუდმივი დროს. და წაშლა შეუძლიათ მიიღონ ახლოს, მუდმივი დრო. და საძიებელი შეგიძლიათ მიიღოთ ახლოს, მუდმივი დრო. That's-- ჩვენ არ გვაქვს მონაცემები სტრუქტურა ჯერ კიდევ, რომ არ შეუძლია, და ეს უკვე ჟღერს როგორც საკმაოდ დიდი რამ. ჩვენ მართლაც შემცირდეს უარყოფითი მხარეები თითოეული საკუთარი. იმისათვის რომ ეს სპექტაკლი განახლება თუმცა, ჩვენ უნდა გადახედოს, თუ როგორ დაამატოთ მონაცემთა სტრუქტურა. კერძოდ, ჩვენ გვინდა მონაცემები თავისთავად გვითხრათ სადაც ის უნდა წავიდეს სტრუქტურაში. და თუ ჩვენ მაშინ უნდა დაინახოს, თუ ის სტრუქტურა, თუ ჩვენ უნდა იპოვოს ის, ჩვენ გვინდა, რომ შევხედოთ მონაცემები ისევ და შეძლებს ეფექტურად, გამოყენებით მონაცემების, შემთხვევით ვებგვერდზე. უბრალოდ ეძებს მონაცემები უნდა გვქონდეს იდეა, სადაც ზუსტად ჩვენ ვაპირებ, რათა იპოვოს hash მაგიდა. ახლა მინუსი ქეშირების მაგიდა არის ის, რომ ისინი მართლაც საკმაოდ ცუდი შეკვეთით ან დახარისხება მონაცემები. და სინამდვილეში, თუ დაიწყება მათი გამოყენება, იმისათვის, ან სახის მონაცემები დაკარგავს ყველა უპირატესობა ადრე ჰქონდა თვალსაზრისით ჩასმა და წაშლა. დრო ხდება ახლოს თეტა ო, და ჩვენ, ძირითადად, უკან დაიხიეს შევიდა უკავშირდება სიაში. ასე რომ, ჩვენ მხოლოდ გვინდა გამოვიყენოთ hash მაგიდები, თუ ჩვენ არ აინტერესებს თუ არა მონაცემები დალაგებულია. იყიდება კონტექსტი, რომელშიც თქვენ მათი გამოყენება CS50 თქვენ, ალბათ, არ მაინტერესებს, რომ მონაცემები ინახება. ასე რომ hash მაგიდა არის კომბინაცია საქართველოს ორ მკაფიო ცალი რომელიც ჩვენ იცნობს. პირველი არის ფუნქცია, რომელიც როგორც წესი, ჩვენ მოვუწოდებთ hash ფუნქცია. და რომ hash ფუნქციის აპირებს დააბრუნებს არასამთავრობო უარყოფითი რიცხვი, რომელიც როგორც წესი, ჩვენ მოვუწოდებთ hashcode, OK? მეორე ნაწილი არის მასივი, რომელიც არის შეუძლია შენახვა მონაცემები ტიპის ჩვენ გსურთ განათავსოთ შევიდა მონაცემები სტრუქტურა. ჩვენ გამართავს off on უკავშირდება სიაში ელემენტს ახლა და მხოლოდ იწყება საფუძვლები hash მაგიდა მისაღებად თქვენი უფროსი გარშემო, და მაშინ ჩვენ, შესაძლოა, აფეთქება თქვენი აზრით ცოტა, როდესაც ჩვენ გაერთიანდება კოლექტორები და ბმული სიების ერთად. ძირითადი იდეა იმისა, არის, რომ ჩვენ გარკვეული მონაცემები. ჩვენ აწარმოებს, რომ მონაცემები ქეშირების ფუნქცია. ასე რომ, მონაცემების დამუშავება და ეს SpitS out ნომერი, OK? და მაშინ, რომ ნომერი ჩვენ უბრალოდ შესანახად მონაცემები ჩვენ გვინდა, რომ შესანახად array იმ ადგილას. ასე მაგალითად, ჩვენ, ალბათ ამ hash მაგიდა სტრიქონები. ეს მივიღე 10 ელემენტები, ასე რომ ჩვენ შეგვიძლია ჯდება 10 სიმებისათვის ის. მოდით ვთქვათ რომ ჩვენ გვინდა, რომ hash იოანე. ასე რომ, იოანე მონაცემები გვინდა ჩადეთ ამ hash მაგიდა სადღაც. სად ჩვენ ეს? ისე, როგორც წესი, რომელზეც მასივი ჯერჯერობით ჩვენ, ალბათ, მისთვის მასივი განთავსების 0. მაგრამ ახლა ჩვენ ახალ hash ფუნქცია. და ვთქვათ, რომ ჩვენ აწარმოებს ჯონ ამ გზით hash ფუნქცია და ის ფეხზე out 4. ისე, რომ სადაც ჩვენ ვართ აპირებს გსურთ დააყენა იოანე. ჩვენ გვინდა, რომ ჯონ მასივი ადგილმდებარეობა 4, იმიტომ, რომ თუ ჩვენ hash ჯონ ერთხელ მოდით ვთქვათ, შემდეგ ჩვენ გსურთ მოძებნოთ და ვნახოთ თუ ჯონ არსებობს ამ hash მაგიდასთან ყველა ჩვენ უნდა გავაკეთოთ აწარმოებს მეშვეობით იგივე hash ფუნქცია, მიიღოს ნომერი 4, და შევძლოთ ჯონ სასწრაფოდ ჩვენს მონაცემთა სტრუქტურას. ეს არის საკმაოდ კარგი. ვთქვათ, ახლა ამის გაკეთება კიდევ ერთხელ, ჩვენ გვინდა, რომ hash პოლ. ჩვენ გვინდა, რომ დაამატოთ პოლ ამ hash მაგიდა. ვთქვათ, რომ ამ დროს ჩვენ აწარმოებს პავლეს ქეშირების ფუნქცია, hashcode, რომელიც გენერირდება 6. ისე, ახლა ჩვენ შეგვიძლია პავლეს მასივი ადგილმდებარეობა 6. და თუ ჩვენ უნდა ეძებოთ თუ არა პავლე ამ hash მაგიდა, ყველა ჩვენ უნდა გავაკეთოთ არის აწარმოებს პოლ მეშვეობით hash ფუნქცია ერთხელ და ჩვენ ვაპირებთ, რომ კიდევ 6 კიდევ ერთხელ. და მაშინ ჩვენ შევჩერდეთ განთავსებულია მასივი ადგილმდებარეობა 6. პავლე იქ? თუ ასეა, ის hash მაგიდა. პავლე არ არის? ის არ არის hash მაგიდა. ეს საკმაოდ მარტივია. ახლა როგორ განვსაზღვროთ ქეშირების ფუნქცია? ისე ნამდვილად არ ლიმიტი ნომერი შესაძლებელია hash ფუნქციები. რეალურად არსებობს მთელი რიგი მართლაც, კარგი პირობა ინტერნეტში. არსებობს მთელი რიგი მართლაც, ნამდვილად ცუდი ინტერნეტში. ეს არის ასევე საკმაოდ ადვილი დაწერა ცუდი. ასე რომ, რაც up კარგი hash ფუნქცია, არა? ისე კარგი ქეშირების ფუნქცია უნდა გამოიყენონ მხოლოდ მონაცემები hashed, და ყველა მონაცემები hashed. ასე რომ, ჩვენ არ გვინდა, რომ გამოიყენოთ anything-- ჩვენ არ ითვალისწინებდეს არაფერი სხვა გარდა მონაცემები. და ჩვენ გვინდა, გამოვიყენოთ ყველა მონაცემები. ჩვენ არ გვინდა, რომ უბრალოდ გამოიყენოთ ნაჭერი ეს, ჩვენ გვინდა გამოვიყენოთ ყველა ის. ქეშირების ფუნქცია უნდა ასევე იქნება დეტერმინისტული. რას ნიშნავს ეს? ისე, ეს იმას ნიშნავს, რომ ყოველ ჯერზე ჩვენ გაივლის ზუსტად იგივე ნაჭერი მონაცემები ქეშირების ფუნქცია ჩვენ ყოველთვის მიიღოს იგივე hashcode out. თუ მე გაივლის ჯონ შევიდა hash ფუნქცია მე გავიდნენ 4. მე უნდა შეეძლოს უნდა გავაკეთოთ, რომ 10,000 ჯერ და მე ყოველთვის 4. ასე რომ, არ შემთხვევითი ნომრები ეფექტურად შეიძლება ჩართული ჩვენი hash tables-- ჩვენს hash ფუნქციები. ქეშირების ფუნქცია ასევე უნდა ერთნაირად გავრცელება მონაცემები. თუ ყოველ ჯერზე თქვენ აწარმოებს მონაცემების საშუალებით hash ფუნქცია მიიღებთ hashcode 0, ეს, ალბათ, არ არის იმდენად დიდი, არა? თქვენ ალბათ მინდა, რომ დიდი სპექტრი hash კოდები. ასევე რამ შეიძლება გავრცელდეს მთელ მაგიდაზე. და ასევე კარგი იქნება, თუ ნამდვილად ანალოგიური მონაცემები, როგორიცაა ჯონ და ჯონათან, იქნებ იყო მოდებული, რომ მოხდეს სხვადასხვა ადგილას hash მაგიდა. ეს იქნება ლამაზი უპირატესობა. აი, მაგალითად, ქეშირების ფუნქცია. მე დავწერე ეს ერთი გოლი ადრე. ეს არ არის განსაკუთრებით კარგი ქეშირების ფუნქცია მიზეზით, რომ ნამდვილად არ დათვი შესვლის უფლება. მაგრამ თქვენ ხედავთ, რა ხდება აქ? როგორც ჩანს, ჩვენ ვაცხადებთ ცვლადი მოუწოდა თანხა და განსაზღვრავს ის ტოლია 0. და შემდეგ, როგორც ჩანს, მე ვაკეთებ რაღაც ასე რომ, სანამ strstr [j] არ არის ტოლი რომ წარმატებული 0. რას ვაკეთებ იქ? ეს არის, ძირითადად, მხოლოდ სხვა გზა განხორციელების [? Strl?] და გამოვლენის, როდესაც თქვენ მიაღწია ბოლოს სიმებიანი. ასე რომ, არ უნდა რეალურად გამოვთვალოთ სიგრძეზე სიმებიანი, მე უბრალოდ გამოყენებით, როდესაც მე მოხვდა წარმატებული 0 ხასიათი მე ვიცი, მე მიაღწია ბოლოს სიმებიანი. და მაშინ მე ვაპირებ შენარჩუნება iterating მეშვეობით, რომ ტექსტი, დასძინა strstr [j] თანხა, და შემდეგ დღის ბოლოს ვაპირებ დაბრუნებას თანხა mod HASH_MAX. ძირითადად ეს ყველაფერი hash ფუნქცია აკეთებს დასძინა მდე ყველა ASCII ღირებულებები ჩემი სიმებიანი და შემდეგ ეს დაბრუნების ზოგიერთი hashcode modded მიერ HASH_MAX. ეს, ალბათ, ზომა ჩემი მასივი, არა? მე არ მინდა, რომ იყოს მიღების hash კოდები, თუ ჩემი array არის ზომა 10, მე არ მინდა, რომ იყოს მიღების out hash კოდები 11, 12, 13, მე ვერ დააყენა რამ შევიდა იმ ადგილას მასივი, რომ იქნება უკანონო. მე განიცდიან სეგმენტაცია ბრალი. ახლა აქ არის კიდევ ერთი სწრაფი განზე. საერთოდ თქვენ ალბათ არ აპირებს გსურთ დაწეროთ თქვენი საკუთარი hash ფუნქციები. ეს არის რეალურად ცოტა ხელოვნება, არ არის მეცნიერება. და იქ ბევრი რომ გადადის მათ. ინტერნეტ, როგორც ვთქვი, არის სრული ნამდვილად კარგი hash ფუნქციები, და თქვენ უნდა გამოიყენოთ ინტერნეტში მოვძებნოთ hash ფუნქციები, რადგან ეს მართლაც უბრალოდ სახის ზედმეტი ნარჩენები დრო შექმნათ თქვენი საკუთარი. თქვენ შეგიძლიათ დაწეროთ მარტივი პირობა ტესტირების მიზნით. მაგრამ როდესაც თქვენ რეალურად ვაპირებთ დაიწყოს ჰეშირება მონაცემები და შენახვის შევიდა hash მაგიდა თქვენ ალბათ აპირებს მინდა გამოიყენოს ზოგიერთი ფუნქცია, რომელიც გენერირდება თქვენ, რომ არსებობს ინტერნეტში. თუ თქვენ უბრალოდ დარწმუნებული უნდა იყოს მოჰყავთ თქვენი წყაროები. არ არსებობს მიზეზი, რომ plagiarize არაფერი აქ. კომპიუტერული მეცნიერებისა არის ნამდვილად იზრდება, და მართლაც ღირებულებები ღია, და ეს მართლაც მნიშვნელოვანია, მოჰყავთ თქვენი წყაროები ისე, რომ ხალხი შეგიძლიათ მიიღოთ მოხსენიება for მუშაობა, რომ ისინი აკეთებს, რომ საზოგადოების კეთილდღეობაზე. ასე რომ ყოველთვის იქნება sure-- და არა მხოლოდ hash ფუნქციები, მაგრამ ზოგადად, როდესაც თქვენ გამოყენება კოდი გარეთ წყარო, ყოველთვის მოჰყავთ თქვენი წყარო. მისცეს საკრედიტო იმ პირს, ვინც ეს გააკეთა ზოგიერთი მუშაობა, ასე რომ თქვენ არ უნდა. OK, ასე რომ მოდით დავუბრუნდეთ ამ hash მაგიდა მეორე. ეს არის, სადაც დავტოვეთ შემდეგ, ჩვენ ჩასმული იოანე და პავლე ამ hash მაგიდა. ხედავთ პრობლემა აქ? თქვენ შეიძლება ნახოთ ორი. მაგრამ, კერძოდ, თქვენ ვხედავ ამ შესაძლო პრობლემა? რა მოხდება, თუ hash Ringo, და ეს გამოდის, რომ დამუშავების შემდეგ რომ მონაცემები hash ფუნქცია Ringo ასევე გამომუშავებული hashcode 6. მე უკვე მივიღე მონაცემები hashcode-- მასივი ადგილმდებარეობა 6. ასე რომ, ეს, ალბათ, იქნება ცოტა პრობლემა ჩემთვის ახლა, არა? ჩვენ მოვუწოდებთ ამ შეჯახება. და შეჯახება ხდება, როდესაც ორი ცალი მონაცემები აწარმოებს მეშვეობით იგივე hash ფუნქცია გამოიღო იგივე hashcode. სავარაუდოდ, ჩვენ მაინც მინდა, რომ ორივე ცალი მონაცემები hash მაგიდა, წინააღმდეგ შემთხვევაში, ჩვენ არ უნდა იყოს გაშვებული Ringo თვითნებურად მეშვეობით ქეშირების ფუნქცია. ჩვენ, სავარაუდოდ, სურთ მიიღონ Ringo, რომ მასივი. როგორ გავაკეთოთ, რომ მიუხედავად იმისა, თუ იგი და პავლე სარგებელი hashcode 6? ჩვენ არ გვინდა, რომ გადავაწერო Paul, ჩვენ გვინდა, პავლე იყოს იქ. ასე რომ, ჩვენ უნდა მოვძებნოთ გზა ელემენტების hash მაგიდა რომელიც კვლავ ინარჩუნებს ჩვენი სწრაფი ჩასმა და სწრაფი up. და ერთი გზა გაუმკლავდეთ ის არის, რომ ამის გაკეთება რაღაც მოუწოდა ხაზოვანი probing. ამ მეთოდით, თუ ჩვენ გვაქვს შეჯახება, ასევე, რა ვქნათ? ისე ჩვენ ვერ დააყენა მას მასივი ადგილმდებარეობა 6, ან რასაც hashcode გამომუშავებული, მოდით დააყენა მას hashcode პლუს 1. და თუ ეს სრული მოდით მას hashcode plus 2. სასარგებლოდ ამ ყოფნა თუ ის არ არის ზუსტად სადაც ჩვენ ვფიქრობთ, ის არის, და ჩვენ უნდა დაიწყოს ეძებს, იქნებ ჩვენ არ უნდა წავიდეს შორს. შესაძლოა, ჩვენ არ უნდა ვეძებოთ ყველა N ელემენტების hash მაგიდა. შესაძლოა, ჩვენ უნდა ვეძებოთ რამდენიმე მათგანი. ასე რომ, ჩვენ ჯერ კიდევ მოვლის მიმართ საშუალო შემთხვევაში, რომ ახლოს 1 vs ახლოს n, იქნებ, რომ ვიმუშავებთ. მოდით ვნახოთ, თუ როგორ ეს შეიძლება შეიმუშაოს სინამდვილეში. მოდით ვნახოთ, თუ შესაძლოა, ჩვენ შეუძლია აღმოაჩინოს პრობლემა, რომელიც შეიძლება მოხდეს აქ. ვთქვათ, hash Bart. ასე რომ, ახლა ჩვენ ვაპირებთ აწარმოებს ახალი ნაკრები სტრიქონები მეშვეობით ქეშირების ფუნქცია, და ჩვენ აწარმოებს Bart მეშვეობით hash ფუნქცია, მივიღებთ hashcode 6. ჩვენ შევხედოთ, ჩვენ ვხედავთ, 6 ცარიელი, ასე რომ ჩვენ შეგვიძლია Bart არსებობს. ახლა ჩვენ hash ლიზა და რომ ასევე ქმნის hashcode 6. ისე, ახლა რომ ჩვენ გამოყენებისას ხაზოვანი საცდელი მეთოდით იწყება 6, ჩვენ ვხედავთ, რომ 6 სავსეა. ჩვენ ვერ დააყენა ლიზა 6. ასე რომ, სად წავიდეთ? წამო 7. 7 ცარიელი, ასე რომ, რომელიც მუშაობს. მოდით დააყენა Lisa არსებობს. ახლა ჩვენ hash Homer და მივიღებთ 7. OK კარგად ვიცით, რომ 7 სრული ახლა, ასე რომ ჩვენ ვერ დააყენა Homer არსებობს. მოდით წავიდეთ 8. 8 ხელმისაწვდომი? ჰო, და 8 ახლო 7, ასე რომ, თუ ჩვენ უნდა დაიწყოს ეძებს ჩვენ არ ვაპირებ წავიდეთ შორს. ასე რომ, მოდით ვთქვათ Homer დილის 8. ახლა ჩვენ hash მეგი და ბრუნდება 3, მადლობა ღმერთს ჩვენ შეუძლია მხოლოდ დააყენა მეგი არსებობს. ჩვენ არ გვაქვს რაიმე ერთგვარი საცდელი რომ. ახლა ჩვენ hash მარჯი, და მარჯი ასევე დააბრუნებს 6. ისე 6 სრული, 7 სავსეა, 8 სავსეა, 9, ყველა უფლება მადლობა ღმერთს, 9 ცარიელია. შემიძლია დააყენა მარჯი at 9. უკვე ჩვენ ვხედავთ, რომ ჩვენ ვიწყებთ ეს პრობლემა, სადაც ახლა ჩვენ დაწყებული მონაკვეთის რამ სახის of შორს მათი hash კოდები. და რომ თეტა 1, საშუალო შემთხვევაში, მუდმივი, იწყება მისაღებად ცოტა more-- დაწყებული, როგორც წესი, ცოტა მეტი მიმართ თეტა ო. ჩვენ ვიწყებთ კარგავენ, რომ უპირატესობა hash მაგიდები. ეს პრობლემა, რომელიც ჩვენ ვნახეთ არის რაღაც მოუწოდა კლასტერიზაცია. და რა არის ნამდვილად ცუდი კლასტერული არის, რომ ერთხელ თქვენ ახლა აქვს ორი ელემენტები, რომლებიც გვერდით მხარეს ეს ხდის კიდევ უფრო სავარაუდოა, თქვენ გაქვთ ორმაგი შანსი, რომ თქვენ აპირებს კიდევ ერთი შეჯახება რომ კასეტური და კასეტური გაიზრდება ერთი. და თქვენ შენარჩუნება იზრდება და იზრდება თქვენი ალბათობა შეჯახება. და საბოლოოდ, ეს როგორც ცუდი არ დახარისხება მონაცემები ყველა. მეორე პრობლემა, მიუხედავად იმისა, რომ ჩვენ მაინც, და ჯერჯერობით ამ ეტაპზე, ვიყავით სახის გაგება, თუ რა hash მაგიდა, ჩვენ ჯერ კიდევ მხოლოდ ოთახი 10 სიმები. თუ ჩვენ გვინდა გავაგრძელოთ hash მოქალაქეებს Springfield, ჩვენ შეიძლება მხოლოდ 10 მათგანი იქ. და თუ ჩვენ ვცდილობთ და დაამატოთ მე -11 და მე -12, ჩვენ არ აქვს ადგილი იმისათვის, რომ მათ. ჩვენ შეიძლება მხოლოდ spinning გარშემო წრეების ცდილობს იპოვოს ცარიელი ადგილზე, და ჩვენ, შესაძლოა, დავრჩებოდით უსასრულო ციკლი. ასე რომ, ეს ერთგვარი lends იმ აზრს, რაღაც მოუწოდა მიჯაჭვის. და ეს არის, სადაც ჩვენ ვაპირებთ, რათა დაკავშირებული სიები ისევ სურათს. რა მოხდება, თუ ნაცვლად შენახვის მხოლოდ მონაცემები თავად მასივი, ყოველ ელემენტს მასივი იქნებოდა გამართავს მრავალჯერადი ცალი მონაცემები? ისე, რომ აზრი არ აქვს, არა? ჩვენ ვიცით, რომ მასივი მხოლოდ hold-- თითოეული ელემენტის მასივი შეიძლება მხოლოდ ერთი ცალი მონაცემების რომ მონაცემები ტიპის. მაგრამ რა, თუ რომ მონაცემები ტიპის არის დაკავშირებული სიაში, უფლება? მერე რა, რომ ყოველ ელემენტს მასივი იყო მომცეთ ხელმძღვანელი უკავშირდება სიაში? და მაშინ ჩვენ შეგვიძლია ავაშენოთ იმ დაკავშირებული სიები და იზრდება მათ თვითნებურად, იმიტომ, რომ უკავშირდება სიები საშუალებას ჩვენთვის იზრდება და მცირდება ბევრი სხვა მოქნილად ვიდრე მასივი აკეთებს. ასე რომ, თუ ჩვენ ახლა გამოყენება, ჩვენ ბერკეტები ამ, არა? ვიწყებთ იზრდება ამ ჯაჭვების აქედან მასივი ადგილას. ახლა ჩვენ შეგვიძლია შეესაბამება უსასრულო თანხის მონაცემები, ან არ არის უსასრულო, თვითნებური თანხა მონაცემები, ჩვენი hash მაგიდა გარეშე ოდესმე გაშვებული შევიდა პრობლემა შეჯახება. ჩვენ ასევე აღმოფხვრილი კლასტერული ამით. და კარგად ვიცით, რომ როდესაც ჩვენ ჩადეთ შევიდა უკავშირდება სიაში, თუ გავიხსენებთ ჩვენი ვიდეო უკავშირდება სიები, ცალკე დაკავშირებული სიები და ორმაგად უკავშირდება სიები, ეს არის მუდმივი დრო ოპერაცია. ჩვენ ვამატებთ ფრონტზე. და თვალი, კარგად ვიცით, რომ ეძებოთ უკავშირდება სიაში შეიძლება იყოს პრობლემა, არა? ჩვენ უნდა მოძებნოთ მეშვეობით ეს თავიდან ბოლომდე. არ არის შემთხვევითი ხელმისაწვდომობა უკავშირდება სიაში. მაგრამ თუ ნაცვლად, რომ ერთი უკავშირდება სიაში, სადაც საძიებელი იქნება ო ო, ახლა ჩვენ გვაქვს 10 უკავშირდება სიები, ან 1000 უკავშირდება სიები, ახლა ეს ო ო იყოფა 10, ან O ო იყოფა 1,000. და მაშინ, როცა ჩვენ ვსაუბრობთ თეორიულად შესახებ სირთულის ჩვენ იგნორირება მუდმივები, რეალურ მსოფლიოს ეს ყველაფერი რეალურად აქვს, არა? ჩვენ, ფაქტობრივად, შეამჩნევთ რომ ეს მოხდება აწარმოებს 10 ჯერ უფრო სწრაფად, ან 1,000 ჯერ უფრო სწრაფად, იმიტომ, რომ ჩვენ დარიგება ერთი ხანგრძლივი ჯაჭვის მასშტაბით 1,000 მცირე ქსელები. ასე რომ, ყოველ ჯერზე ჩვენ უნდა ვეძებოთ ერთ-ერთ იმ ჯაჭვების ჩვენ შეგვიძლია იგნორირება 999 ჯაჭვების ჩვენ არ აინტერესებს შესახებ, და უბრალოდ ძებნის, რომ ერთი. რომელი საშუალოდ 1,000 ჯერ უფრო მოკლეა. ასე რომ, ჩვენ ჯერ კიდევ არის ერთგვარი მოვლის მიმართ ეს საშუალო შემთხვევაში მიმდინარეობს მუდმივი, მაგრამ მხოლოდ იმიტომ, რომ ჩვენ ოპერაციული გამყოფი ზოგიერთი დიდი მუდმივი ფაქტორი. ვნახოთ, როგორ ეს შეიძლება რეალურად გამოიყურება თუმცა. ასე რომ, ეს იყო hash მაგიდა გვქონდა სანამ ჩვენ განაცხადა hash მაგიდა რომელიც იყო შეუძლია შენახვა 10 სიმები. ჩვენ არ ვაპირებთ გავაკეთოთ, რომ მთელი მსოფლიოს მასშტაბით. ჩვენ უკვე ვიცით, შეზღუდვები, რომელიც საშუალებას. ახლა ჩვენი hash მაგიდა იქნება მასივი 10 კვანძების, მითითებას ხელმძღვანელებს დაკავშირებული სიები. და ახლა ეს null. თითოეული ერთი იმ 10 მითითებას null. არაფერია ჩვენს hash მაგიდა ახლავე. ახლა დავიწყოთ დააყენოს გარკვეული რამ ამ hash მაგიდა. და ვნახოთ, თუ როგორ ეს მეთოდი აპირებს ისარგებლოს ჩვენთვის ცოტა. მოდით ახლა hash Joey. ჩვენ აწარმოებს სიმებიანი Joey მეშვეობით ქეშირების ფუნქცია და ჩვენ დაუბრუნოს 6. ისე, რა ვქნათ? ისე ახლა მუშაობს დაკავშირებული სიები, ჩვენ არ მუშაობს მასივები. და როდესაც ჩვენ ვმუშაობთ უკავშირდება სიები ჩვენ იცით, ჩვენ უნდა დავიწყოთ დინამიურად გამოყოფის სივრცე და სამშენებლო ქსელები. სწორედ ერთგვარი how-- იმ ძირითადი ელემენტები მშენებლობის უკავშირდება სიაში. მოდით დინამიურად გამოყოს ფართი Joey, და მაშინ მოდით დაამატოთ მას ჯაჭვი. ასე რომ, ახლა გამოიყურება, რაც ჩვენ გავაკეთეთ. როდესაც ჩვენ hash Joey მივიღეთ hashcode 6. ახლა მაჩვენებელი მასივი ადგილმდებარეობა 6 მიუთითებს, რომ ხელმძღვანელი უკავშირდება სია, და ახლა ეს მხოლოდ ელემენტს უკავშირდება სიაში. და კვანძის, რომ უკავშირდება სია Joey. ასე რომ, თუ ჩვენ უნდა ეძებოთ Joey შემდეგ, ჩვენ უბრალოდ hash Joey ერთხელ, ჩვენ კიდევ ისევ 6 იმიტომ, რომ ჩვენი ქეშირების ფუნქცია არის deterministic. და მერე ჩვენ დავიწყოთ ხელმძღვანელი უკავშირდება სიაში აღნიშნა მიერ მასივი ადგილმდებარეობა 6, და ჩვენ შეგვიძლია iterate მასშტაბით, რომ ცდილობს იპოვოს Joey. და თუ ჩვენ ჩვენს hash მაგიდა ეფექტურად, და ჩვენი ქეშირების ფუნქცია ეფექტურად გავრცელება მონაცემები კარგად, საშუალოდ თითოეულ იმ დაკავშირებული სიების ყოველ მასივი ადგილმდებარეობა იქნება 1/10 ზომა, თუ ჩვენ უბრალოდ ჰქონდა, როგორც ერთი დიდი უკავშირდება სიაში ყველაფერი ეს. თუ ჩვენ გავრცელება, რომ დიდი უკავშირდება სია მასშტაბით 10 დაკავშირებული სიები თითოეულ სია იქნება 1/10 ზომა. და, შესაბამისად, 10-ჯერ უფრო სწრაფად ძებნის საშუალებით. ასე რომ, მოდით ეს კიდევ ერთხელ გავაკეთოთ. მოდით ახლა hash როსი. და მოდით ვთქვათ, Ross, როდესაც ჩვენ გავაკეთებთ, რომ hash კოდი მივიღებთ უკან 2. ისე, ახლა ჩვენ დინამიურად გამოყოფს ახალი კვანძის, ჩვენ როს, რომ კვანძის, და ვამბობთ ახლა მასივი ადგილმდებარეობა 2, ნაცვლად მიუთითებს null, მიუთითებს, რომ ხელმძღვანელი უკავშირდება სია, რომელთა ერთადერთი კვანძის როსი. და ჩვენ შეგვიძლია ამის გაკეთება კიდევ ერთხელ, ჩვენ შეგიძლიათ hash Rachel და მიიღეთ hashcode 4. malloc ახალი კვანძის, დააყენა რეიჩელ კვანძის, და აცხადებენ, რომ მასივი ადგილმდებარეობა 4 ახლა მიუთითებს უფროსი უკავშირდება სია, რომელთა მხოლოდ ელემენტი ხდება, რომ რეიჩელ. OK, მაგრამ რა მოხდება, თუ ჩვენ შეჯახება? ვნახოთ, როგორ გაუმკლავდეს collisions გამოყენებით ცალკე chaining მეთოდი. მოდით hash Phoebe. მივიღებთ hashcode 6. ჩვენი წინა მაგალითად ჩვენ მხოლოდ შენახვის სიმები მასივი. ეს იყო პრობლემა. ჩვენ არ გვინდა, რომ clobber Joey, და ჩვენ უკვე ჩანს, რომ ჩვენ შეიძლება რაღაც კლასტერული პრობლემა თუ ჩვენ ვცდილობთ და ნაბიჯი მეშვეობით და გამოძიება. მაგრამ თუ ჩვენ მხოლოდ სახის მკურნალობა იგივე გზით, არა? ეს, ისევე, დასძინა ელემენტს ხელმძღვანელი უკავშირდება სიაში. მოდით უბრალოდ malloc ფართი Phoebe. ჩვენ ვიტყვით, Phoebe მომდევნო მაჩვენებელი რაოდენობა ძველი ხელმძღვანელი უკავშირდება სია, და შემდეგ 6 მხოლოდ მიუთითებს ახალი ხელმძღვანელი უკავშირდება სიაში. ახლა კი გამოიყურება, ჩვენ შეიცვალა Phoebe in. ახლა ჩვენ შეგვიძლია შესანახად ორი ელემენტების hashcode 6, და ჩვენ არ გვაქვს არანაირი პრობლემა. ეს არის საკმაოდ ბევრი ყველა არ არის chaining. და chaining ნამდვილად მეთოდი, რომელიც არის იქნება ყველაზე ეფექტური, თუ თქვენ შენახვის მონაცემების hash მაგიდა. მაგრამ ეს კომბინაცია კოლექტორები და დაკავშირებული სიები ერთად შექმნან hash მაგიდა ნამდვილად მკვეთრად აუმჯობესებს თქვენი უნარი შესანახად დიდი რაოდენობით მონაცემები და ძალიან სწრაფად და ეფექტურად ძიება მეშვეობით, რომ მონაცემები. არსებობს კიდევ ერთი მონაცემები სტრუქტურა არსებობს რომ შეიძლება იყოს ცოტა უკეთესი კუთხით გარანტიას რომ ჩვენი ჩასმა, წაშლა, და ეძებოთ ჯერ უფრო სწრაფად. ჩვენ დავინახავთ, რომ ვიდეო ლელო. მე Doug Lloyd, ეს არის CS50.