1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:01,900 [MUSIC PLAYING] 3 00:00:01,900 --> 00:00:05,710 4 00:00:05,710 --> 00:00:09,150 >> DOUG LLOYD: İndi siz Diziler haqqında çox bilmək, 5 00:00:09,150 --> 00:00:11,610 və bağlı siyahıları haqqında bir çox bilirik. 6 00:00:11,610 --> 00:00:13,650 Və biz müzakirə etdik lehte ve eksiklikleri, biz 7 00:00:13,650 --> 00:00:16,620 siyahıları bağlı ki, müzakirə böyük və kiçik əldə edə bilərsiniz, 8 00:00:16,620 --> 00:00:18,630 lakin onlar daha ölçüsü almaq. 9 00:00:18,630 --> 00:00:22,359 Diziler daha sadə var istifadə, lakin onlar qədər məhdudlaşdırıcı istəyirik 10 00:00:22,359 --> 00:00:24,900 biz ölçüsünü təyin etmək kimi çox başında array 11 00:00:24,900 --> 00:00:26,910 sonra biz ilə vurulmuş edirik. 12 00:00:26,910 --> 00:00:30,470 >> Amma ki, biz olduqca çox var var, Bizim mövzular bütün canı 13 00:00:30,470 --> 00:00:33,040 bağlı siyahıları və Diziler haqqında. 14 00:00:33,040 --> 00:00:34,950 Yoxsa biz var? 15 00:00:34,950 --> 00:00:37,720 Bəlkə biz bir şey edə bilərsiniz daha yaradıcı. 16 00:00:37,720 --> 00:00:40,950 Və verir ki, sort bir hash masa ideyası. 17 00:00:40,950 --> 00:00:46,680 >> Belə ki, bir hash masa biz cəhd olacaq bir bağlı siyahı ilə bir sıra birləşdirir. 18 00:00:46,680 --> 00:00:49,520 Biz üstünlükləri olacaq serialın, təsadüfi giriş kimi, 19 00:00:49,520 --> 00:00:53,510 yalnız array getmək üçün qadir olan element 4 və ya array element 8 20 00:00:53,510 --> 00:00:55,560 üzrə təkrarlamaq olmadan. 21 00:00:55,560 --> 00:00:57,260 Bu doğru, olduqca sürətli var? 22 00:00:57,260 --> 00:01:00,714 >> Amma biz də məlumatlar var istəyirəm strukturu inkişaf və shrink edə bilərsiniz. 23 00:01:00,714 --> 00:01:02,630 Biz deyil, ehtiyac yoxdur məhdudlaşdırılacaq istəyirik. 24 00:01:02,630 --> 00:01:04,588 Və biz etmək istəyirəm əlavə və hər şeyi aradan qaldırılması üçün 25 00:01:04,588 --> 00:01:08,430 çox asanlıqla, siz geri əgər, bir sıra ilə çox mürəkkəbdir. 26 00:01:08,430 --> 00:01:11,650 Və biz bu zəng edə bilərsiniz yeni bir şey bir hash masa. 27 00:01:11,650 --> 00:01:15,190 >> Əgər düzgün tətbiq biz növ alaraq edirik 28 00:01:15,190 --> 00:01:18,150 həm də məlumatların üstünlükləri Əgər siz artıq gördüm strukturları, 29 00:01:18,150 --> 00:01:19,880 Diziler və bağlı siyahıları. 30 00:01:19,880 --> 00:01:23,070 Taxmaq başlaya bilərsiniz 1 teta doğru edirlər. 31 00:01:23,070 --> 00:01:26,207 Theta biz, həqiqətən, müzakirə deyil, lakin teta yalnız orta olduğu, 32 00:01:26,207 --> 00:01:27,540 nə həqiqətən baş verəcək. 33 00:01:27,540 --> 00:01:29,680 Siz həmişə fikrində deyilik ən pis halda ssenari var, 34 00:01:29,680 --> 00:01:32,555 və həmişə fikrində deyilik Ən yaxşı ssenari, belə ki, nə var 35 00:01:32,555 --> 00:01:33,900 orta ssenari? 36 00:01:33,900 --> 00:01:36,500 >> Yaxşı bir orta durub bir hash masa 37 00:01:36,500 --> 00:01:39,370 yaxın daimi vaxt almaq üçün başlaya bilərsiniz. 38 00:01:39,370 --> 00:01:41,570 Və silinməsi əldə edə bilərsiniz daimi zaman bağlayın. 39 00:01:41,570 --> 00:01:44,440 Və Sistemi əldə edə bilərsiniz daimi zaman bağlayın. 40 00:01:44,440 --> 00:01:48,600 That bir məlumat yoxdur strukturu hələ ki, bunu edə bilərsiniz, 41 00:01:48,600 --> 00:01:51,180 və bu, artıq səslər olduqca böyük şey kimi. 42 00:01:51,180 --> 00:01:57,010 Biz, həqiqətən, yumşaldılmasına etdik öz hər mənfi cəhətləri. 43 00:01:57,010 --> 00:01:59,160 >> Bu performansı almaq üçün , baxmayaraq ki biz təkmilləşdirmək 44 00:01:59,160 --> 00:02:03,580 biz əlavə nə yenidən etmək lazımdır strukturu data. 45 00:02:03,580 --> 00:02:07,380 Xüsusilə biz istəyirik data özü bizə 46 00:02:07,380 --> 00:02:09,725 harada strukturunda getməlidir. 47 00:02:09,725 --> 00:02:12,850 Və biz o var görmek üçün lazımdır, əgər strukturu, biz tapmaq lazımdır, 48 00:02:12,850 --> 00:02:16,610 biz məlumatların baxmaq istəyirəm yenidən və səmərəli edə bilər, 49 00:02:16,610 --> 00:02:18,910 veri istifadə edərək, təsadüfi daxil. 50 00:02:18,910 --> 00:02:20,700 Just baxaraq data biz olmalıdır 51 00:02:20,700 --> 00:02:25,890 məhz biz olduğunuz bir fikir hash masa tapmaq üçün gedir. 52 00:02:25,890 --> 00:02:28,770 >> Bir hash İndi İşin mənfi tərəfi odur masa həqiqətən istəyirik ki, 53 00:02:28,770 --> 00:02:31,770 sifariş və ya data çeşidlənməsi olduqca pis. 54 00:02:31,770 --> 00:02:34,970 Və əslində, siz başlamaq əgər sifariş və ya sort üçün onlara istifadə etmək 55 00:02:34,970 --> 00:02:37,990 data bütün itirmək üstünlükləri əvvəllər 56 00:02:37,990 --> 00:02:40,710 durub və silinməsi baxımından idi. 57 00:02:40,710 --> 00:02:44,060 vaxt yaxın olur n teta, və biz əsasən var 58 00:02:44,060 --> 00:02:45,530 bir bağlı siyahısına daxil gerilədi. 59 00:02:45,530 --> 00:02:48,850 Və belə ki, biz yalnız hash istifadə etmək istədiyiniz masalar biz qayğı yoxdur, əgər 60 00:02:48,850 --> 00:02:51,490 data çeşidlənir olub. 61 00:02:51,490 --> 00:02:54,290 Kontekstində olan CS50 onları istifadə edəcəyik 62 00:02:54,290 --> 00:02:58,900 Siz yəqin ki, qayğı yoxdur data çeşidlənir ki. 63 00:02:58,900 --> 00:03:03,170 >> Belə ki, bir hash table bir birləşməsidir iki fərqli ədəd 64 00:03:03,170 --> 00:03:04,980 olan biz tanış edirik. 65 00:03:04,980 --> 00:03:07,930 ilk funksiyası olan biz adətən bir hash funksiyası zəng. 66 00:03:07,930 --> 00:03:11,760 Və hash funksiyası gedir , bəzi qeyri-mənfi tam qayıtmaq hansı 67 00:03:11,760 --> 00:03:14,870 biz adətən OK, bir hashcode zəng? 68 00:03:14,870 --> 00:03:20,230 ikinci parça bir sıra edir tipli biz saxlanılması məlumatların bilən 69 00:03:20,230 --> 00:03:22,190 data strukturu yerləşdirmək istəyirəm. 70 00:03:22,190 --> 00:03:24,310 Biz off keçirmək lazımdır İndi siyahısı element bağlıdır 71 00:03:24,310 --> 00:03:27,810 və yalnız bir əsasları ilə başlamaq onun ətrafında baş almaq üçün masa hash, 72 00:03:27,810 --> 00:03:30,210 sonra biz bəlkə zərbə olacaq fikrinizi bir az zaman 73 00:03:30,210 --> 00:03:32,920 birlikdə Diziler və link siyahıları birləşdirir. 74 00:03:32,920 --> 00:03:35,590 >> əsas fikir olsa bəzi məlumatları almaq deyil. 75 00:03:35,590 --> 00:03:37,860 Biz data vasitəsilə run hash funksiyası. 76 00:03:37,860 --> 00:03:41,980 Və belə data emal və OK, bir sıra spits? 77 00:03:41,980 --> 00:03:44,890 Və sonra sayı biz yalnız veri 78 00:03:44,890 --> 00:03:48,930 biz saxlamaq istəyirəm ki, yeri array. 79 00:03:48,930 --> 00:03:53,990 Belə ki, məsələn, biz bəlkə var strings bu hash masa. 80 00:03:53,990 --> 00:03:57,350 Bu, belə ki, bu 10 elementlər var biz onu 10 strings uyğun bilər. 81 00:03:57,350 --> 00:03:59,320 >> Biz John hash istəyirəm deyirlər. 82 00:03:59,320 --> 00:04:02,979 John Belə ki, data kimi biz əlavə etmək istəyirəm haradasa bu hash masa. 83 00:04:02,979 --> 00:04:03,770 Harada biz qoymaq bilərəm? 84 00:04:03,770 --> 00:04:05,728 Yaxşı adətən ilə array günə qədər biz yəqin ki, 85 00:04:05,728 --> 00:04:07,610 array yeri 0 onu qoymaq olardı. 86 00:04:07,610 --> 00:04:09,960 Amma indi biz bu yeni hash funksiyası var. 87 00:04:09,960 --> 00:04:13,180 >> Və biz John run ki, bildirin Bu hash funksiyası vasitəsilə 88 00:04:13,180 --> 00:04:15,417 və 4 spits oldu. 89 00:04:15,417 --> 00:04:17,500 Biz olduğunuz yaxşı ki var John qoymaq istəyirəm olacaq. 90 00:04:17,500 --> 00:04:22,050 Biz array yeri Yəhya qoymaq istəyirəm 4, biz again-- John hash, çünki 91 00:04:22,050 --> 00:04:23,810 nin sonra biz deyək axtarış və görmək istəyirik 92 00:04:23,810 --> 00:04:26,960 John bu hash varsa biz nə etmək lazımdır bütün Masa 93 00:04:26,960 --> 00:04:30,310 Eyni hash vasitəsilə idarə olunur funksiyası, sayı 4 çıxmaq 94 00:04:30,310 --> 00:04:33,929 və John tapa biləcəklər dərhal data strukturu. 95 00:04:33,929 --> 00:04:34,720 Bu olduqca yaxşı. 96 00:04:34,720 --> 00:04:36,928 >> Biz indi bunu deyirlər yenə biz Paulun hash istəyirik. 97 00:04:36,928 --> 00:04:39,446 Biz Paul əlavə etmək istədiyiniz Bu hash masa. 98 00:04:39,446 --> 00:04:42,070 Bu dəfə biz run deyirlər Hash funksiyası vasitəsilə Paul, 99 00:04:42,070 --> 00:04:44,600 yaradılan hashcode 6. 100 00:04:44,600 --> 00:04:47,340 Yaxşı indi biz Paul qoya bilər array yeri 6. 101 00:04:47,340 --> 00:04:50,040 Və biz olmadığını baxmaq lazımdır Paul bu hash masa var, 102 00:04:50,040 --> 00:04:53,900 biz nə etmək lazımdır bütün Paul run hash funksiyası vasitəsilə yenidən 103 00:04:53,900 --> 00:04:55,830 və biz yenə 6 almaq olacaq. 104 00:04:55,830 --> 00:04:57,590 >> Və sonra biz yalnız baxmaq array yeri 6. 105 00:04:57,590 --> 00:04:58,910 Paul varmı? 106 00:04:58,910 --> 00:05:00,160 Əgər belədirsə, o, hash masa var. 107 00:05:00,160 --> 00:05:01,875 Paul yoxdur? 108 00:05:01,875 --> 00:05:03,000 O, hash cədvəldə deyil. 109 00:05:03,000 --> 00:05:05,720 Bu olduqca sadə. 110 00:05:05,720 --> 00:05:07,770 >> İndi necə bir hash funksiyası müəyyən edirsiniz? 111 00:05:07,770 --> 00:05:11,460 Yaxşı həqiqətən heç bir limit var mümkün hash funksiyalarının sayı. 112 00:05:11,460 --> 00:05:14,350 Əslində bir sıra həqiqətən var internet, həqiqətən, yaxşı olanları. 113 00:05:14,350 --> 00:05:17,560 Bir sıra həqiqətən var internet, həqiqətən, pis olanları. 114 00:05:17,560 --> 00:05:21,080 O, həmçinin olduqca asandır pis bir yazmaq. 115 00:05:21,080 --> 00:05:23,760 >> Belə ki, nə bir yaxşı təşkil edir hash funksiyası, sağ? 116 00:05:23,760 --> 00:05:27,280 Yaxşı yaxşı hash funksiyası olmalıdır yalnız data hashed olunur istifadə, 117 00:05:27,280 --> 00:05:29,420 və məlumatların bütün hashed olunur. 118 00:05:29,420 --> 00:05:32,500 Beləliklə, biz anything-- istifadə etmək istəmirəm biz bir şey daxil deyil 119 00:05:32,500 --> 00:05:35,560 data başqa başqa. 120 00:05:35,560 --> 00:05:37,080 Biz data bütün istifadə etmək istəyirik. 121 00:05:37,080 --> 00:05:39,830 Biz yalnız bir parça istifadə etmək istəmirəm bu, biz bunu bütün istifadə etmək istəyirik. 122 00:05:39,830 --> 00:05:41,710 A hash funksiyası olmalıdır də deterministic olun. 123 00:05:41,710 --> 00:05:42,550 Bunun mənası nədir? 124 00:05:42,550 --> 00:05:46,200 Yaxşı o deməkdir ki, hər dəfə biz məlumatların eyni parça keçmək 125 00:05:46,200 --> 00:05:50,040 hash funksiyası daxil biz həmişə Eyni hashcode çıxmaq. 126 00:05:50,040 --> 00:05:52,870 Mən daxil John keçmək əgər hash funksiyası Mən 4 çıxmaq. 127 00:05:52,870 --> 00:05:56,110 Mən bunu etmək lazımdır 10,000 dəfə və mən həmişə 4 almaq lazımdır. 128 00:05:56,110 --> 00:06:00,810 Belə ki, heç təsadüfi nömrələri səmərəli Bizim hash cəlb edilə bilər tables-- 129 00:06:00,810 --> 00:06:02,750 Bizim hash funksiyaları. 130 00:06:02,750 --> 00:06:05,750 >> A hash funksiyası da olmalıdır uniformly məlumat yaymaq. 131 00:06:05,750 --> 00:06:09,700 Hər zaman vasitəsilə məlumat çalıştırıyorsanız hash funksiyası, hashcode 0 almaq 132 00:06:09,700 --> 00:06:11,200 doğru, yəqin ki, o qədər də böyük deyil? 133 00:06:11,200 --> 00:06:14,600 Siz yəqin ki, böyük istəyirəm hash kodları bir sıra. 134 00:06:14,600 --> 00:06:17,190 Həmçinin şeyi yayılmışdır bilər masa ərzində həyata. 135 00:06:17,190 --> 00:06:23,210 Və həmçinin, əgər həqiqətən böyük olacaq John və Yonatan kimi oxşar məlumatlar, 136 00:06:23,210 --> 00:06:26,320 bəlkə çəkin yayılmışdır edildi hash cədvəldə müxtəlif yerlərdə. 137 00:06:26,320 --> 00:06:28,750 Ki, bir gözəl üstünlüyü olacaq. 138 00:06:28,750 --> 00:06:31,250 >> Burada hash funksiyası bir misal var. 139 00:06:31,250 --> 00:06:33,150 Mən əvvəllər bu bir qədər yazdı. 140 00:06:33,150 --> 00:06:35,047 Bu xüsusilə deyil yaxşı hash funksiyası 141 00:06:35,047 --> 00:06:37,380 həqiqətən, yoxdur səbəblərə görə İndi gedən daşıyırlar. 142 00:06:37,380 --> 00:06:41,040 Amma burada nə olub görürsünüz? 143 00:06:41,040 --> 00:06:44,420 Biz bir dəyişən elan edirik kimi görünür məbləği və 0-a bərabər qəbulu çağırıb. 144 00:06:44,420 --> 00:06:50,010 Və sonra yəqin mən bir şey edirəm belə uzun strstr [j] bərabər deyil 145 00:06:50,010 --> 00:06:52,490 0 backslash üçün. 146 00:06:52,490 --> 00:06:54,870 Mən orada nə edirəm? 147 00:06:54,870 --> 00:06:57,440 >> Bu əsasən yalnız başqa [həyata keçirilməsi yolu? Strl?] 148 00:06:57,440 --> 00:06:59,773 Siz var zaman aşkar simli sona gəlindi. 149 00:06:59,773 --> 00:07:02,480 Belə ki, Mən, həqiqətən, yoxdur simli uzunluğu hesablamaq, 150 00:07:02,480 --> 00:07:05,640 Mən hit zaman mən yalnız istifadə edirəm backslash 0 xarakter bilirəm 151 00:07:05,640 --> 00:07:07,185 Mən simli sonunda əldə etdiyiniz. 152 00:07:07,185 --> 00:07:09,560 Və sonra mən saxlamaq üçün gedirəm ki, simli vasitəsilə iterating, 153 00:07:09,560 --> 00:07:15,310 strstr [j] əlavə sonra yekunlaşdırmaq, və Günün sonunda məbləği mod geri olacaq 154 00:07:15,310 --> 00:07:16,200 HASH_MAX. 155 00:07:16,200 --> 00:07:18,700 >> Əsasən bütün bu hash funksiyası əlavə olunur edir 156 00:07:18,700 --> 00:07:23,450 ASCII dəyərləri bütün Mənim string, sonra var 157 00:07:23,450 --> 00:07:26,390 bəzi hashcode qaytarılması HASH_MAX tərəfindən modded. 158 00:07:26,390 --> 00:07:29,790 Bu yəqin ki, ölçüsü var Mənim serialın, sağ? 159 00:07:29,790 --> 00:07:33,160 Mən hash əldə etmək istəmirəm kodları mənim array ölçüsü 10 olduqda, 160 00:07:33,160 --> 00:07:35,712 Mən əldə olmaq istəmirəm həyata hash kodları 11, 12, 161 00:07:35,712 --> 00:07:38,690 13, mən daxil şeyi qoymaq bilməz serialın o locations, 162 00:07:38,690 --> 00:07:39,790 ki, qeyri-qanuni ola bilər. 163 00:07:39,790 --> 00:07:42,130 Mən bir seqmentasiya günah əziyyət ediyorum. 164 00:07:42,130 --> 00:07:45,230 >> İndi burada bir sürətli kənara edir. 165 00:07:45,230 --> 00:07:48,470 Ümumiyyətlə siz yəqin ki, fikrində deyilik öz hash funksiyaları yazmaq istəyirəm. 166 00:07:48,470 --> 00:07:50,997 Bu, həqiqətən bir az bir sənət, bir elm. 167 00:07:50,997 --> 00:07:52,580 Onların gider bir çox var. 168 00:07:52,580 --> 00:07:55,288 Dediyim kimi internet, tam həqiqətən yaxşı hash funksiyaları, 169 00:07:55,288 --> 00:07:58,470 və internet istifadə etməlidir Bu, həqiqətən, çünki hash funksiyaları tapmaq 170 00:07:58,470 --> 00:08:03,230 yalnız cür gərəksiz vaxt itkisi öz yaratmaq. 171 00:08:03,230 --> 00:08:05,490 >> Siz sadə olanları yaza bilərsiniz məqsədləri test üçün. 172 00:08:05,490 --> 00:08:08,323 Amma əslində gedən zaman məlumat hashing və saxlanılması başlamaq 173 00:08:08,323 --> 00:08:10,780 Siz bu hash masa yəqin ki, istəyirəm olacaq 174 00:08:10,780 --> 00:08:14,580 istehsal edilmişdir bəzi funksiyadan istifadə etmək Sizin üçün ki, internet mövcuddur. 175 00:08:14,580 --> 00:08:17,240 Yalnız əmin olun deyilsə Sizin mənbələri istinad. 176 00:08:17,240 --> 00:08:21,740 Heç bir səbəb üçün var burada bir şey plagiarize. 177 00:08:21,740 --> 00:08:25,370 >> informatika icma edir mütləq dəyərlər artan və həqiqətən 178 00:08:25,370 --> 00:08:28,796 açıq mənbə və bu, həqiqətən vacibdir Sizin mənbələri istinad ki, insanlar 179 00:08:28,796 --> 00:08:30,670 üçün attribution əldə edə bilərsiniz onlar iş 180 00:08:30,670 --> 00:08:32,312 cəmiyyətin xeyrinə edirik. 181 00:08:32,312 --> 00:08:34,020 Belə ki, həmişə sure-- ola və yalnız hash üçün 182 00:08:34,020 --> 00:08:37,270 funksiyaları, lakin ümumiyyətlə zaman bir kənarda mənbədən kodu istifadə, 183 00:08:37,270 --> 00:08:38,299 həmişə mənbə istinad. 184 00:08:38,299 --> 00:08:43,500 Etdi şəxsə kredit vermək iş bəzi belə yoxdur. 185 00:08:43,500 --> 00:08:46,720 >> OK, belə ki, bu yenidən edək ikinci hash masa. 186 00:08:46,720 --> 00:08:48,780 Biz sol yerdir biz daxil sonra 187 00:08:48,780 --> 00:08:53,300 Bu hash masa John və Paul. 188 00:08:53,300 --> 00:08:55,180 Burada bir problem görürsünüzmü? 189 00:08:55,180 --> 00:08:58,410 Siz iki görə bilərsiniz. 190 00:08:58,410 --> 00:09:02,240 Amma xüsusilə, siz Bu mümkün problem görmək? 191 00:09:02,240 --> 00:09:06,770 >> Mən Ringo hash və əgər sonra emal çıxır ki, 192 00:09:06,770 --> 00:09:14,000 hash funksiyası vasitəsilə data Ringo də hashcode 6 yaradılan. 193 00:09:14,000 --> 00:09:16,810 Mən artıq data var hashcode-- array yeri 6. 194 00:09:16,810 --> 00:09:22,000 Belə ki, yəqin ki, bir az olacaq İndi mənim üçün bir problem, sağ? 195 00:09:22,000 --> 00:09:23,060 >> Biz toqquşma çağırırıq. 196 00:09:23,060 --> 00:09:26,460 Və toqquşma iki baş verir məlumatların ədəd eyni hash vasitəsilə run 197 00:09:26,460 --> 00:09:29,200 funksiyası eyni hashcode verir. 198 00:09:29,200 --> 00:09:32,850 Ehtimal biz hələ də almaq istəyirəm hash masa məlumatların ədəd, 199 00:09:32,850 --> 00:09:36,330 əks halda biz Ringo çalışan olmaz özbaşına hash funksiyası vasitəsilə. 200 00:09:36,330 --> 00:09:40,870 Biz ehtimalla almaq istəyirəm Ki array daxil Ringo. 201 00:09:40,870 --> 00:09:46,070 >> Biz baxmayaraq bunu necə, o, əgər və Paul, həm də gəlir hashcode 6? 202 00:09:46,070 --> 00:09:49,520 Biz Paul yazmaq istəmirəm, biz Paul orada olmaq istəyirəm. 203 00:09:49,520 --> 00:09:52,790 Beləliklə, biz almaq üçün bir yol tapmaq lazımdır hash masa elementləri ki 204 00:09:52,790 --> 00:09:56,550 hələ bizim sürətli qoruyur durub və göz atınız up. 205 00:09:56,550 --> 00:10:01,350 Və onunla məşğul bir yol var probing xətti deyilən bir şey yoxdur. 206 00:10:01,350 --> 00:10:04,170 >> Bir varsa, bu metodu istifadə edərək toqquşma, yaxşı, biz nə etməliyəm? 207 00:10:04,170 --> 00:10:08,580 Yaxşı array yeri onu qoymaq bilməz 6, və ya hər hansı hashcode istehsal edilmişdir, 208 00:10:08,580 --> 00:10:10,820 nin hashcode plus 1 onu qoymaq bildirin. 209 00:10:10,820 --> 00:10:13,670 Və tam edək, əgər hashcode plus 2 onu qoydu. 210 00:10:13,670 --> 00:10:17,420 Bu varlığın fayda o əgər tam biz o hesab edirəm olduğu, 211 00:10:17,420 --> 00:10:20,850 və biz axtarış başlamaq üçün, bəlkə biz çox uzaq getmək yoxdur. 212 00:10:20,850 --> 00:10:23,900 Bəlkə biz axtarış yoxdur hash masa bütün n elementləri. 213 00:10:23,900 --> 00:10:25,790 Bəlkə biz axtarış Onların bir neçə. 214 00:10:25,790 --> 00:10:30,680 >> Və belə ki, biz hələ doğru meyl edirik orta işi 1 yaxın vs gedir 215 00:10:30,680 --> 00:10:34,280 n yaxın, belə ki, bəlkə ki, işləmək lazımdır. 216 00:10:34,280 --> 00:10:38,010 Belə ki, necə bu görək əslində iş bilər. 217 00:10:38,010 --> 00:10:41,460 Və bəlkə biz aşkar edə bilərsiniz əgər in görək Burada baş verə bilər problem. 218 00:10:41,460 --> 00:10:42,540 >> Biz Bart hash deyirlər. 219 00:10:42,540 --> 00:10:45,581 Belə ki, indi biz yeni bir sıra çalıştırmak olacaq hash funksiyası vasitəsilə strings, 220 00:10:45,581 --> 00:10:48,460 və biz hash vasitəsilə Bartın run funksiyası, biz hashcode 6 almaq. 221 00:10:48,460 --> 00:10:52,100 Biz bir nəzər, biz 6 görmək boş, belə ki, biz orada Bart bilər. 222 00:10:52,100 --> 00:10:55,410 >> İndi biz Lisa və hash də hashcode 6 yaradır. 223 00:10:55,410 --> 00:10:58,330 Yaxşı indi biz bu istifadə etdiyiniz ki, xətti, biz 6-da başlayacaq metodu yoxlamağa 224 00:10:58,330 --> 00:10:59,330 biz 6 dolu olduğunu görürük. 225 00:10:59,330 --> 00:11:00,990 Biz 6 Lisa qoymaq bilməz. 226 00:11:00,990 --> 00:11:02,090 Beləliklə, biz getmək yoxdur? 227 00:11:02,090 --> 00:11:03,280 7 gedək. 228 00:11:03,280 --> 00:11:04,610 7-nin boş, belə işləyir. 229 00:11:04,610 --> 00:11:06,510 Belə ki, orada Lisa qoymaq bildirin. 230 00:11:06,510 --> 00:11:10,200 >> İndi biz Homer hash və 7 almaq. 231 00:11:10,200 --> 00:11:13,380 OK, biz bilirik 7-nin tam ki, İndi, belə ki, biz orada Homer qoymaq bilməz. 232 00:11:13,380 --> 00:11:14,850 Belə ki, 8 gedək. 233 00:11:14,850 --> 00:11:15,664 8 bilər? 234 00:11:15,664 --> 00:11:18,330 Bəli, və 7 8 yaxın, belə ki, əgər Biz istəyirik axtarış başlamaq üçün 235 00:11:18,330 --> 00:11:20,020 çox uzaq getmək üçün var niyyətində deyil. 236 00:11:20,020 --> 00:11:22,860 Və belə ki, 8 Homer qoymaq bildirin. 237 00:11:22,860 --> 00:11:25,151 >> İndi biz hash Maggie və 3 qaytarır şükür 238 00:11:25,151 --> 00:11:26,650 biz yalnız orada Maggie qoymaq istəyirik. 239 00:11:26,650 --> 00:11:29,070 Biz heç nə yoxdur sort ki yoxlamağa. 240 00:11:29,070 --> 00:11:32,000 İndi biz Marge hash və Marge də 6 qaytarır. 241 00:11:32,000 --> 00:11:39,560 >> Yaxşı 6, 8 dolu, 7 tam, tam 9, bütün sağ 9 boş, Allaha şükür. 242 00:11:39,560 --> 00:11:41,600 Mən 9 Marge bilər. 243 00:11:41,600 --> 00:11:45,280 Onsuz da biz başlanğıc etdiyiniz görə bilərsiniz biz istəyirik indi bu problem 244 00:11:45,280 --> 00:11:48,780 cür şeyi uzanır başlayır uzaq onların hash kodları. 245 00:11:48,780 --> 00:11:52,960 Və 1 ki teta ki, orta daimi vaxt olan halda, 246 00:11:52,960 --> 00:11:56,560 bir az more-- almaq üçün başlayır bir az daha meyli başlayaraq 247 00:11:56,560 --> 00:11:58,050 n teta doğru. 248 00:11:58,050 --> 00:12:01,270 Biz ki, itirmək üçün başlanğıc edirik hash masalar üstünlüyü. 249 00:12:01,270 --> 00:12:03,902 >> Biz yalnız gördüm bu problem klasterləşmə deyilən bir şey var. 250 00:12:03,902 --> 00:12:06,360 Və həqiqətən pis nə var klasterləşmə ki, sizin bir dəfə indi 251 00:12:06,360 --> 00:12:09,606 yan iki elementləri ilə var bu, daha çox edir yan, 252 00:12:09,606 --> 00:12:11,480 Siz ikiqat şans, siz olacaq 253 00:12:11,480 --> 00:12:13,516 başqa toqquşma var ki çoxluq ilə, 254 00:12:13,516 --> 00:12:14,890 və cluster biri artacaq. 255 00:12:14,890 --> 00:12:19,640 Və artan və artan saxlamaq lazımdır bir toqquşma olan sizin ehtimalı. 256 00:12:19,640 --> 00:12:24,470 Və nəticədə bu kimi pis kimi bütün məlumatların çeşidlənməsi deyil. 257 00:12:24,470 --> 00:12:27,590 >> digər problem olsa biz hələ və bu günə qədər bu nöqtəyə qədər, 258 00:12:27,590 --> 00:12:30,336 biz yalnız növ oldum bir hash table nə anlama, 259 00:12:30,336 --> 00:12:31,960 biz hələ yalnız 10 strings üçün otaq var. 260 00:12:31,960 --> 00:12:37,030 Biz hash davam etmək istəyirsinizsə, Springfield vətəndaşları, 261 00:12:37,030 --> 00:12:38,790 biz yalnız orada onlardan 10 əldə edə bilərsiniz. 262 00:12:38,790 --> 00:12:42,619 Və biz cəhd və bir 11-ci və ya 12 əlavə biz onları qoymaq üçün bir yer yoxdur. 263 00:12:42,619 --> 00:12:45,660 Biz yalnız ətrafında iplik bilər dairələr, boş spot tapmaq üçün çalışırıq 264 00:12:45,660 --> 00:12:49,000 və biz bəlkə takılıyorum sonsuz loop. 265 00:12:49,000 --> 00:12:51,810 >> Belə ki, fikir verir bu cür bir şey chaining çağırıb. 266 00:12:51,810 --> 00:12:55,790 Və bu gətirmək olacaq harada geri şəkil bağlı siyahıları. 267 00:12:55,790 --> 00:13:01,300 Nə əvəzinə yalnız saxlanılması array data özü, 268 00:13:01,300 --> 00:13:04,471 serialın hər element bilər çox ədəd məlumatların keçirəcək? 269 00:13:04,471 --> 00:13:05,970 Yaxşı ki, sağ mənada etmir? 270 00:13:05,970 --> 00:13:09,280 Biz ki, bir sıra yalnız bilirik bir sıra hər bir element hold-- 271 00:13:09,280 --> 00:13:12,930 yalnız bir parça aça bilər ki, data növü məlumatların. 272 00:13:12,930 --> 00:13:16,750 >> Amma nə əgər data type bir bağlı siyahı sağ, var? 273 00:13:16,750 --> 00:13:19,830 Belə ki, nə əgər hər serialın element idi 274 00:13:19,830 --> 00:13:22,790 bir bağlı siyahı rəhbəri bir göstərici? 275 00:13:22,790 --> 00:13:24,680 Və sonra biz qurmaq bilər bu bağlı siyahıları 276 00:13:24,680 --> 00:13:27,120 və özbaşına onların inkişaf bağlı siyahıları imkan verir, çünki 277 00:13:27,120 --> 00:13:32,090 Bizə inkişaf və daha çox shrink bir sıra edir çevik çox. 278 00:13:32,090 --> 00:13:34,210 Belə ki, nə biz indi istifadə əgər, biz doğru, bu leverage? 279 00:13:34,210 --> 00:13:37,760 Biz bu zəncirlər inkişaf başlamaq bu array yerlərdə həyata. 280 00:13:37,760 --> 00:13:40,740 >> İndi biz sonsuz uyğun data məbləği, və ya sonsuz deyil, 281 00:13:40,740 --> 00:13:44,170 bir ixtiyari məbləği data, bizim hash masa 282 00:13:44,170 --> 00:13:47,760 Heç daxil çalışan olmadan Toqquşmanın problem. 283 00:13:47,760 --> 00:13:50,740 Biz də aradan sonra bu etməklə klasterləşmə. 284 00:13:50,740 --> 00:13:54,380 Və biz biz daxil zaman bilirik ki, bir bağlı siyahısına daxil, siz geri əgər 285 00:13:54,380 --> 00:13:57,779 story bağlı siyahıları bizim video bağlı siyahıları və ikiqat bağlı siyahıları, 286 00:13:57,779 --> 00:13:59,070 bu, daimi vaxt əməliyyat var. 287 00:13:59,070 --> 00:14:00,710 Biz yalnız ön əlavə edirik. 288 00:14:00,710 --> 00:14:04,400 >> Və baxmaq qədər, biz bilirik ki, bir bağlı siyahısında baxmaq 289 00:14:04,400 --> 00:14:05,785 sağ, bir problem ola bilər? 290 00:14:05,785 --> 00:14:07,910 Biz vasitəsilə axtarış əvvəldən sona. 291 00:14:07,910 --> 00:14:10,460 Heç bir təsadüfi var bir bağlı siyahı giriş. 292 00:14:10,460 --> 00:14:15,610 Amma əgər əvəzinə bir olan bağlı bir axtarış n Ey olardı siyahısı 293 00:14:15,610 --> 00:14:19,590 biz indi 10 bağlı siyahıları var, və ya 1000 bağlı siyahıları, 294 00:14:19,590 --> 00:14:24,120 indi 10 bölünür n O var, və ya n O 1000 bölünür. 295 00:14:24,120 --> 00:14:26,940 >> Və biz söhbət isə nəzəri mürəkkəbliyi haqqında 296 00:14:26,940 --> 00:14:30,061 biz real, sabitləri ardı bunlar həqiqətən məsələ dünya, 297 00:14:30,061 --> 00:14:30,560 sağ? 298 00:14:30,560 --> 00:14:33,080 Biz, həqiqətən, görəcəksiniz bu olur ki, 299 00:14:33,080 --> 00:14:36,610 daha sürətli 10 dəfə çalıştırmak üçün, və ya 1000 dəfə daha sürətli, 300 00:14:36,610 --> 00:14:41,570 biz uzun bir paylayaraq, çünki 1000 kiçik zəncirlər arasında zəncir. 301 00:14:41,570 --> 00:14:45,090 Və belə ki, biz hər zaman axtarmaq üçün biz o zəncirlər biri ilə 302 00:14:45,090 --> 00:14:50,290 biz qayğı yoxdur 999 zəncirlər ignore haqqında, və yalnız bir axtarış. 303 00:14:50,290 --> 00:14:53,220 >> Hansı orta edir 1000 dəfə qısa ola bilər. 304 00:14:53,220 --> 00:14:56,460 Və belə ki, biz hələ sort var Bu orta halda doğru baxma 305 00:14:56,460 --> 00:15:01,610 daimi vaxt olan, lakin yalnız biz yararlanarak, çünki 306 00:15:01,610 --> 00:15:03,730 bəzi böyük daimi amil bölünməsi. 307 00:15:03,730 --> 00:15:05,804 Bu necə ola bilər Baxaq həqiqətən baxmayaraq baxmaq. 308 00:15:05,804 --> 00:15:08,720 Belə ki, bu biz idi hash table idi bir hash masa elan əvvəl 309 00:15:08,720 --> 00:15:10,270 10 strings saxlanılması qadir idi. 310 00:15:10,270 --> 00:15:11,728 Biz artıq bunu etmək fikrində deyilik. 311 00:15:11,728 --> 00:15:13,880 Biz artıq bilirik ki, metodu məhdudiyyətlər. 312 00:15:13,880 --> 00:15:20,170 İndi bizim hash table olacaq 10 qovşaqlarının, göstəricilər bir sıra 313 00:15:20,170 --> 00:15:22,120 bağlı siyahıları rəhbərlərinə. 314 00:15:22,120 --> 00:15:23,830 >> Və indi bu null. 315 00:15:23,830 --> 00:15:26,170 Bu 10 göstəricilər hər bir null edir. 316 00:15:26,170 --> 00:15:29,870 Heç bir şey bizim var var İndi masa hash. 317 00:15:29,870 --> 00:15:32,690 >> İndi bəzi qoymaq başlamaq edək Bu hash masa şeylər. 318 00:15:32,690 --> 00:15:35,440 Və bu üsul necə edək Bizə bir az fayda gedir. 319 00:15:35,440 --> 00:15:36,760 İndi Joey hash edək. 320 00:15:36,760 --> 00:15:40,210 Biz simli Joey vasitəsilə davam edəcək lazımdır bir hash funksiyası və biz 6 qayıtmaq. 321 00:15:40,210 --> 00:15:41,200 Yaxşı indi nə etməliyəm? 322 00:15:41,200 --> 00:15:44,090 >> Yaxşı indi bağlı siyahıları ilə iş, biz serialların ilə iş deyilik. 323 00:15:44,090 --> 00:15:45,881 Və biz çalışırıq zaman bağlı siyahıları ilə biz 324 00:15:45,881 --> 00:15:49,790 biz dinamik başlamaq lazımdır bilirik space və tikinti zəncirlər bölüşdürülməsi. 325 00:15:49,790 --> 00:15:54,020 Ki, sort o əsas var how-- var bir bağlı siyahı bina elementləri. 326 00:15:54,020 --> 00:15:57,670 Belə ki, dinamik edək Joey üçün yerin ayrılması, 327 00:15:57,670 --> 00:16:00,390 Və sonra zəncir ona əlavə edək. 328 00:16:00,390 --> 00:16:03,170 >> Belə ki, indi biz etdik nə baxmaq. 329 00:16:03,170 --> 00:16:06,440 Biz Joey hash zaman hashcode 6 var. 330 00:16:06,440 --> 00:16:11,790 Array yeri 6 İndi pointer bir bağlı siyahı başı göstərir, 331 00:16:11,790 --> 00:16:14,900 və indi yalnız var bir bağlı siyahı element. 332 00:16:14,900 --> 00:16:18,350 Və ki, node bağlı siyahı Joey edir. 333 00:16:18,350 --> 00:16:22,300 >> Biz Joey baxmaq lazımdır, belə ki, sonra, biz yalnız yenidən Joey hash, 334 00:16:22,300 --> 00:16:26,300 biz bizimdir bizim çünki yenidən 6 almaq hash funksiyası deterministic edir. 335 00:16:26,300 --> 00:16:30,400 Və sonra biz baş-da başlayacaq bağlı siyahı işarə 336 00:16:30,400 --> 00:16:33,360 array yeri ilə 6 və biz təkrarlamaq bilər 337 00:16:33,360 --> 00:16:35,650 Joey tapmaq üçün çalışırıq ki, rast. 338 00:16:35,650 --> 00:16:37,780 Və biz qurmaq bizim səmərəli masa hash, 339 00:16:37,780 --> 00:16:41,790 və hash funksiyası səmərəli yaxşı məlumat yaymaq, 340 00:16:41,790 --> 00:16:45,770 orta hesabla o hər bağlı hər array yerdə siyahıları 341 00:16:45,770 --> 00:16:50,110 əgər ölçüsü 1/10 olacaq biz yalnız bir böyük kimi idi 342 00:16:50,110 --> 00:16:51,650 bu hər şeyi ilə bağlı siyahısı. 343 00:16:51,650 --> 00:16:55,670 >> Biz böyük bağlı olduğunu yaymaq 10 bağlı siyahıları arasında siyahısı 344 00:16:55,670 --> 00:16:57,760 Hər bir siyahı 1/10 ölçüsü olacaq. 345 00:16:57,760 --> 00:17:01,432 Və beləliklə 10 dəfə daha sürətli vasitəsilə axtarış. 346 00:17:01,432 --> 00:17:02,390 Belə ki, bir daha bunu edək. 347 00:17:02,390 --> 00:17:04,290 İndi Ross hash edək. 348 00:17:04,290 --> 00:17:07,540 >> Və biz bunu zaman Ross, deyək biz geri almaq hash kodu 2. 349 00:17:07,540 --> 00:17:10,630 Yaxşı indi biz dinamik bir ayrılması yeni node, biz ki, node Ross qoymaq 350 00:17:10,630 --> 00:17:14,900 və biz array yer indi demək 2 null işarə əvəzinə, 351 00:17:14,900 --> 00:17:18,579 bir bağlı rəhbəri göstərir yeganə node siyahısı Ross edir. 352 00:17:18,579 --> 00:17:22,660 Və biz, biz bu dəfə daha edə bilərsiniz Rachel hash və hashcode 4 əldə edə bilərsiniz. 353 00:17:22,660 --> 00:17:25,490 Rachel qoymaq, yeni node malloc node və array yeri demək 354 00:17:25,490 --> 00:17:27,839 4 indi baş işarə Onun bir bağlı siyahı 355 00:17:27,839 --> 00:17:31,420 yalnız element Rachel olmaq olur. 356 00:17:31,420 --> 00:17:33,470 >> OK lakin nə olur biz bir toqquşma var? 357 00:17:33,470 --> 00:17:38,560 Biz toqquşma idarə necə görmək edək ayrı-ayrı chaining metodundan istifadə. 358 00:17:38,560 --> 00:17:39,800 Nin Phoebe hash edək. 359 00:17:39,800 --> 00:17:41,094 Biz hashcode 6 almaq. 360 00:17:41,094 --> 00:17:44,010 Əvvəlki nümunədə biz yalnız idi serialda strings saxlanılması. 361 00:17:44,010 --> 00:17:45,980 Bu bir problem idi. 362 00:17:45,980 --> 00:17:48,444 >> Biz döymək istəmirəm Joey, və biz artıq var 363 00:17:48,444 --> 00:17:51,110 bəzi klasterləşmə əldə edə bilərsiniz ki, gördük problemlərini cəhd və addım 364 00:17:51,110 --> 00:17:52,202 vasitəsilə və sonda. 365 00:17:52,202 --> 00:17:54,660 Amma nə əgər biz yalnız növ bu hüquqa eyni şəkildə müalicə? 366 00:17:54,660 --> 00:17:57,440 Bu, sadəcə bir element əlavə kimi bir bağlı siyahı rəhbəri. 367 00:17:57,440 --> 00:18:00,220 Phoebe üçün yalnız malloc yer edək. 368 00:18:00,220 --> 00:18:04,764 >> Biz Phoebe növbəti pointer xal demək lazımdır bağlı siyahı köhnə rəhbəri, 369 00:18:04,764 --> 00:18:07,180 və sonra 6 yalnız işarə bağlı siyahı yeni rəhbəri. 370 00:18:07,180 --> 00:18:10,150 İndi biz Phoebe dəyişdirdik, baxmaq. 371 00:18:10,150 --> 00:18:14,210 Biz indi iki bilərsiniz hashcode 6 elementləri, 372 00:18:14,210 --> 00:18:17,170 və hər hansı bir problem yoxdur. 373 00:18:17,170 --> 00:18:20,147 >> Olduqca çox bütün var zəncirləmə var. 374 00:18:20,147 --> 00:18:21,980 Və chaining mütləq deyil metodu 375 00:18:21,980 --> 00:18:27,390 əgər üçün ən effektiv olacaq Bir hash masa məlumatların saxlanılması olunur. 376 00:18:27,390 --> 00:18:30,890 Amma bu birləşməsi Diziler və bağlı siyahıları 377 00:18:30,890 --> 00:18:36,080 birlikdə həqiqətən bir hash masa yaratmaq üçün dramatik sizin qabiliyyətini artırır 378 00:18:36,080 --> 00:18:40,550 məlumatların böyük həcmdə saxlamaq, və çox tez və səmərəli axtarış 379 00:18:40,550 --> 00:18:41,630 ki, data vasitəsilə. 380 00:18:41,630 --> 00:18:44,150 >> Bir daha hələ var Orada data structure 381 00:18:44,150 --> 00:18:48,700 ki, hətta bir az ola bilər, təmin baxımından daha yaxşı 382 00:18:48,700 --> 00:18:51,920 ki, bizim durub, silinməsi, və yuxarı baxmaq dəfə daha sürətli edir. 383 00:18:51,920 --> 00:18:55,630 Və biz çalışır bir video görəcəksiniz. 384 00:18:55,630 --> 00:18:58,930 Mən Doug Lloyd deyiləm, bu CS50 edir. 385 00:18:58,930 --> 00:19:00,214