1 00:00:00,000 --> 00:00:11,856 2 00:00:11,856 --> 00:00:13,050 >> ROB BOWDEN: Dia duit. 3 00:00:13,050 --> 00:00:16,210 Tá mé Rob, agus a ligean ar hash an réiteach seo amach. 4 00:00:16,210 --> 00:00:20,070 Mar sin anseo táimid ag dul a chur i bhfeidhm tábla hash ginearálta. 5 00:00:20,070 --> 00:00:24,090 Feicimid go bhfuil an nód struct ar ár hash Tá tábla ag dul chun breathnú cosúil le seo. 6 00:00:24,090 --> 00:00:28,710 Mar sin, tá sé ag dul a bheith acu focal ruabhreac sraith de fhad méid móide 1. 7 00:00:28,710 --> 00:00:32,259 Ná déan dearmad ar 1 ó an t-uasmhéid Is é an focal san fhoclóir 45 8 00:00:32,259 --> 00:00:35,110 carachtair, agus ansin táimid ag dul chun Ní mór carachtar breise amháin don 9 00:00:35,110 --> 00:00:37,070 cúlslais 0. 10 00:00:37,070 --> 00:00:40,870 >> Agus ansin ár tábla hash i ngach Tá buicéad ag dul a stóráil ar 11 00:00:40,870 --> 00:00:42,320 liosta nasctha de nóid. 12 00:00:42,320 --> 00:00:44,420 Ní Táimid ag déanamh líneach deacra anseo. 13 00:00:44,420 --> 00:00:48,430 Agus mar sin d'fhonn a nascadh leis an chéad cheann eile eilimint sa buicéad, ní mór dúinn a 14 00:00:48,430 --> 00:00:51,110 nód struct * chugainn. 15 00:00:51,110 --> 00:00:53,090 Mar sin, go bhfuil an méid Breathnaíonn nód cosúil. 16 00:00:53,090 --> 00:00:56,180 Anois, tá anseo an dearbhú ar ár tábla hash. 17 00:00:56,180 --> 00:01:01,910 Tá sé ag dul a bheith 16,384 buicéid, ach nach líon ábhar i ndáiríre. 18 00:01:01,910 --> 00:01:05,450 Agus ar deireadh, táimid ag dul a bheith acu ar an hashtable_size athróg domhanda, a 19 00:01:05,450 --> 00:01:08,640 Tá dul chun tús a chur amach mar 0, agus tá sé dul súil a choinneáil cé mhéad focail 20 00:01:08,640 --> 00:01:10,080 bhí ár foclóir. 21 00:01:10,080 --> 00:01:10,760 Gach ceart. 22 00:01:10,760 --> 00:01:13,190 >> Mar sin, a ligean ar ghlacadh le breathnú ar ualach. 23 00:01:13,190 --> 00:01:16,390 Mar sin, faoi deara go ualach, tuairisceáin sé bool. 24 00:01:16,390 --> 00:01:20,530 Tá tú ar ais fíor má bhí sé rathúil luchtaithe agus bréagach ar shlí eile. 25 00:01:20,530 --> 00:01:23,990 Agus a thógann sé ruabhric CONST * réalta foclóir, a bhfuil an foclóir 26 00:01:23,990 --> 00:01:25,280 gur mhaith linn a oscailt. 27 00:01:25,280 --> 00:01:27,170 Mar sin, go bhfuil an chéad rud táimid ag dul a dhéanamh. 28 00:01:27,170 --> 00:01:30,420 Táimid ag dul a fopen an foclóir do léamh, agus táimid ag dul a bheith acu 29 00:01:30,420 --> 00:01:34,700 a dhéanamh cinnte go bhfuil d'éirigh sé sin má d'fhill sé NULLComment, ansin ní raibh muid 30 00:01:34,700 --> 00:01:37,440 rathúil an foclóir a oscailt agus ní mór dúinn a thabhairt ar ais bréagach. 31 00:01:37,440 --> 00:01:41,580 >> Ach ag glacadh leis go raibh sé go rathúil oscailte, ansin ba mhaith linn a léamh ar an 32 00:01:41,580 --> 00:01:42,400 foclóir. 33 00:01:42,400 --> 00:01:46,210 Mar sin a choinneáil go dtí go bhfaighidh muid roinnt looping chúis a bhriseadh amach as an 34 00:01:46,210 --> 00:01:47,570 lúb a beidh orainn a fheiceáil. 35 00:01:47,570 --> 00:01:51,780 Mar sin a choinneáil looping, agus anois táimid ag dul a malloc nód amháin. 36 00:01:51,780 --> 00:01:56,800 Agus ar ndóigh, ní mór dúinn a sheiceáil earráid arís mar sin más rud é nach raibh mallocing éireoidh 37 00:01:56,800 --> 00:02:00,660 agus ba mhaith linn a dhíluchtú ar bith nód go bhfuil muid a tharla do malloc roimh, dún an 38 00:02:00,660 --> 00:02:02,590 foclóir agus seol ar ais bréagach. 39 00:02:02,590 --> 00:02:07,440 >> Ach neamhaird a bhfuil, ag glacadh leis againn d'éirigh leis, ansin ba mhaith linn a úsáid fscanf 40 00:02:07,440 --> 00:02:12,400 focal amháin a léamh as ár dictionary isteach inár nód. 41 00:02:12,400 --> 00:02:17,310 Mar sin, cuimhnigh go bhfuil focal iontráil-> Is é an ruabhreac Maolán focal ar fhad méid móide 42 00:02:17,310 --> 00:02:20,300 ceann a táimid ag dul chun stóráil an focal isteach 43 00:02:20,300 --> 00:02:25,280 Mar sin, tá fscanf ag dul a thabhairt ar ais 1 chomh fada mar a bhí sé in ann a léamh go rathúil le 44 00:02:25,280 --> 00:02:26,750 focal as an gcomhad. 45 00:02:26,750 --> 00:02:31,030 >> Má tharlaíonn ceachtar earráid nó a bhaint amach againn an deireadh an chomhaid, ní bheidh sé 46 00:02:31,030 --> 00:02:34,950 ar ais 1 sa chás sin más rud é nach ndéanann sé ar ais 1, táimid ag dul ar deireadh a bhriseadh 47 00:02:34,950 --> 00:02:37,280 amach as an lúb fad. 48 00:02:37,280 --> 00:02:42,770 Mar sin, a fheicimid go bhfuil nuair a bhíonn againn go rathúil Léigh focal isteach 49 00:02:42,770 --> 00:02:48,270 iontráil-> focal, ansin tá muid ag dul a hash an focal sin ag baint úsáide as ár n-fheidhm hash. 50 00:02:48,270 --> 00:02:49,580 A ligean ar ghlacadh le breathnú ar an fheidhm hash. 51 00:02:49,580 --> 00:02:52,430 52 00:02:52,430 --> 00:02:55,610 >> Mar sin, ní gá duit i ndáiríre a thuiscint seo. 53 00:02:55,610 --> 00:02:59,460 Agus i ndáiríre, tharraing muid díreach tar éis seo hash fheidhm seo ón idirlíon. 54 00:02:59,460 --> 00:03:04,010 Is é an rud ach ní mór duit a aithint go nglacann an ruabhric CONST * focal, 55 00:03:04,010 --> 00:03:08,960 mar sin tá sé ag cur ar shraith mar ionchur agus filleadh ar an slánuimhir gan síniú mar aschur. 56 00:03:08,960 --> 00:03:12,360 Mar sin, sin uile feidhm hash é, tá sé Bíonn i ionchur, tugann sé tú 57 00:03:12,360 --> 00:03:14,490 innéacs isteach sa tábla hash. 58 00:03:14,490 --> 00:03:18,530 Fógra go bhfuil muid ag modding ag NUM_BUCKETS mar sin an luach hash ar ais 59 00:03:18,530 --> 00:03:21,730 i ndáiríre innéacs isteach sa tábla hash agus ní dhéanann innéacs thar an 60 00:03:21,730 --> 00:03:24,320 theorainn an eagar. 61 00:03:24,320 --> 00:03:27,855 >> Mar sin, ós rud é go feidhm hash, táimid ag dul a hash an focal a léamh againn 62 00:03:27,855 --> 00:03:31,700 as an bhfoclóir, agus ansin táimid ag dul úsáid a bhaint as go bhfuil a chur isteach ar an 63 00:03:31,700 --> 00:03:33,750 iontráil isteach sa tábla hash. 64 00:03:33,750 --> 00:03:38,830 Anois, tá hash hashtable reatha liosta nasctha sa tábla hash, agus 65 00:03:38,830 --> 00:03:41,410 tá sé an-is féidir go díreach NULLComment. 66 00:03:41,410 --> 00:03:45,640 Ba mhaith linn a chur isteach ar ár iontrála ag na tús an liosta seo nasctha, agus mar sin 67 00:03:45,640 --> 00:03:48,910 táimid ag dul go bhfuil ár n-iontráil reatha pointe cad é an tábla hash láthair 68 00:03:48,910 --> 00:03:54,030 pointí a agus ansin táimid ag dul a stóráil sa tábla hash ag an hash 69 00:03:54,030 --> 00:03:55,350 an iontráil reatha. 70 00:03:55,350 --> 00:03:59,320 >> Mar sin, an dá líne isteach go rathúil an iontráil ag tús na 71 00:03:59,320 --> 00:04:02,270 liosta nasctha ag an innéacs sa tábla hash. 72 00:04:02,270 --> 00:04:04,900 Nuair a bhíonn muid ag déanamh leis sin, tá a fhios againn go raibh muid focal eile sa 73 00:04:04,900 --> 00:04:07,800 foclóir agus táimid incrimint arís. 74 00:04:07,800 --> 00:04:13,960 Mar sin, a choinneáil orainn é sin a dhéanamh go dtí go fscanf tuairisceáin ar deireadh rud éigin nach 1 ag 75 00:04:13,960 --> 00:04:18,560 a pointe cuimhnigh gur gá dúinn a isteach saor in aisce, mar sin suas anseo, malloced againn 76 00:04:18,560 --> 00:04:21,329 iontráil agus rinneamar iarracht rud éigin a léamh as an bhfoclóir. 77 00:04:21,329 --> 00:04:24,110 Agus ní raibh muid ag léamh go rathúil rud éigin as an foclóir a 78 00:04:24,110 --> 00:04:27,440 cás is gá dúinn saor in aisce leis an iontráil go ndéanaimid riamh a chur i ndáiríre isteach sa tábla hash 79 00:04:27,440 --> 00:04:29,110 agus ar deireadh a bhriseadh. 80 00:04:29,110 --> 00:04:32,750 >> Nuair a briseadh muid amach, is gá dúinn a fheiceáil, go maith, raibh muid briseadh amach toisc go 81 00:04:32,750 --> 00:04:35,840 ndearnadh earráid ag léamh as an gcomhad, nó raibh muid briseadh amach mar gheall ar shroich muid 82 00:04:35,840 --> 00:04:37,120 an deireadh an chomhaid? 83 00:04:37,120 --> 00:04:40,150 Má bhí earráid, ansin ba mhaith linn a tuairisceán bréige toisc nach raibh ualach 84 00:04:40,150 --> 00:04:43,260 iarracht, agus sa phróiseas, ba mhaith linn a Díluchtaigh na focail go léir a léamh againn 85 00:04:43,260 --> 00:04:45,670 i agus an comhad a dhúnadh foclóir. 86 00:04:45,670 --> 00:04:48,740 Ag glacadh leis raibh muid éireoidh, ansin dúinn ach gá fós a dhúnadh ar an bhfoclóir 87 00:04:48,740 --> 00:04:51,970 comhad, agus ar deireadh ar ais fíor ó tá muid luchtaithe go rathúil ar an 88 00:04:51,970 --> 00:04:53,040 foclóir. 89 00:04:53,040 --> 00:04:54,420 Agus sin é do ualach. 90 00:04:54,420 --> 00:04:59,020 >> Mar sin a sheiceáil anois, tugtar tábla hash luchtaithe, Tá dul chun breathnú cosúil le seo. 91 00:04:59,020 --> 00:05:02,690 Mar sin a sheiceáil, tuairisceáin sé bool, a ag dul a chur in iúl cé acu an 92 00:05:02,690 --> 00:05:07,530 ritheadh-i ruabhric * focal, cibé acu an Is ritheadh-i dteaghrán i ár foclóir. 93 00:05:07,530 --> 00:05:10,530 Mar sin, má tá sé sa bhfoclóir, má tá sé in ár tábla hash, beidh muid ar ais 94 00:05:10,530 --> 00:05:13,380 fíor, agus más rud é nach bhfuil sé, Beidh muid ar ais bréagach. 95 00:05:13,380 --> 00:05:17,770 Mar gheall ar an focal ritheadh-i, tá muid ag dul go dtí an focal hash. 96 00:05:17,770 --> 00:05:22,020 >> Anois, tá an rud is tábhachtaí a aithint gur i ualach, bhí a fhios againn go léir 97 00:05:22,020 --> 00:05:25,820 Bhí na focail ag dul a bheith cás níos ísle, ach anseo, nach bhfuil muid chomh cinnte. 98 00:05:25,820 --> 00:05:29,510 Má chur orainn le breathnú ar ár n-fheidhm hash, ár n-fheidhm hash iarbhír 99 00:05:29,510 --> 00:05:32,700 Tá gach carachtar lowercasing an focal. 100 00:05:32,700 --> 00:05:37,580 Mar sin, beag beann ar an caipitlithe de focal, is é ár fheidhm hash ag dul go dtí 101 00:05:37,580 --> 00:05:42,270 ar ais an t-innéacs céanna cibé an Is caipitlithe mar a bheadh ​​sé a bheith 102 00:05:42,270 --> 00:05:45,280 thoghfar do litreacha beaga go hiomlán leagan den fhocal. 103 00:05:45,280 --> 00:05:45,950 Gach ceart. 104 00:05:45,950 --> 00:05:47,410 >> Mar sin, go bhfuil ár innéacs. 105 00:05:47,410 --> 00:05:49,790 Tá sé an tábla hash don fhocal seo. 106 00:05:49,790 --> 00:05:52,940 Anois, tá sé seo le haghaidh lúb leanúnach go dtí os cionn an liosta nasctha 107 00:05:52,940 --> 00:05:55,000 go raibh ag an innéacs. 108 00:05:55,000 --> 00:05:59,630 Mar sin, faoi deara againn ag initializing iontráil a chur in iúl leis an innéacs. 109 00:05:59,630 --> 00:06:03,480 Táimid ag dul chun leanúint ar aghaidh agus a dhéanann iontráil Ní NULLComment comhionann, agus cuimhnigh go 110 00:06:03,480 --> 00:06:08,350 cothrom le dáta an pointeoir i ár liosta nasctha is ionann iontráil isteach-> seo chugainn, ionas go mbeidh 111 00:06:08,350 --> 00:06:13,840 ár pointe iontrála reatha go dtí an chéad mhír eile ar an liosta nasctha. 112 00:06:13,840 --> 00:06:14,400 Gach ceart. 113 00:06:14,400 --> 00:06:19,150 >> Mar sin, le haghaidh gach iontrála ar an liosta nasctha, táimid ag dul strcasecmp a úsáid. 114 00:06:19,150 --> 00:06:23,780 Níl sé strcmp mar aon uair arís, táimid ag ag iarraidh a dhéanamh rudaí cás neamh-mhothálach. 115 00:06:23,780 --> 00:06:28,830 Mar sin, úsáidimid strcasecmp an focal a chur i gcomparáid gur ritheadh ​​an fheidhm seo 116 00:06:28,830 --> 00:06:31,860 i gcoinne an focal go Is san iontráil seo. 117 00:06:31,860 --> 00:06:35,570 Má tuairisceáin sé 0, ciallaíonn sé go raibh ar chluiche, agus sa chás sin ba mhaith linn a 118 00:06:35,570 --> 00:06:36,630 ar ais fíor. 119 00:06:36,630 --> 00:06:39,590 Fuair ​​muid go rathúil leis an focal i ár tábla hash. 120 00:06:39,590 --> 00:06:43,040 >> Más rud é nach raibh aon rud oiriúnach, ansin tá muid ag dul go dtí lúb arís agus féach ar an 121 00:06:43,040 --> 00:06:43,990 iontráil seo chugainn. 122 00:06:43,990 --> 00:06:47,640 Agus beidh muid ag leanúint ar aghaidh looping cé go Tá iontrálacha sa liosta seo nasctha. 123 00:06:47,640 --> 00:06:50,160 Cad a tharlaíonn má bhriseann muid as seo lúb? 124 00:06:50,160 --> 00:06:55,110 Ciallaíonn sé sin nach raibh againn teacht ar iontráil a mheaitseáil focal seo, agus sa chás sin 125 00:06:55,110 --> 00:07:00,220 táimid ar ais bréagach a chur in iúl go bhfuil ár Ní raibh tábla hais bhfuil an focal seo. 126 00:07:00,220 --> 00:07:01,910 Agus sin é do sheiceáil. 127 00:07:01,910 --> 00:07:02,540 Gach ceart. 128 00:07:02,540 --> 00:07:04,790 >> Mar sin, a ligean ar ghlacadh le breathnú ar an méid. 129 00:07:04,790 --> 00:07:09,280 Anois, tá méid dul a bheith simplí go leor cuimhnigh ós rud é i ualach, do gach focal 130 00:07:09,280 --> 00:07:12,880 fuair muid incrimintithe muid domhanda hashtable_size athraitheach. 131 00:07:12,880 --> 00:07:15,830 Mar sin, is é an fheidhm méid ach ag dul a thabhairt ar ais go domhanda 132 00:07:15,830 --> 00:07:18,150 athróg, agus go bhfuil sé. 133 00:07:18,150 --> 00:07:22,300 >> Anois, ar deireadh, ní mór dúinn a dhíluchtú foclóir nuair a tá gach rud a dhéanamh. 134 00:07:22,300 --> 00:07:25,340 Mar sin, conas a bhfuil muid ag dul a dhéanamh sin? 135 00:07:25,340 --> 00:07:30,440 Ceart anseo, tá muid looping thar gach buicéid ar ár tábla hash. 136 00:07:30,440 --> 00:07:33,240 Mar sin, tá NUM_BUCKETS buicéid. 137 00:07:33,240 --> 00:07:37,490 Agus do gach liosta nasctha in ár hash tábla, táimid ag dul chun lúb thar an 138 00:07:37,490 --> 00:07:41,070 go hiomlán ar an liosta nasctha freeing gach gné. 139 00:07:41,070 --> 00:07:46,070 Anois, ní mór dúinn a bheith cúramach, mar sin anseo táimid ag Tá athróg sealadach go 140 00:07:46,070 --> 00:07:49,740 stóráil an pointeoir chuig an chéad cheann eile eilimint sa liosta nasctha. 141 00:07:49,740 --> 00:07:52,140 Agus ansin táimid ag dul go dtí saor in aisce an eilimint atá ann faoi láthair. 142 00:07:52,140 --> 00:07:55,990 >> Ní mór dúinn a bheith cinnte a dhéanaimid é seo ós rud é againn Ní féidir ach saor in aisce leis an eilimint atá ann faoi láthair 143 00:07:55,990 --> 00:07:59,260 agus ansin déan iarracht rochtain a fháil ar an pointeoir eile ós rud é aon uair amháin freed muid é an 144 00:07:59,260 --> 00:08:00,870 thiocfaidh chun bheith neamhbhailí cuimhne. 145 00:08:00,870 --> 00:08:04,990 Mar sin, ní mór dúinn a choinneáil timpeall ar pointeoir go an chéad bhall eile, ansin is féidir linn a saor in aisce ar an 146 00:08:04,990 --> 00:08:08,360 eilimint atá ann faoi láthair, agus ansin is féidir linn a thabhairt cothrom le dáta ár n-eilimint ann faoi láthair a chur in iúl do 147 00:08:08,360 --> 00:08:09,590 an chéad bhall eile. 148 00:08:09,590 --> 00:08:12,770 >> Beidh muid lúb cé go bhfuil gnéithe sa liosta seo nasctha. 149 00:08:12,770 --> 00:08:16,450 Beidh muid é sin a dhéanamh do gach liosta nasctha i an tábla hais, agus nuair a táimid ag déanamh 150 00:08:16,450 --> 00:08:20,180 leis sin, tá muid á díluchtú go hiomlán an tábla hais, agus táimid ag déanamh. 151 00:08:20,180 --> 00:08:24,050 Mar sin, tá sé dodhéanta do unloads a riamh tuairisceán bréige, agus nuair a táimid ag déanamh, táimid ag 152 00:08:24,050 --> 00:08:25,320 ach ar ais fíor. 153 00:08:25,320 --> 00:08:27,563