1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:01,900 [მუსიკის დაკვრა] 3 00:00:01,900 --> 00:00:05,710 4 00:00:05,710 --> 00:00:09,150 >> DOUG LLOYD: ახლა თქვენ ვიცი, ბევრი რამ მასივები, 5 00:00:09,150 --> 00:00:11,610 და თქვენ იცით, ბევრი რამ უკავშირდება სიები. 6 00:00:11,610 --> 00:00:13,650 და ჩვენ განიხილავენ დადებითი და უარყოფითი მხარეები, ჩვენ 7 00:00:13,650 --> 00:00:16,620 განიხილეს, რომელიც უკავშირდება სიები შეგიძლიათ მიიღოთ უფრო დიდი და პატარა, 8 00:00:16,620 --> 00:00:18,630 მაგრამ მათ დასჭირდეს უფრო ზომა. 9 00:00:18,630 --> 00:00:22,359 მასივები, ბევრად უფრო მარტივია, რომ გამოყენება, მაგრამ ისინი შეზღუდულად იმდენი 10 00:00:22,359 --> 00:00:24,900 როგორც ჩვენ უნდა დააყენოთ ზომა მასივი თავიდანვე 11 00:00:24,900 --> 00:00:26,910 და მაშინ ჩვენ მოხდა ეს. 12 00:00:26,910 --> 00:00:30,470 >> მაგრამ ეს არის ის, რომ ჩვენ საკმაოდ ბევრი ამოწურა ყველა ჩვენი თემა 13 00:00:30,470 --> 00:00:33,040 დაკავშირებული სიები და მასივები. 14 00:00:33,040 --> 00:00:34,950 ან უნდა ჩვენ? 15 00:00:34,950 --> 00:00:37,720 იქნებ ჩვენ შეგვიძლია გავაკეთოთ რაღაც კიდევ უფრო შემოქმედებითი. 16 00:00:37,720 --> 00:00:40,950 და რომ ერთგვარი lends იდეა hash მაგიდა. 17 00:00:40,950 --> 00:00:46,680 >> ასე რომ hash მაგიდა, ჩვენ ვაპირებთ, რომ ცდილობენ გაერთიანდება მასივი უკავშირდება სიაში. 18 00:00:46,680 --> 00:00:49,520 ჩვენ ვაპირებთ, რომ მიიღოს უპირატესობა მასივი, როგორც შემთხვევითი წვდომის, 19 00:00:49,520 --> 00:00:53,510 რომელსაც შეუძლია მხოლოდ წასვლა მასივი ელემენტი 4 ან მასივი ელემენტს 8 20 00:00:53,510 --> 00:00:55,560 გარეშე iterate მასშტაბით. 21 00:00:55,560 --> 00:00:57,260 ეს არის საკმაოდ სწრაფი, არა? 22 00:00:57,260 --> 00:01:00,714 >> მაგრამ ჩვენ ასევე გვინდა ჩვენი მონაცემებით სტრუქტურა შეძლებს იზრდება და მცირდება. 23 00:01:00,714 --> 00:01:02,630 ჩვენ არ გვჭირდება, ჩვენ არ გვინდა, რომ იყოს შეზღუდული. 24 00:01:02,630 --> 00:01:04,588 და ჩვენ გვინდა, რომ შეძლებს დამატება და წაშლა რამ 25 00:01:04,588 --> 00:01:08,430 ძალიან მარტივად, რომელიც თუ გავიხსენებთ, არის ძალიან რთული მასივი. 26 00:01:08,430 --> 00:01:11,650 და ჩვენ შეგვიძლია ვუწოდოთ ახალი რამ hash მაგიდა. 27 00:01:11,650 --> 00:01:15,190 >> და თუ განხორციელდა სწორად, ჩვენ ერთგვარი აღების 28 00:01:15,190 --> 00:01:18,150 უპირატესობა ორივე მონაცემები სტრუქტურები თქვენ უკვე ჩანს, 29 00:01:18,150 --> 00:01:19,880 კოლექტორები და დაკავშირებული სიები. 30 00:01:19,880 --> 00:01:23,070 Insertion შეიძლება დაიწყოს ტენდენცია თეტა 1. 31 00:01:23,070 --> 00:01:26,207 Theta ჩვენ ნამდვილად არ განიხილება, მაგრამ თეტა არის მხოლოდ საშუალო შემთხვევაში, 32 00:01:26,207 --> 00:01:27,540 რაც რეალურად მოხდება. 33 00:01:27,540 --> 00:01:29,680 თქვენ ყოველთვის არ აპირებს უარეს შემთხვევაში სცენარი, 34 00:01:29,680 --> 00:01:32,555 და თქვენ ყოველთვის არ აქვს საუკეთესო სცენარი, რა არის 35 00:01:32,555 --> 00:01:33,900 საშუალო სცენარი? 36 00:01:33,900 --> 00:01:36,500 >> ისე საშუალოდ ჩასმა შევიდა hash მაგიდა 37 00:01:36,500 --> 00:01:39,370 შეიძლება დაიწყოს მიიღოს ახლოს მუდმივი დროს. 38 00:01:39,370 --> 00:01:41,570 და წაშლა შეუძლიათ მიიღონ ახლოს, მუდმივი დრო. 39 00:01:41,570 --> 00:01:44,440 და საძიებელი შეგიძლიათ მიიღოთ ახლოს, მუდმივი დრო. 40 00:01:44,440 --> 00:01:48,600 That's-- ჩვენ არ გვაქვს მონაცემები სტრუქტურა ჯერ კიდევ, რომ არ შეუძლია, 41 00:01:48,600 --> 00:01:51,180 და ეს უკვე ჟღერს როგორც საკმაოდ დიდი რამ. 42 00:01:51,180 --> 00:01:57,010 ჩვენ მართლაც შემცირდეს უარყოფითი მხარეები თითოეული საკუთარი. 43 00:01:57,010 --> 00:01:59,160 >> იმისათვის რომ ეს სპექტაკლი განახლება თუმცა, ჩვენ 44 00:01:59,160 --> 00:02:03,580 უნდა გადახედოს, თუ როგორ დაამატოთ მონაცემთა სტრუქტურა. 45 00:02:03,580 --> 00:02:07,380 კერძოდ, ჩვენ გვინდა მონაცემები თავისთავად გვითხრათ 46 00:02:07,380 --> 00:02:09,725 სადაც ის უნდა წავიდეს სტრუქტურაში. 47 00:02:09,725 --> 00:02:12,850 და თუ ჩვენ მაშინ უნდა დაინახოს, თუ ის სტრუქტურა, თუ ჩვენ უნდა იპოვოს ის, 48 00:02:12,850 --> 00:02:16,610 ჩვენ გვინდა, რომ შევხედოთ მონაცემები ისევ და შეძლებს ეფექტურად, 49 00:02:16,610 --> 00:02:18,910 გამოყენებით მონაცემების, შემთხვევით ვებგვერდზე. 50 00:02:18,910 --> 00:02:20,700 უბრალოდ ეძებს მონაცემები უნდა გვქონდეს 51 00:02:20,700 --> 00:02:25,890 იდეა, სადაც ზუსტად ჩვენ ვაპირებ, რათა იპოვოს hash მაგიდა. 52 00:02:25,890 --> 00:02:28,770 >> ახლა მინუსი ქეშირების მაგიდა არის ის, რომ ისინი მართლაც 53 00:02:28,770 --> 00:02:31,770 საკმაოდ ცუდი შეკვეთით ან დახარისხება მონაცემები. 54 00:02:31,770 --> 00:02:34,970 და სინამდვილეში, თუ დაიწყება მათი გამოყენება, იმისათვის, ან სახის 55 00:02:34,970 --> 00:02:37,990 მონაცემები დაკარგავს ყველა უპირატესობა ადრე 56 00:02:37,990 --> 00:02:40,710 ჰქონდა თვალსაზრისით ჩასმა და წაშლა. 57 00:02:40,710 --> 00:02:44,060 დრო ხდება ახლოს თეტა ო, და ჩვენ, ძირითადად, 58 00:02:44,060 --> 00:02:45,530 უკან დაიხიეს შევიდა უკავშირდება სიაში. 59 00:02:45,530 --> 00:02:48,850 ასე რომ, ჩვენ მხოლოდ გვინდა გამოვიყენოთ hash მაგიდები, თუ ჩვენ არ აინტერესებს 60 00:02:48,850 --> 00:02:51,490 თუ არა მონაცემები დალაგებულია. 61 00:02:51,490 --> 00:02:54,290 იყიდება კონტექსტი, რომელშიც თქვენ მათი გამოყენება CS50 62 00:02:54,290 --> 00:02:58,900 თქვენ, ალბათ, არ მაინტერესებს, რომ მონაცემები ინახება. 63 00:02:58,900 --> 00:03:03,170 >> ასე რომ hash მაგიდა არის კომბინაცია საქართველოს ორ მკაფიო ცალი 64 00:03:03,170 --> 00:03:04,980 რომელიც ჩვენ იცნობს. 65 00:03:04,980 --> 00:03:07,930 პირველი არის ფუნქცია, რომელიც როგორც წესი, ჩვენ მოვუწოდებთ hash ფუნქცია. 66 00:03:07,930 --> 00:03:11,760 და რომ hash ფუნქციის აპირებს დააბრუნებს არასამთავრობო უარყოფითი რიცხვი, რომელიც 67 00:03:11,760 --> 00:03:14,870 როგორც წესი, ჩვენ მოვუწოდებთ hashcode, OK? 68 00:03:14,870 --> 00:03:20,230 მეორე ნაწილი არის მასივი, რომელიც არის შეუძლია შენახვა მონაცემები ტიპის ჩვენ 69 00:03:20,230 --> 00:03:22,190 გსურთ განათავსოთ შევიდა მონაცემები სტრუქტურა. 70 00:03:22,190 --> 00:03:24,310 ჩვენ გამართავს off on უკავშირდება სიაში ელემენტს ახლა 71 00:03:24,310 --> 00:03:27,810 და მხოლოდ იწყება საფუძვლები hash მაგიდა მისაღებად თქვენი უფროსი გარშემო, 72 00:03:27,810 --> 00:03:30,210 და მაშინ ჩვენ, შესაძლოა, აფეთქება თქვენი აზრით ცოტა, როდესაც ჩვენ 73 00:03:30,210 --> 00:03:32,920 გაერთიანდება კოლექტორები და ბმული სიების ერთად. 74 00:03:32,920 --> 00:03:35,590 >> ძირითადი იდეა იმისა, არის, რომ ჩვენ გარკვეული მონაცემები. 75 00:03:35,590 --> 00:03:37,860 ჩვენ აწარმოებს, რომ მონაცემები ქეშირების ფუნქცია. 76 00:03:37,860 --> 00:03:41,980 ასე რომ, მონაცემების დამუშავება და ეს SpitS out ნომერი, OK? 77 00:03:41,980 --> 00:03:44,890 და მაშინ, რომ ნომერი ჩვენ უბრალოდ შესანახად მონაცემები 78 00:03:44,890 --> 00:03:48,930 ჩვენ გვინდა, რომ შესანახად array იმ ადგილას. 79 00:03:48,930 --> 00:03:53,990 ასე მაგალითად, ჩვენ, ალბათ ამ hash მაგიდა სტრიქონები. 80 00:03:53,990 --> 00:03:57,350 ეს მივიღე 10 ელემენტები, ასე რომ ჩვენ შეგვიძლია ჯდება 10 სიმებისათვის ის. 81 00:03:57,350 --> 00:03:59,320 >> მოდით ვთქვათ რომ ჩვენ გვინდა, რომ hash იოანე. 82 00:03:59,320 --> 00:04:02,979 ასე რომ, იოანე მონაცემები გვინდა ჩადეთ ამ hash მაგიდა სადღაც. 83 00:04:02,979 --> 00:04:03,770 სად ჩვენ ეს? 84 00:04:03,770 --> 00:04:05,728 ისე, როგორც წესი, რომელზეც მასივი ჯერჯერობით ჩვენ, ალბათ, 85 00:04:05,728 --> 00:04:07,610 მისთვის მასივი განთავსების 0. 86 00:04:07,610 --> 00:04:09,960 მაგრამ ახლა ჩვენ ახალ hash ფუნქცია. 87 00:04:09,960 --> 00:04:13,180 >> და ვთქვათ, რომ ჩვენ აწარმოებს ჯონ ამ გზით hash ფუნქცია 88 00:04:13,180 --> 00:04:15,417 და ის ფეხზე out 4. 89 00:04:15,417 --> 00:04:17,500 ისე, რომ სადაც ჩვენ ვართ აპირებს გსურთ დააყენა იოანე. 90 00:04:17,500 --> 00:04:22,050 ჩვენ გვინდა, რომ ჯონ მასივი ადგილმდებარეობა 4, იმიტომ, რომ თუ ჩვენ hash ჯონ ერთხელ 91 00:04:22,050 --> 00:04:23,810 მოდით ვთქვათ, შემდეგ ჩვენ გსურთ მოძებნოთ და ვნახოთ 92 00:04:23,810 --> 00:04:26,960 თუ ჯონ არსებობს ამ hash მაგიდასთან ყველა ჩვენ უნდა გავაკეთოთ 93 00:04:26,960 --> 00:04:30,310 აწარმოებს მეშვეობით იგივე hash ფუნქცია, მიიღოს ნომერი 4, 94 00:04:30,310 --> 00:04:33,929 და შევძლოთ ჯონ სასწრაფოდ ჩვენს მონაცემთა სტრუქტურას. 95 00:04:33,929 --> 00:04:34,720 ეს არის საკმაოდ კარგი. 96 00:04:34,720 --> 00:04:36,928 >> ვთქვათ, ახლა ამის გაკეთება კიდევ ერთხელ, ჩვენ გვინდა, რომ hash პოლ. 97 00:04:36,928 --> 00:04:39,446 ჩვენ გვინდა, რომ დაამატოთ პოლ ამ hash მაგიდა. 98 00:04:39,446 --> 00:04:42,070 ვთქვათ, რომ ამ დროს ჩვენ აწარმოებს პავლეს ქეშირების ფუნქცია, 99 00:04:42,070 --> 00:04:44,600 hashcode, რომელიც გენერირდება 6. 100 00:04:44,600 --> 00:04:47,340 ისე, ახლა ჩვენ შეგვიძლია პავლეს მასივი ადგილმდებარეობა 6. 101 00:04:47,340 --> 00:04:50,040 და თუ ჩვენ უნდა ეძებოთ თუ არა პავლე ამ hash მაგიდა, 102 00:04:50,040 --> 00:04:53,900 ყველა ჩვენ უნდა გავაკეთოთ არის აწარმოებს პოლ მეშვეობით hash ფუნქცია ერთხელ 103 00:04:53,900 --> 00:04:55,830 და ჩვენ ვაპირებთ, რომ კიდევ 6 კიდევ ერთხელ. 104 00:04:55,830 --> 00:04:57,590 >> და მაშინ ჩვენ შევჩერდეთ განთავსებულია მასივი ადგილმდებარეობა 6. 105 00:04:57,590 --> 00:04:58,910 პავლე იქ? 106 00:04:58,910 --> 00:05:00,160 თუ ასეა, ის hash მაგიდა. 107 00:05:00,160 --> 00:05:01,875 პავლე არ არის? 108 00:05:01,875 --> 00:05:03,000 ის არ არის hash მაგიდა. 109 00:05:03,000 --> 00:05:05,720 ეს საკმაოდ მარტივია. 110 00:05:05,720 --> 00:05:07,770 >> ახლა როგორ განვსაზღვროთ ქეშირების ფუნქცია? 111 00:05:07,770 --> 00:05:11,460 ისე ნამდვილად არ ლიმიტი ნომერი შესაძლებელია hash ფუნქციები. 112 00:05:11,460 --> 00:05:14,350 რეალურად არსებობს მთელი რიგი მართლაც, კარგი პირობა ინტერნეტში. 113 00:05:14,350 --> 00:05:17,560 არსებობს მთელი რიგი მართლაც, ნამდვილად ცუდი ინტერნეტში. 114 00:05:17,560 --> 00:05:21,080 ეს არის ასევე საკმაოდ ადვილი დაწერა ცუდი. 115 00:05:21,080 --> 00:05:23,760 >> ასე რომ, რაც up კარგი hash ფუნქცია, არა? 116 00:05:23,760 --> 00:05:27,280 ისე კარგი ქეშირების ფუნქცია უნდა გამოიყენონ მხოლოდ მონაცემები hashed, 117 00:05:27,280 --> 00:05:29,420 და ყველა მონაცემები hashed. 118 00:05:29,420 --> 00:05:32,500 ასე რომ, ჩვენ არ გვინდა, რომ გამოიყენოთ anything-- ჩვენ არ ითვალისწინებდეს არაფერი 119 00:05:32,500 --> 00:05:35,560 სხვა გარდა მონაცემები. 120 00:05:35,560 --> 00:05:37,080 და ჩვენ გვინდა, გამოვიყენოთ ყველა მონაცემები. 121 00:05:37,080 --> 00:05:39,830 ჩვენ არ გვინდა, რომ უბრალოდ გამოიყენოთ ნაჭერი ეს, ჩვენ გვინდა გამოვიყენოთ ყველა ის. 122 00:05:39,830 --> 00:05:41,710 ქეშირების ფუნქცია უნდა ასევე იქნება დეტერმინისტული. 123 00:05:41,710 --> 00:05:42,550 რას ნიშნავს ეს? 124 00:05:42,550 --> 00:05:46,200 ისე, ეს იმას ნიშნავს, რომ ყოველ ჯერზე ჩვენ გაივლის ზუსტად იგივე ნაჭერი მონაცემები 125 00:05:46,200 --> 00:05:50,040 ქეშირების ფუნქცია ჩვენ ყოველთვის მიიღოს იგივე hashcode out. 126 00:05:50,040 --> 00:05:52,870 თუ მე გაივლის ჯონ შევიდა hash ფუნქცია მე გავიდნენ 4. 127 00:05:52,870 --> 00:05:56,110 მე უნდა შეეძლოს უნდა გავაკეთოთ, რომ 10,000 ჯერ და მე ყოველთვის 4. 128 00:05:56,110 --> 00:06:00,810 ასე რომ, არ შემთხვევითი ნომრები ეფექტურად შეიძლება ჩართული ჩვენი hash tables-- 129 00:06:00,810 --> 00:06:02,750 ჩვენს hash ფუნქციები. 130 00:06:02,750 --> 00:06:05,750 >> ქეშირების ფუნქცია ასევე უნდა ერთნაირად გავრცელება მონაცემები. 131 00:06:05,750 --> 00:06:09,700 თუ ყოველ ჯერზე თქვენ აწარმოებს მონაცემების საშუალებით hash ფუნქცია მიიღებთ hashcode 0, 132 00:06:09,700 --> 00:06:11,200 ეს, ალბათ, არ არის იმდენად დიდი, არა? 133 00:06:11,200 --> 00:06:14,600 თქვენ ალბათ მინდა, რომ დიდი სპექტრი hash კოდები. 134 00:06:14,600 --> 00:06:17,190 ასევე რამ შეიძლება გავრცელდეს მთელ მაგიდაზე. 135 00:06:17,190 --> 00:06:23,210 და ასევე კარგი იქნება, თუ ნამდვილად ანალოგიური მონაცემები, როგორიცაა ჯონ და ჯონათან, 136 00:06:23,210 --> 00:06:26,320 იქნებ იყო მოდებული, რომ მოხდეს სხვადასხვა ადგილას hash მაგიდა. 137 00:06:26,320 --> 00:06:28,750 ეს იქნება ლამაზი უპირატესობა. 138 00:06:28,750 --> 00:06:31,250 >> აი, მაგალითად, ქეშირების ფუნქცია. 139 00:06:31,250 --> 00:06:33,150 მე დავწერე ეს ერთი გოლი ადრე. 140 00:06:33,150 --> 00:06:35,047 ეს არ არის განსაკუთრებით კარგი ქეშირების ფუნქცია 141 00:06:35,047 --> 00:06:37,380 მიზეზით, რომ ნამდვილად არ დათვი შესვლის უფლება. 142 00:06:37,380 --> 00:06:41,040 მაგრამ თქვენ ხედავთ, რა ხდება აქ? 143 00:06:41,040 --> 00:06:44,420 როგორც ჩანს, ჩვენ ვაცხადებთ ცვლადი მოუწოდა თანხა და განსაზღვრავს ის ტოლია 0. 144 00:06:44,420 --> 00:06:50,010 და შემდეგ, როგორც ჩანს, მე ვაკეთებ რაღაც ასე რომ, სანამ strstr [j] არ არის ტოლი 145 00:06:50,010 --> 00:06:52,490 რომ წარმატებული 0. 146 00:06:52,490 --> 00:06:54,870 რას ვაკეთებ იქ? 147 00:06:54,870 --> 00:06:57,440 >> ეს არის, ძირითადად, მხოლოდ სხვა გზა განხორციელების [? Strl?] 148 00:06:57,440 --> 00:06:59,773 და გამოვლენის, როდესაც თქვენ მიაღწია ბოლოს სიმებიანი. 149 00:06:59,773 --> 00:07:02,480 ასე რომ, არ უნდა რეალურად გამოვთვალოთ სიგრძეზე სიმებიანი, 150 00:07:02,480 --> 00:07:05,640 მე უბრალოდ გამოყენებით, როდესაც მე მოხვდა წარმატებული 0 ხასიათი მე ვიცი, 151 00:07:05,640 --> 00:07:07,185 მე მიაღწია ბოლოს სიმებიანი. 152 00:07:07,185 --> 00:07:09,560 და მაშინ მე ვაპირებ შენარჩუნება iterating მეშვეობით, რომ ტექსტი, 153 00:07:09,560 --> 00:07:15,310 დასძინა strstr [j] თანხა, და შემდეგ დღის ბოლოს ვაპირებ დაბრუნებას თანხა mod 154 00:07:15,310 --> 00:07:16,200 HASH_MAX. 155 00:07:16,200 --> 00:07:18,700 >> ძირითადად ეს ყველაფერი hash ფუნქცია აკეთებს დასძინა მდე 156 00:07:18,700 --> 00:07:23,450 ყველა ASCII ღირებულებები ჩემი სიმებიანი და შემდეგ ეს 157 00:07:23,450 --> 00:07:26,390 დაბრუნების ზოგიერთი hashcode modded მიერ HASH_MAX. 158 00:07:26,390 --> 00:07:29,790 ეს, ალბათ, ზომა ჩემი მასივი, არა? 159 00:07:29,790 --> 00:07:33,160 მე არ მინდა, რომ იყოს მიღების hash კოდები, თუ ჩემი array არის ზომა 10, 160 00:07:33,160 --> 00:07:35,712 მე არ მინდა, რომ იყოს მიღების out hash კოდები 11, 12, 161 00:07:35,712 --> 00:07:38,690 13, მე ვერ დააყენა რამ შევიდა იმ ადგილას მასივი, 162 00:07:38,690 --> 00:07:39,790 რომ იქნება უკანონო. 163 00:07:39,790 --> 00:07:42,130 მე განიცდიან სეგმენტაცია ბრალი. 164 00:07:42,130 --> 00:07:45,230 >> ახლა აქ არის კიდევ ერთი სწრაფი განზე. 165 00:07:45,230 --> 00:07:48,470 საერთოდ თქვენ ალბათ არ აპირებს გსურთ დაწეროთ თქვენი საკუთარი hash ფუნქციები. 166 00:07:48,470 --> 00:07:50,997 ეს არის რეალურად ცოტა ხელოვნება, არ არის მეცნიერება. 167 00:07:50,997 --> 00:07:52,580 და იქ ბევრი რომ გადადის მათ. 168 00:07:52,580 --> 00:07:55,288 ინტერნეტ, როგორც ვთქვი, არის სრული ნამდვილად კარგი hash ფუნქციები, 169 00:07:55,288 --> 00:07:58,470 და თქვენ უნდა გამოიყენოთ ინტერნეტში მოვძებნოთ hash ფუნქციები, რადგან ეს მართლაც 170 00:07:58,470 --> 00:08:03,230 უბრალოდ სახის ზედმეტი ნარჩენები დრო შექმნათ თქვენი საკუთარი. 171 00:08:03,230 --> 00:08:05,490 >> თქვენ შეგიძლიათ დაწეროთ მარტივი პირობა ტესტირების მიზნით. 172 00:08:05,490 --> 00:08:08,323 მაგრამ როდესაც თქვენ რეალურად ვაპირებთ დაიწყოს ჰეშირება მონაცემები და შენახვის 173 00:08:08,323 --> 00:08:10,780 შევიდა hash მაგიდა თქვენ ალბათ აპირებს მინდა 174 00:08:10,780 --> 00:08:14,580 გამოიყენოს ზოგიერთი ფუნქცია, რომელიც გენერირდება თქვენ, რომ არსებობს ინტერნეტში. 175 00:08:14,580 --> 00:08:17,240 თუ თქვენ უბრალოდ დარწმუნებული უნდა იყოს მოჰყავთ თქვენი წყაროები. 176 00:08:17,240 --> 00:08:21,740 არ არსებობს მიზეზი, რომ plagiarize არაფერი აქ. 177 00:08:21,740 --> 00:08:25,370 >> კომპიუტერული მეცნიერებისა არის ნამდვილად იზრდება, და მართლაც ღირებულებები 178 00:08:25,370 --> 00:08:28,796 ღია, და ეს მართლაც მნიშვნელოვანია, მოჰყავთ თქვენი წყაროები ისე, რომ ხალხი 179 00:08:28,796 --> 00:08:30,670 შეგიძლიათ მიიღოთ მოხსენიება for მუშაობა, რომ ისინი 180 00:08:30,670 --> 00:08:32,312 აკეთებს, რომ საზოგადოების კეთილდღეობაზე. 181 00:08:32,312 --> 00:08:34,020 ასე რომ ყოველთვის იქნება sure-- და არა მხოლოდ hash 182 00:08:34,020 --> 00:08:37,270 ფუნქციები, მაგრამ ზოგადად, როდესაც თქვენ გამოყენება კოდი გარეთ წყარო, 183 00:08:37,270 --> 00:08:38,299 ყოველთვის მოჰყავთ თქვენი წყარო. 184 00:08:38,299 --> 00:08:43,500 მისცეს საკრედიტო იმ პირს, ვინც ეს გააკეთა ზოგიერთი მუშაობა, ასე რომ თქვენ არ უნდა. 185 00:08:43,500 --> 00:08:46,720 >> OK, ასე რომ მოდით დავუბრუნდეთ ამ hash მაგიდა მეორე. 186 00:08:46,720 --> 00:08:48,780 ეს არის, სადაც დავტოვეთ შემდეგ, ჩვენ ჩასმული 187 00:08:48,780 --> 00:08:53,300 იოანე და პავლე ამ hash მაგიდა. 188 00:08:53,300 --> 00:08:55,180 ხედავთ პრობლემა აქ? 189 00:08:55,180 --> 00:08:58,410 თქვენ შეიძლება ნახოთ ორი. 190 00:08:58,410 --> 00:09:02,240 მაგრამ, კერძოდ, თქვენ ვხედავ ამ შესაძლო პრობლემა? 191 00:09:02,240 --> 00:09:06,770 >> რა მოხდება, თუ hash Ringo, და ეს გამოდის, რომ დამუშავების შემდეგ 192 00:09:06,770 --> 00:09:14,000 რომ მონაცემები hash ფუნქცია Ringo ასევე გამომუშავებული hashcode 6. 193 00:09:14,000 --> 00:09:16,810 მე უკვე მივიღე მონაცემები hashcode-- მასივი ადგილმდებარეობა 6. 194 00:09:16,810 --> 00:09:22,000 ასე რომ, ეს, ალბათ, იქნება ცოტა პრობლემა ჩემთვის ახლა, არა? 195 00:09:22,000 --> 00:09:23,060 >> ჩვენ მოვუწოდებთ ამ შეჯახება. 196 00:09:23,060 --> 00:09:26,460 და შეჯახება ხდება, როდესაც ორი ცალი მონაცემები აწარმოებს მეშვეობით იგივე hash 197 00:09:26,460 --> 00:09:29,200 ფუნქცია გამოიღო იგივე hashcode. 198 00:09:29,200 --> 00:09:32,850 სავარაუდოდ, ჩვენ მაინც მინდა, რომ ორივე ცალი მონაცემები hash მაგიდა, 199 00:09:32,850 --> 00:09:36,330 წინააღმდეგ შემთხვევაში, ჩვენ არ უნდა იყოს გაშვებული Ringo თვითნებურად მეშვეობით ქეშირების ფუნქცია. 200 00:09:36,330 --> 00:09:40,870 ჩვენ, სავარაუდოდ, სურთ მიიღონ Ringo, რომ მასივი. 201 00:09:40,870 --> 00:09:46,070 >> როგორ გავაკეთოთ, რომ მიუხედავად იმისა, თუ იგი და პავლე სარგებელი hashcode 6? 202 00:09:46,070 --> 00:09:49,520 ჩვენ არ გვინდა, რომ გადავაწერო Paul, ჩვენ გვინდა, პავლე იყოს იქ. 203 00:09:49,520 --> 00:09:52,790 ასე რომ, ჩვენ უნდა მოვძებნოთ გზა ელემენტების hash მაგიდა რომელიც 204 00:09:52,790 --> 00:09:56,550 კვლავ ინარჩუნებს ჩვენი სწრაფი ჩასმა და სწრაფი up. 205 00:09:56,550 --> 00:10:01,350 და ერთი გზა გაუმკლავდეთ ის არის, რომ ამის გაკეთება რაღაც მოუწოდა ხაზოვანი probing. 206 00:10:01,350 --> 00:10:04,170 >> ამ მეთოდით, თუ ჩვენ გვაქვს შეჯახება, ასევე, რა ვქნათ? 207 00:10:04,170 --> 00:10:08,580 ისე ჩვენ ვერ დააყენა მას მასივი ადგილმდებარეობა 6, ან რასაც hashcode გამომუშავებული, 208 00:10:08,580 --> 00:10:10,820 მოდით დააყენა მას hashcode პლუს 1. 209 00:10:10,820 --> 00:10:13,670 და თუ ეს სრული მოდით მას hashcode plus 2. 210 00:10:13,670 --> 00:10:17,420 სასარგებლოდ ამ ყოფნა თუ ის არ არის ზუსტად სადაც ჩვენ ვფიქრობთ, ის არის, 211 00:10:17,420 --> 00:10:20,850 და ჩვენ უნდა დაიწყოს ეძებს, იქნებ ჩვენ არ უნდა წავიდეს შორს. 212 00:10:20,850 --> 00:10:23,900 შესაძლოა, ჩვენ არ უნდა ვეძებოთ ყველა N ელემენტების hash მაგიდა. 213 00:10:23,900 --> 00:10:25,790 შესაძლოა, ჩვენ უნდა ვეძებოთ რამდენიმე მათგანი. 214 00:10:25,790 --> 00:10:30,680 >> ასე რომ, ჩვენ ჯერ კიდევ მოვლის მიმართ საშუალო შემთხვევაში, რომ ახლოს 1 vs 215 00:10:30,680 --> 00:10:34,280 ახლოს n, იქნებ, რომ ვიმუშავებთ. 216 00:10:34,280 --> 00:10:38,010 მოდით ვნახოთ, თუ როგორ ეს შეიძლება შეიმუშაოს სინამდვილეში. 217 00:10:38,010 --> 00:10:41,460 მოდით ვნახოთ, თუ შესაძლოა, ჩვენ შეუძლია აღმოაჩინოს პრობლემა, რომელიც შეიძლება მოხდეს აქ. 218 00:10:41,460 --> 00:10:42,540 >> ვთქვათ, hash Bart. 219 00:10:42,540 --> 00:10:45,581 ასე რომ, ახლა ჩვენ ვაპირებთ აწარმოებს ახალი ნაკრები სტრიქონები მეშვეობით ქეშირების ფუნქცია, 220 00:10:45,581 --> 00:10:48,460 და ჩვენ აწარმოებს Bart მეშვეობით hash ფუნქცია, მივიღებთ hashcode 6. 221 00:10:48,460 --> 00:10:52,100 ჩვენ შევხედოთ, ჩვენ ვხედავთ, 6 ცარიელი, ასე რომ ჩვენ შეგვიძლია Bart არსებობს. 222 00:10:52,100 --> 00:10:55,410 >> ახლა ჩვენ hash ლიზა და რომ ასევე ქმნის hashcode 6. 223 00:10:55,410 --> 00:10:58,330 ისე, ახლა რომ ჩვენ გამოყენებისას ხაზოვანი საცდელი მეთოდით იწყება 6, 224 00:10:58,330 --> 00:10:59,330 ჩვენ ვხედავთ, რომ 6 სავსეა. 225 00:10:59,330 --> 00:11:00,990 ჩვენ ვერ დააყენა ლიზა 6. 226 00:11:00,990 --> 00:11:02,090 ასე რომ, სად წავიდეთ? 227 00:11:02,090 --> 00:11:03,280 წამო 7. 228 00:11:03,280 --> 00:11:04,610 7 ცარიელი, ასე რომ, რომელიც მუშაობს. 229 00:11:04,610 --> 00:11:06,510 მოდით დააყენა Lisa არსებობს. 230 00:11:06,510 --> 00:11:10,200 >> ახლა ჩვენ hash Homer და მივიღებთ 7. 231 00:11:10,200 --> 00:11:13,380 OK კარგად ვიცით, რომ 7 სრული ახლა, ასე რომ ჩვენ ვერ დააყენა Homer არსებობს. 232 00:11:13,380 --> 00:11:14,850 მოდით წავიდეთ 8. 233 00:11:14,850 --> 00:11:15,664 8 ხელმისაწვდომი? 234 00:11:15,664 --> 00:11:18,330 ჰო, და 8 ახლო 7, ასე რომ, თუ ჩვენ უნდა დაიწყოს ეძებს ჩვენ 235 00:11:18,330 --> 00:11:20,020 არ ვაპირებ წავიდეთ შორს. 236 00:11:20,020 --> 00:11:22,860 ასე რომ, მოდით ვთქვათ Homer დილის 8. 237 00:11:22,860 --> 00:11:25,151 >> ახლა ჩვენ hash მეგი და ბრუნდება 3, მადლობა ღმერთს 238 00:11:25,151 --> 00:11:26,650 ჩვენ შეუძლია მხოლოდ დააყენა მეგი არსებობს. 239 00:11:26,650 --> 00:11:29,070 ჩვენ არ გვაქვს რაიმე ერთგვარი საცდელი რომ. 240 00:11:29,070 --> 00:11:32,000 ახლა ჩვენ hash მარჯი, და მარჯი ასევე დააბრუნებს 6. 241 00:11:32,000 --> 00:11:39,560 >> ისე 6 სრული, 7 სავსეა, 8 სავსეა, 9, ყველა უფლება მადლობა ღმერთს, 9 ცარიელია. 242 00:11:39,560 --> 00:11:41,600 შემიძლია დააყენა მარჯი at 9. 243 00:11:41,600 --> 00:11:45,280 უკვე ჩვენ ვხედავთ, რომ ჩვენ ვიწყებთ ეს პრობლემა, სადაც ახლა ჩვენ 244 00:11:45,280 --> 00:11:48,780 დაწყებული მონაკვეთის რამ სახის of შორს მათი hash კოდები. 245 00:11:48,780 --> 00:11:52,960 და რომ თეტა 1, საშუალო შემთხვევაში, მუდმივი, 246 00:11:52,960 --> 00:11:56,560 იწყება მისაღებად ცოტა more-- დაწყებული, როგორც წესი, ცოტა მეტი 247 00:11:56,560 --> 00:11:58,050 მიმართ თეტა ო. 248 00:11:58,050 --> 00:12:01,270 ჩვენ ვიწყებთ კარგავენ, რომ უპირატესობა hash მაგიდები. 249 00:12:01,270 --> 00:12:03,902 >> ეს პრობლემა, რომელიც ჩვენ ვნახეთ არის რაღაც მოუწოდა კლასტერიზაცია. 250 00:12:03,902 --> 00:12:06,360 და რა არის ნამდვილად ცუდი კლასტერული არის, რომ ერთხელ თქვენ ახლა 251 00:12:06,360 --> 00:12:09,606 აქვს ორი ელემენტები, რომლებიც გვერდით მხარეს ეს ხდის კიდევ უფრო სავარაუდოა, 252 00:12:09,606 --> 00:12:11,480 თქვენ გაქვთ ორმაგი შანსი, რომ თქვენ აპირებს 253 00:12:11,480 --> 00:12:13,516 კიდევ ერთი შეჯახება რომ კასეტური 254 00:12:13,516 --> 00:12:14,890 და კასეტური გაიზრდება ერთი. 255 00:12:14,890 --> 00:12:19,640 და თქვენ შენარჩუნება იზრდება და იზრდება თქვენი ალბათობა შეჯახება. 256 00:12:19,640 --> 00:12:24,470 და საბოლოოდ, ეს როგორც ცუდი არ დახარისხება მონაცემები ყველა. 257 00:12:24,470 --> 00:12:27,590 >> მეორე პრობლემა, მიუხედავად იმისა, რომ ჩვენ მაინც, და ჯერჯერობით ამ ეტაპზე, 258 00:12:27,590 --> 00:12:30,336 ვიყავით სახის გაგება, თუ რა hash მაგიდა, 259 00:12:30,336 --> 00:12:31,960 ჩვენ ჯერ კიდევ მხოლოდ ოთახი 10 სიმები. 260 00:12:31,960 --> 00:12:37,030 თუ ჩვენ გვინდა გავაგრძელოთ hash მოქალაქეებს Springfield, 261 00:12:37,030 --> 00:12:38,790 ჩვენ შეიძლება მხოლოდ 10 მათგანი იქ. 262 00:12:38,790 --> 00:12:42,619 და თუ ჩვენ ვცდილობთ და დაამატოთ მე -11 და მე -12, ჩვენ არ აქვს ადგილი იმისათვის, რომ მათ. 263 00:12:42,619 --> 00:12:45,660 ჩვენ შეიძლება მხოლოდ spinning გარშემო წრეების ცდილობს იპოვოს ცარიელი ადგილზე, 264 00:12:45,660 --> 00:12:49,000 და ჩვენ, შესაძლოა, დავრჩებოდით უსასრულო ციკლი. 265 00:12:49,000 --> 00:12:51,810 >> ასე რომ, ეს ერთგვარი lends იმ აზრს, რაღაც მოუწოდა მიჯაჭვის. 266 00:12:51,810 --> 00:12:55,790 და ეს არის, სადაც ჩვენ ვაპირებთ, რათა დაკავშირებული სიები ისევ სურათს. 267 00:12:55,790 --> 00:13:01,300 რა მოხდება, თუ ნაცვლად შენახვის მხოლოდ მონაცემები თავად მასივი, 268 00:13:01,300 --> 00:13:04,471 ყოველ ელემენტს მასივი იქნებოდა გამართავს მრავალჯერადი ცალი მონაცემები? 269 00:13:04,471 --> 00:13:05,970 ისე, რომ აზრი არ აქვს, არა? 270 00:13:05,970 --> 00:13:09,280 ჩვენ ვიცით, რომ მასივი მხოლოდ hold-- თითოეული ელემენტის მასივი 271 00:13:09,280 --> 00:13:12,930 შეიძლება მხოლოდ ერთი ცალი მონაცემების რომ მონაცემები ტიპის. 272 00:13:12,930 --> 00:13:16,750 >> მაგრამ რა, თუ რომ მონაცემები ტიპის არის დაკავშირებული სიაში, უფლება? 273 00:13:16,750 --> 00:13:19,830 მერე რა, რომ ყოველ ელემენტს მასივი იყო 274 00:13:19,830 --> 00:13:22,790 მომცეთ ხელმძღვანელი უკავშირდება სიაში? 275 00:13:22,790 --> 00:13:24,680 და მაშინ ჩვენ შეგვიძლია ავაშენოთ იმ დაკავშირებული სიები 276 00:13:24,680 --> 00:13:27,120 და იზრდება მათ თვითნებურად, იმიტომ, რომ უკავშირდება სიები საშუალებას 277 00:13:27,120 --> 00:13:32,090 ჩვენთვის იზრდება და მცირდება ბევრი სხვა მოქნილად ვიდრე მასივი აკეთებს. 278 00:13:32,090 --> 00:13:34,210 ასე რომ, თუ ჩვენ ახლა გამოყენება, ჩვენ ბერკეტები ამ, არა? 279 00:13:34,210 --> 00:13:37,760 ვიწყებთ იზრდება ამ ჯაჭვების აქედან მასივი ადგილას. 280 00:13:37,760 --> 00:13:40,740 >> ახლა ჩვენ შეგვიძლია შეესაბამება უსასრულო თანხის მონაცემები, ან არ არის უსასრულო, 281 00:13:40,740 --> 00:13:44,170 თვითნებური თანხა მონაცემები, ჩვენი hash მაგიდა 282 00:13:44,170 --> 00:13:47,760 გარეშე ოდესმე გაშვებული შევიდა პრობლემა შეჯახება. 283 00:13:47,760 --> 00:13:50,740 ჩვენ ასევე აღმოფხვრილი კლასტერული ამით. 284 00:13:50,740 --> 00:13:54,380 და კარგად ვიცით, რომ როდესაც ჩვენ ჩადეთ შევიდა უკავშირდება სიაში, თუ გავიხსენებთ 285 00:13:54,380 --> 00:13:57,779 ჩვენი ვიდეო უკავშირდება სიები, ცალკე დაკავშირებული სიები და ორმაგად უკავშირდება სიები, 286 00:13:57,779 --> 00:13:59,070 ეს არის მუდმივი დრო ოპერაცია. 287 00:13:59,070 --> 00:14:00,710 ჩვენ ვამატებთ ფრონტზე. 288 00:14:00,710 --> 00:14:04,400 >> და თვალი, კარგად ვიცით, რომ ეძებოთ უკავშირდება სიაში 289 00:14:04,400 --> 00:14:05,785 შეიძლება იყოს პრობლემა, არა? 290 00:14:05,785 --> 00:14:07,910 ჩვენ უნდა მოძებნოთ მეშვეობით ეს თავიდან ბოლომდე. 291 00:14:07,910 --> 00:14:10,460 არ არის შემთხვევითი ხელმისაწვდომობა უკავშირდება სიაში. 292 00:14:10,460 --> 00:14:15,610 მაგრამ თუ ნაცვლად, რომ ერთი უკავშირდება სიაში, სადაც საძიებელი იქნება ო ო, 293 00:14:15,610 --> 00:14:19,590 ახლა ჩვენ გვაქვს 10 უკავშირდება სიები, ან 1000 უკავშირდება სიები, 294 00:14:19,590 --> 00:14:24,120 ახლა ეს ო ო იყოფა 10, ან O ო იყოფა 1,000. 295 00:14:24,120 --> 00:14:26,940 >> და მაშინ, როცა ჩვენ ვსაუბრობთ თეორიულად შესახებ სირთულის 296 00:14:26,940 --> 00:14:30,061 ჩვენ იგნორირება მუდმივები, რეალურ მსოფლიოს ეს ყველაფერი რეალურად აქვს, 297 00:14:30,061 --> 00:14:30,560 არა? 298 00:14:30,560 --> 00:14:33,080 ჩვენ, ფაქტობრივად, შეამჩნევთ რომ ეს მოხდება 299 00:14:33,080 --> 00:14:36,610 აწარმოებს 10 ჯერ უფრო სწრაფად, ან 1,000 ჯერ უფრო სწრაფად, 300 00:14:36,610 --> 00:14:41,570 იმიტომ, რომ ჩვენ დარიგება ერთი ხანგრძლივი ჯაჭვის მასშტაბით 1,000 მცირე ქსელები. 301 00:14:41,570 --> 00:14:45,090 ასე რომ, ყოველ ჯერზე ჩვენ უნდა ვეძებოთ ერთ-ერთ იმ ჯაჭვების ჩვენ შეგვიძლია 302 00:14:45,090 --> 00:14:50,290 იგნორირება 999 ჯაჭვების ჩვენ არ აინტერესებს შესახებ, და უბრალოდ ძებნის, რომ ერთი. 303 00:14:50,290 --> 00:14:53,220 >> რომელი საშუალოდ 1,000 ჯერ უფრო მოკლეა. 304 00:14:53,220 --> 00:14:56,460 ასე რომ, ჩვენ ჯერ კიდევ არის ერთგვარი მოვლის მიმართ ეს საშუალო შემთხვევაში 305 00:14:56,460 --> 00:15:01,610 მიმდინარეობს მუდმივი, მაგრამ მხოლოდ იმიტომ, რომ ჩვენ ოპერაციული 306 00:15:01,610 --> 00:15:03,730 გამყოფი ზოგიერთი დიდი მუდმივი ფაქტორი. 307 00:15:03,730 --> 00:15:05,804 ვნახოთ, როგორ ეს შეიძლება რეალურად გამოიყურება თუმცა. 308 00:15:05,804 --> 00:15:08,720 ასე რომ, ეს იყო hash მაგიდა გვქონდა სანამ ჩვენ განაცხადა hash მაგიდა რომელიც 309 00:15:08,720 --> 00:15:10,270 იყო შეუძლია შენახვა 10 სიმები. 310 00:15:10,270 --> 00:15:11,728 ჩვენ არ ვაპირებთ გავაკეთოთ, რომ მთელი მსოფლიოს მასშტაბით. 311 00:15:11,728 --> 00:15:13,880 ჩვენ უკვე ვიცით, შეზღუდვები, რომელიც საშუალებას. 312 00:15:13,880 --> 00:15:20,170 ახლა ჩვენი hash მაგიდა იქნება მასივი 10 კვანძების, მითითებას 313 00:15:20,170 --> 00:15:22,120 ხელმძღვანელებს დაკავშირებული სიები. 314 00:15:22,120 --> 00:15:23,830 >> და ახლა ეს null. 315 00:15:23,830 --> 00:15:26,170 თითოეული ერთი იმ 10 მითითებას null. 316 00:15:26,170 --> 00:15:29,870 არაფერია ჩვენს hash მაგიდა ახლავე. 317 00:15:29,870 --> 00:15:32,690 >> ახლა დავიწყოთ დააყენოს გარკვეული რამ ამ hash მაგიდა. 318 00:15:32,690 --> 00:15:35,440 და ვნახოთ, თუ როგორ ეს მეთოდი აპირებს ისარგებლოს ჩვენთვის ცოტა. 319 00:15:35,440 --> 00:15:36,760 მოდით ახლა hash Joey. 320 00:15:36,760 --> 00:15:40,210 ჩვენ აწარმოებს სიმებიანი Joey მეშვეობით ქეშირების ფუნქცია და ჩვენ დაუბრუნოს 6. 321 00:15:40,210 --> 00:15:41,200 ისე, რა ვქნათ? 322 00:15:41,200 --> 00:15:44,090 >> ისე ახლა მუშაობს დაკავშირებული სიები, ჩვენ არ მუშაობს მასივები. 323 00:15:44,090 --> 00:15:45,881 და როდესაც ჩვენ ვმუშაობთ უკავშირდება სიები ჩვენ 324 00:15:45,881 --> 00:15:49,790 იცით, ჩვენ უნდა დავიწყოთ დინამიურად გამოყოფის სივრცე და სამშენებლო ქსელები. 325 00:15:49,790 --> 00:15:54,020 სწორედ ერთგვარი how-- იმ ძირითადი ელემენტები მშენებლობის უკავშირდება სიაში. 326 00:15:54,020 --> 00:15:57,670 მოდით დინამიურად გამოყოს ფართი Joey, 327 00:15:57,670 --> 00:16:00,390 და მაშინ მოდით დაამატოთ მას ჯაჭვი. 328 00:16:00,390 --> 00:16:03,170 >> ასე რომ, ახლა გამოიყურება, რაც ჩვენ გავაკეთეთ. 329 00:16:03,170 --> 00:16:06,440 როდესაც ჩვენ hash Joey მივიღეთ hashcode 6. 330 00:16:06,440 --> 00:16:11,790 ახლა მაჩვენებელი მასივი ადგილმდებარეობა 6 მიუთითებს, რომ ხელმძღვანელი უკავშირდება სია, 331 00:16:11,790 --> 00:16:14,900 და ახლა ეს მხოლოდ ელემენტს უკავშირდება სიაში. 332 00:16:14,900 --> 00:16:18,350 და კვანძის, რომ უკავშირდება სია Joey. 333 00:16:18,350 --> 00:16:22,300 >> ასე რომ, თუ ჩვენ უნდა ეძებოთ Joey შემდეგ, ჩვენ უბრალოდ hash Joey ერთხელ, 334 00:16:22,300 --> 00:16:26,300 ჩვენ კიდევ ისევ 6 იმიტომ, რომ ჩვენი ქეშირების ფუნქცია არის deterministic. 335 00:16:26,300 --> 00:16:30,400 და მერე ჩვენ დავიწყოთ ხელმძღვანელი უკავშირდება სიაში აღნიშნა 336 00:16:30,400 --> 00:16:33,360 მიერ მასივი ადგილმდებარეობა 6, და ჩვენ შეგვიძლია iterate 337 00:16:33,360 --> 00:16:35,650 მასშტაბით, რომ ცდილობს იპოვოს Joey. 338 00:16:35,650 --> 00:16:37,780 და თუ ჩვენ ჩვენს hash მაგიდა ეფექტურად, 339 00:16:37,780 --> 00:16:41,790 და ჩვენი ქეშირების ფუნქცია ეფექტურად გავრცელება მონაცემები კარგად, 340 00:16:41,790 --> 00:16:45,770 საშუალოდ თითოეულ იმ დაკავშირებული სიების ყოველ მასივი ადგილმდებარეობა 341 00:16:45,770 --> 00:16:50,110 იქნება 1/10 ზომა, თუ ჩვენ უბრალოდ ჰქონდა, როგორც ერთი დიდი 342 00:16:50,110 --> 00:16:51,650 უკავშირდება სიაში ყველაფერი ეს. 343 00:16:51,650 --> 00:16:55,670 >> თუ ჩვენ გავრცელება, რომ დიდი უკავშირდება სია მასშტაბით 10 დაკავშირებული სიები 344 00:16:55,670 --> 00:16:57,760 თითოეულ სია იქნება 1/10 ზომა. 345 00:16:57,760 --> 00:17:01,432 და, შესაბამისად, 10-ჯერ უფრო სწრაფად ძებნის საშუალებით. 346 00:17:01,432 --> 00:17:02,390 ასე რომ, მოდით ეს კიდევ ერთხელ გავაკეთოთ. 347 00:17:02,390 --> 00:17:04,290 მოდით ახლა hash როსი. 348 00:17:04,290 --> 00:17:07,540 >> და მოდით ვთქვათ, Ross, როდესაც ჩვენ გავაკეთებთ, რომ hash კოდი მივიღებთ უკან 2. 349 00:17:07,540 --> 00:17:10,630 ისე, ახლა ჩვენ დინამიურად გამოყოფს ახალი კვანძის, ჩვენ როს, რომ კვანძის, 350 00:17:10,630 --> 00:17:14,900 და ვამბობთ ახლა მასივი ადგილმდებარეობა 2, ნაცვლად მიუთითებს null, 351 00:17:14,900 --> 00:17:18,579 მიუთითებს, რომ ხელმძღვანელი უკავშირდება სია, რომელთა ერთადერთი კვანძის როსი. 352 00:17:18,579 --> 00:17:22,660 და ჩვენ შეგვიძლია ამის გაკეთება კიდევ ერთხელ, ჩვენ შეგიძლიათ hash Rachel და მიიღეთ hashcode 4. 353 00:17:22,660 --> 00:17:25,490 malloc ახალი კვანძის, დააყენა რეიჩელ კვანძის, და აცხადებენ, რომ მასივი ადგილმდებარეობა 354 00:17:25,490 --> 00:17:27,839 4 ახლა მიუთითებს უფროსი უკავშირდება სია, რომელთა 355 00:17:27,839 --> 00:17:31,420 მხოლოდ ელემენტი ხდება, რომ რეიჩელ. 356 00:17:31,420 --> 00:17:33,470 >> OK, მაგრამ რა მოხდება, თუ ჩვენ შეჯახება? 357 00:17:33,470 --> 00:17:38,560 ვნახოთ, როგორ გაუმკლავდეს collisions გამოყენებით ცალკე chaining მეთოდი. 358 00:17:38,560 --> 00:17:39,800 მოდით hash Phoebe. 359 00:17:39,800 --> 00:17:41,094 მივიღებთ hashcode 6. 360 00:17:41,094 --> 00:17:44,010 ჩვენი წინა მაგალითად ჩვენ მხოლოდ შენახვის სიმები მასივი. 361 00:17:44,010 --> 00:17:45,980 ეს იყო პრობლემა. 362 00:17:45,980 --> 00:17:48,444 >> ჩვენ არ გვინდა, რომ clobber Joey, და ჩვენ უკვე 363 00:17:48,444 --> 00:17:51,110 ჩანს, რომ ჩვენ შეიძლება რაღაც კლასტერული პრობლემა თუ ჩვენ ვცდილობთ და ნაბიჯი 364 00:17:51,110 --> 00:17:52,202 მეშვეობით და გამოძიება. 365 00:17:52,202 --> 00:17:54,660 მაგრამ თუ ჩვენ მხოლოდ სახის მკურნალობა იგივე გზით, არა? 366 00:17:54,660 --> 00:17:57,440 ეს, ისევე, დასძინა ელემენტს ხელმძღვანელი უკავშირდება სიაში. 367 00:17:57,440 --> 00:18:00,220 მოდით უბრალოდ malloc ფართი Phoebe. 368 00:18:00,220 --> 00:18:04,764 >> ჩვენ ვიტყვით, Phoebe მომდევნო მაჩვენებელი რაოდენობა ძველი ხელმძღვანელი უკავშირდება სია, 369 00:18:04,764 --> 00:18:07,180 და შემდეგ 6 მხოლოდ მიუთითებს ახალი ხელმძღვანელი უკავშირდება სიაში. 370 00:18:07,180 --> 00:18:10,150 ახლა კი გამოიყურება, ჩვენ შეიცვალა Phoebe in. 371 00:18:10,150 --> 00:18:14,210 ახლა ჩვენ შეგვიძლია შესანახად ორი ელემენტების hashcode 6, 372 00:18:14,210 --> 00:18:17,170 და ჩვენ არ გვაქვს არანაირი პრობლემა. 373 00:18:17,170 --> 00:18:20,147 >> ეს არის საკმაოდ ბევრი ყველა არ არის chaining. 374 00:18:20,147 --> 00:18:21,980 და chaining ნამდვილად მეთოდი, რომელიც არის 375 00:18:21,980 --> 00:18:27,390 იქნება ყველაზე ეფექტური, თუ თქვენ შენახვის მონაცემების hash მაგიდა. 376 00:18:27,390 --> 00:18:30,890 მაგრამ ეს კომბინაცია კოლექტორები და დაკავშირებული სიები 377 00:18:30,890 --> 00:18:36,080 ერთად შექმნან hash მაგიდა ნამდვილად მკვეთრად აუმჯობესებს თქვენი უნარი 378 00:18:36,080 --> 00:18:40,550 შესანახად დიდი რაოდენობით მონაცემები და ძალიან სწრაფად და ეფექტურად ძიება 379 00:18:40,550 --> 00:18:41,630 მეშვეობით, რომ მონაცემები. 380 00:18:41,630 --> 00:18:44,150 >> არსებობს კიდევ ერთი მონაცემები სტრუქტურა არსებობს 381 00:18:44,150 --> 00:18:48,700 რომ შეიძლება იყოს ცოტა უკეთესი კუთხით გარანტიას 382 00:18:48,700 --> 00:18:51,920 რომ ჩვენი ჩასმა, წაშლა, და ეძებოთ ჯერ უფრო სწრაფად. 383 00:18:51,920 --> 00:18:55,630 ჩვენ დავინახავთ, რომ ვიდეო ლელო. 384 00:18:55,630 --> 00:18:58,930 მე Doug Lloyd, ეს არის CS50. 385 00:18:58,930 --> 00:19:00,214