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 >> داگ لوید: در حال حاضر شما می دانم که بسیاری در مورد آرایه ها، 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 و آن نوع از می آورد به این ایده از یک جدول هش. 17 00:00:40,950 --> 00:00:46,680 >> بنابراین در یک جدول هش ما قصد داریم به تلاش ترکیب یک آرایه با یک لیست پیوندی. 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 بدون نیاز به تکرار در سراسر. 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 و ما می توانیم این پاسخ چیز جدید یک جدول هش. 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 درج می توانید شروع به تمایل به سمت تتا، از مجموع 1 31 00:01:23,070 --> 00:01:26,207 تتا ما واقعا مورد بحث نیست، اما تتا فقط در مورد به طور متوسط، 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 >> خب یک درج متوسط به یک جدول هش 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 ایده که در آن دقیقا ما رفتن به پیدا کردن آن را در جدول هش. 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 ساعت هم نزدیک تر می شود به تتا از n، و ما اساسا 58 00:02:44,060 --> 00:02:45,530 پسرفت به یک لیست پیوندی. 59 00:02:45,530 --> 00:02:48,850 و بنابراین ما فقط مایل به استفاده هش جداول اگر ما در مورد مراقبت از 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 >> بنابراین یک جدول هش ترکیبی است دو قطعه مجزا 64 00:03:03,170 --> 00:03:04,980 که ما با آن آشنا هستید. 65 00:03:04,980 --> 00:03:07,930 برای اولین بار یک تابع است که ما معمولا یک تابع هش پاسخ. 66 00:03:07,930 --> 00:03:11,760 و تابع هش است برای رفتن به بازگشت برخی از عدد صحیح غیر منفی، که 67 00:03:11,760 --> 00:03:14,870 ما معمولا یک hashcode پاسخ، خوب است؟ 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 ما بر روی دست نگه دارند مرتبط لیست عنصر برای 71 00:03:24,310 --> 00:03:27,810 و فقط با اصول اولیه یک شروع جدول هش برای دریافت سر خود را در اطراف آن، 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 و به این ترتیب داده های پردازش شده است و تف کردن یک عدد، OK؟ 77 00:03:41,980 --> 00:03:44,890 و سپس با شماره ما فقط ذخیره داده ها 78 00:03:44,890 --> 00:03:48,930 ما می خواهیم برای ذخیره در آرایه در آن محل. 79 00:03:48,930 --> 00:03:53,990 بنابراین برای مثال ما شاید این جدول هش از رشته ها. 80 00:03:53,990 --> 00:03:57,350 آن را به 10 عنصر در آن، پس ما می توانیم 10 رشته در آن جا داد. 81 00:03:57,350 --> 00:03:59,320 >> بیایید می گویند ما می خواهیم به هش جان. 82 00:03:59,320 --> 00:04:02,979 بنابراین جان به عنوان داده های ما خواهید برای وارد کردن به این جدول هش جایی. 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 اما در حال حاضر ما باید این تابع هش جدید. 87 00:04:09,960 --> 00:04:13,180 >> و اجازه دهید بگویم که ما اجرا جان از طریق این تابع هش 88 00:04:13,180 --> 00:04:15,417 و آن را تف 4. 89 00:04:15,417 --> 00:04:17,500 خوب است که در آن ما به رفتن به خواهید برای قرار دادن جان. 90 00:04:17,500 --> 00:04:22,050 ما می خواهیم به قرار دادن جان در محل آرایه 4، چرا که اگر ما هش جان again-- 91 00:04:22,050 --> 00:04:23,810 اجازه دهید بعد می گویند ما می خواهید برای جستجو و ببینید 92 00:04:23,810 --> 00:04:26,960 اگر جان در این هش وجود دارد table-- همه ما باید انجام دهیم 93 00:04:26,960 --> 00:04:30,310 است آن را از طریق هش همان اجرا تابع، بدست آوردن شماره 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 >> بیایید می گویند ما در حال حاضر انجام این کار دوباره، ما می خواهیم به هش پل. 97 00:04:36,928 --> 00:04:39,446 ما می خواهیم به اضافه پل به این جدول هش. 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 و اگر ما نیاز به نگاه کردن آیا پل در این جدول هش، 102 00:04:50,040 --> 00:04:53,900 همه ما باید انجام دهیم این است که اجرای پل از طریق تابع هش دوباره 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 اگر چنین است، او در جدول هش است. 107 00:05:00,160 --> 00:05:01,875 است پل وجود ندارد؟ 108 00:05:01,875 --> 00:05:03,000 او در جدول هش است. 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 خب واقعا هیچ محدودیتی برای وجود دارد تعدادی از توابع هش امکان پذیر است. 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 >> بنابراین چه چیزی باعث شده تا خوب تابع هش، درست است؟ 116 00:05:23,760 --> 00:05:27,280 خب یک تابع هش خوب باید استفاده از تنها داده های در حال درهم، 117 00:05:27,280 --> 00:05:29,420 و همه داده های در حال درهم. 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 همان است. 126 00:05:50,040 --> 00:05:52,870 اگر من عبور جان به تابع هش من خارج 4. 127 00:05:52,870 --> 00:05:56,110 من باید قادر به انجام این کار می تواند 10،000 زمان و من همیشه می خواهید 4. 128 00:05:56,110 --> 00:06:00,810 بنابراین هیچ اعداد تصادفی به طور موثر را می توان در هش ما نقش دارند tables-- 129 00:06:00,810 --> 00:06:02,750 در توابع هش ما است. 130 00:06:02,750 --> 00:06:05,750 >> یک تابع هش نیز باید یکنواخت توزیع داده ها. 131 00:06:05,750 --> 00:06:09,700 اگر هر بار که اطلاعات شما اجرا از طریق تابع هش شما در hashcode 0 را دریافت کنید، 132 00:06:09,700 --> 00:06:11,200 که احتمالا نه چندان بزرگ، درست است؟ 133 00:06:11,200 --> 00:06:14,600 شما احتمالا به بزرگ می خواهند طیف وسیعی از کد هش. 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 شاید بیرون پخش شد به وزن مکان های مختلف در جدول هش. 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 و سپس من رفتن به نگه داشتن تکرار از طریق این رشته، 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 >> در واقع تمام این هش تابع انجام شده است اضافه کردن 156 00:07:18,700 --> 00:07:23,450 تمام ارزش ASCII از رشته من، و سپس آن را 157 00:07:23,450 --> 00:07:26,390 بازگشت برخی hashcode کامپیوتر های HASH_MAX. 158 00:07:26,390 --> 00:07:29,790 این احتمالا به اندازه آرایه من، درست است؟ 159 00:07:29,790 --> 00:07:33,160 من نمی خواهم به گرفتن هش کد اگر آرایه من است اندازه 10، 160 00:07:33,160 --> 00:07:35,712 من نمی خواهم به گرفتن کد رشته هش از 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 به طور کلی شما احتمالا به رفتن نیست می خواهم برای نوشتن توابع هش خود را. 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 اینترنت، مثل من گفت، کامل است از توابع هش واقعا خوب است، 169 00:07:55,288 --> 00:07:58,470 و شما باید به اینترنت برای استفاده پیدا توابع هش دلیل آن را واقعا 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 به یک جدول هش شما احتمالا می خواهید 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 هیچ دلیلی برای وجود دارد خوشه چینی کردن هر چیزی در اینجا. 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 می توانید برای دریافت اسناد کار است که آنها 180 00:08:30,670 --> 00:08:32,312 انجام به نفع جامعه است. 181 00:08:32,312 --> 00:08:34,020 بنابراین همیشه sure-- شود و نه فقط برای هش 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 بنابراین اجازه دهید این دوباره جدول هش برای یک ثانیه. 186 00:08:46,720 --> 00:08:48,780 این جایی است که ما به سمت چپ بعد از ما قرار داده 187 00:08:48,780 --> 00:08:53,300 جان و پل به این جدول هش. 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 >> اگر من هش رینگو، و آن معلوم است که پس از پردازش 192 00:09:06,770 --> 00:09:14,000 که داده ها از طریق تابع هش رینگو همچنین تولید 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 و برخورد رخ می دهد که دو قطعه از داده ها از طریق هش همان اجرا 197 00:09:26,460 --> 00:09:29,200 عملکرد تابع hashcode است. 198 00:09:29,200 --> 00:09:32,850 احتمالا ما هنوز هم می خواهید به دریافت هر دو قطعه از داده ها را به جدول هش، 199 00:09:32,850 --> 00:09:36,330 در غیر این صورت ما نمی شود در حال اجرا رینگو خودسرانه از طریق تابع هش. 200 00:09:36,330 --> 00:09:40,870 ما احتمالا می خواهید برای دریافت رینگو به که آرایه. 201 00:09:40,870 --> 00:09:46,070 >> چگونه ما آن را انجام هر چند، اگر او و پل هر دو عملکرد hashcode 6؟ 202 00:09:46,070 --> 00:09:49,520 ما نمی خواهیم به بازنویسی پل، ما می خواهیم به پل وجود دارد بیش از حد. 203 00:09:49,520 --> 00:09:52,790 بنابراین ما نیاز به پیدا کردن یک راه برای به دست آوردن عناصر به جدول هش که 204 00:09:52,790 --> 00:09:56,550 هنوز هم سریع ما را حفظ درج و سریع نگاه کردن. 205 00:09:56,550 --> 00:10:01,350 و یک راه برای مقابله با آن است به انجام چیزی به نام کاوش خطی. 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 به علاوه 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 از جدول هش. 213 00:10:23,900 --> 00:10:25,790 شاید ما باید به جستجو یک زن و شوهر از آنها. 214 00:10:25,790 --> 00:10:30,680 >> و بنابراین ما هنوز هم نسبت به رسیدگی که به طور متوسط ​​مورد نزدیک شدن به 1 مقابل 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 >> بیایید می گویند ما هش بارت. 219 00:10:42,540 --> 00:10:45,581 بنابراین در حال حاضر ما در حال رفتن به اجرای یک مجموعه جدید از رشته از طریق تابع هش، 220 00:10:45,581 --> 00:10:48,460 و ما بارت از طریق هش اجرا تابع، ما hashcode 6. 221 00:10:48,460 --> 00:10:52,100 ما را نگاه کنیم، می بینیم 6 خالی، بنابراین ما می توانیم بارت وجود دارد قرار داده است. 222 00:10:52,100 --> 00:10:55,410 >> در حال حاضر ما هش لیزا و همچنین تولید 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 بنابراین اجازه دهید لیزا وجود دارد. 230 00:11:06,510 --> 00:11:10,200 >> در حال حاضر ما هش هومر و ما 7. 231 00:11:10,200 --> 00:11:13,380 OK خوبی می دانیم که 7 کامل در حال حاضر، بنابراین ما می توانیم هومر قرار داده نشده است. 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 آره، و نزدیک به 7 8 است، بنابراین اگر ما شروع به جستجو ما 235 00:11:18,330 --> 00:11:20,020 قصد ندارم به به بیش از حد. 236 00:11:20,020 --> 00:11:22,860 و بنابراین اجازه دهید هومر را در 8. 237 00:11:22,860 --> 00:11:25,151 >> در حال حاضر ما هش مگی و را برمی گرداند 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 در حال حاضر ما هش حاشیه، و حاشیه نیز باز می گردد 6. 241 00:11:32,000 --> 00:11:39,560 >> خوب 6 پر است، پر است 7، 8 پر است، 9، همه حق خدا را شکر، 9 خالی است. 242 00:11:39,560 --> 00:11:41,600 من می توانم حاشیه در 9 قرار داده است. 243 00:11:41,600 --> 00:11:45,280 در حال حاضر ما می توانید ببینید که ما در حال شروع به این مشکل که در آن در حال حاضر ما 244 00:11:45,280 --> 00:11:48,780 شروع به کشش همه چیز نوع از دور از کد هش است. 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 به سمت تتا از n. 248 00:11:58,050 --> 00:12:01,270 ما در حال شروع به از دست دادن که استفاده از جداول هش. 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 ما فقط از شده درک آنچه یک جدول هش، 259 00:12:30,336 --> 00:12:31,960 ما هنوز هم تنها 10 اتاق برای رشته داشته باشد. 260 00:12:31,960 --> 00:12:37,030 اگر ما می خواهیم به به هش شهروندان اسپرینگفیلد، 261 00:12:37,030 --> 00:12:38,790 ما فقط می توانیم 10 نفر از آنها را در وجود دارد. 262 00:12:38,790 --> 00:12:42,619 و اگر ما را امتحان کنید و یا اضافه کردن یک 11TH تاریخ 12th، ما یک محل برای قرار دادن آنها ندارد. 263 00:12:42,619 --> 00:12:45,660 ما فقط می تواند در حال چرخش به دور محافل تلاش برای پیدا کردن یک نقطه خالی، 264 00:12:45,660 --> 00:12:49,000 و ما شاید گیر در یک حلقه بی نهایت. 265 00:12:49,000 --> 00:12:51,810 >> بنابراین این نوع از آشنایی به این ایده از چیزی به نام زنجیری. 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 هر مقدار دلخواهی داده ها، به جدول هش ما 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 اما اگر به جای داشتن یک مرتبط لیست که در آن مراجعه می O از n باشد، 293 00:14:15,610 --> 00:14:19,590 ما در حال حاضر 10 لیست های پیوندی، یا 1،000 لیست های پیوندی، 294 00:14:19,590 --> 00:14:24,120 در حال حاضر آن O از N تقسیم بر 10، و یا O از N تقسیم 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 بنابراین این جدول هش ما بود قبل از جدول هش ما اعلام کرد که 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 در حال حاضر جدول هش ما را برای رفتن به آرایه ای از 10 گره، اشاره گر 313 00:15:20,170 --> 00:15:22,120 به سر از لیست های پیوندی. 314 00:15:22,120 --> 00:15:23,830 >> و در حال حاضر آن را تهی. 315 00:15:23,830 --> 00:15:26,170 هر یک از این 10 اشاره گر تهی است. 316 00:15:26,170 --> 00:15:29,870 هیچ چیز در ما جدول هش در حال حاضر. 317 00:15:29,870 --> 00:15:32,690 >> حالا اجازه دهید شروع به قرار دادن برخی از چیزها را به این جدول هش. 318 00:15:32,690 --> 00:15:35,440 و بیایید ببینید که چگونه این روش این است رفتن به نفع ما یک کمی. 319 00:15:35,440 --> 00:15:36,760 اکنون بیایید هش جوی. 320 00:15:36,760 --> 00:15:40,210 ما در رشته جوی از طریق شما را اجرا خواهد کرد یک تابع هش و ما بازگشت 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 بنابراین اجازه دهید به صورت پویا اختصاص فضا برای جوی، 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 هنگامی که ما هش جوی ما در 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 و گره در لیست پیوندی جوی است. 333 00:16:18,350 --> 00:16:22,300 >> بنابراین اگر ما نیاز به نگاه کردن جوی بعد، ما فقط جوی هش دوباره، 334 00:16:22,300 --> 00:16:26,300 ما 6 بار دیگر به دلیل ما تابع هش قطعی است. 335 00:16:26,300 --> 00:16:30,400 و سپس ما در شروع به سر از لیست پیوندی اشاره 336 00:16:30,400 --> 00:16:33,360 به محل آرایه 6، و ما می توانیم تکرار 337 00:16:33,360 --> 00:16:35,650 که در سراسر تلاش برای پیدا کردن جوی. 338 00:16:35,650 --> 00:16:37,780 و اگر ما ساخت ما جدول هش به طور موثر، 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 اکنون بیایید هش راس. 348 00:17:04,290 --> 00:17:07,540 >> و اجازه دهید بگویم راس، زمانی که ما این کار را کد هش ما تماس 2 است. 349 00:17:07,540 --> 00:17:10,630 خوب در حال حاضر ما به صورت پویا اختصاص گره جدید، ما در راس آن گره قرار داده است، 350 00:17:10,630 --> 00:17:14,900 و ما اکنون می گویند مکانهای آرایه 2، به جای اشاره به تهی، 351 00:17:14,900 --> 00:17:18,579 اشاره به سر یک مرتبط لیست که تنها گره راس است. 352 00:17:18,579 --> 00:17:22,660 و ما می توانیم این را یک بار دیگر انجام دهید، ما می توانید راشل هش و 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 بیایید ببینید که چگونه ما رسیدگی برخورد با استفاده از روش زنجیره جداگانه. 358 00:17:38,560 --> 00:17:39,800 بیایید هش قمر. 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 >> ما نمی خواهیم به کتک زدن جوی و ما در حال حاضر 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 برای قمر. 368 00:18:00,220 --> 00:18:04,764 >> ما می گویند نقطه اشاره گر قمر به سر های قدیمی از لیست پیوندی، 369 00:18:04,764 --> 00:18:07,180 و سپس 6 فقط به نقاط رئیس جدید لیست پیوندی. 370 00:18:07,180 --> 00:18:10,150 و در حال حاضر نگاه کنید، ما قمر در تغییر است. 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 >> که تقریبا همه است به زنجیره وجود دارد. 374 00:18:20,147 --> 00:18:21,980 و زنجیری است که قطعا روش که 375 00:18:21,980 --> 00:18:27,390 رفتن به ترین برای شما اگر موثر شما در حال ذخیره سازی داده ها در یک جدول هش. 376 00:18:27,390 --> 00:18:30,890 اما این ترکیب از آرایه ها و لیست های پیوندی 377 00:18:30,890 --> 00:18:36,080 هم به صورت یک جدول هش واقعا به طور چشمگیری بهبود توانایی خود را 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 من داگ لوید هستم، این CS50. 385 00:18:58,930 --> 00:19:00,214