1
00:00:00,000 --> 00:00:11,856

2
00:00:11,856 --> 00:00:13,050
>> ROBボーデン：こんにちは。

3
00:00:13,050 --> 00:00:16,210
私はロブだし、レッツハッシュ
このソリューションが不足しています。

4
00:00:16,210 --> 00:00:20,070
そこでここでは、実装するつもりだ
一般的なハッシュテーブル。

5
00:00:20,070 --> 00:00:24,090
私たちは、ハッシュの構造ノードが分かり
テーブルは次のようにしようとしている。

6
00:00:24,090 --> 00:00:28,710
だから、char型の言葉を持っているために起こっている
サイズ長さプラス1の配列。

7
00:00:28,710 --> 00:00:32,259
最大以来1を忘れてはいけない
辞書内の単語は45です

8
00:00:32,259 --> 00:00:35,110
文字、その後、我々はするつもりだ
のための1余分な文字を必要とする

9
00:00:35,110 --> 00:00:37,070
バックスラッシュ0。

10
00:00:37,070 --> 00:00:40,870
>> して、それぞれに私たちのハッシュテーブル
バケットは、保存しようとしている

11
00:00:40,870 --> 00:00:42,320
ノードのリンクリスト。

12
00:00:42,320 --> 00:00:44,420
ここでは、プロービング線形をしていない。

13
00:00:44,420 --> 00:00:48,430
だから次のリンクするために
バケット内の要素、私たちが必要とする

14
00:00:48,430 --> 00:00:51,110
次の構造体ノード*。

15
00:00:51,110 --> 00:00:53,090
だから、ノードは次のようになります。

16
00:00:53,090 --> 00:00:56,180
今、ここに宣言です
当社のハッシュテーブルの。

17
00:00:56,180 --> 00:01:01,910
これは、16,384バケツを持っているつもりが、だ
その数は本当に重要ではありません。

18
00:01:01,910 --> 00:01:05,450
そして最後に、我々は持っているつもりです
グローバル変数hashtable_size、その

19
00:01:05,450 --> 00:01:08,640
0としてオフを開始する予定、それはださ
どのように多くの単語を追跡しようとして

20
00:01:08,640 --> 00:01:10,080
私たちの辞書にあった。

21
00:01:10,080 --> 00:01:10,760
わかりました。

22
00:01:10,760 --> 00:01:13,190
>> それでは、負荷を見てみましょう。

23
00:01:13,190 --> 00:01:16,390
だから負荷に気づく、
それはBOOLを返します。

24
00:01:16,390 --> 00:01:20,530
それが成功した場合はtrueを返す
それ以外の場合はロードされ、falseを返します。

25
00:01:20,530 --> 00:01:23,990
そして、それはcon​​stのchar *のスターを取る
辞書で辞書、

26
00:01:23,990 --> 00:01:25,280
我々はオープンしたいという。

27
00:01:25,280 --> 00:01:27,170
だから、最初のことだ
私たちは、やろうとしている。

28
00:01:27,170 --> 00:01:30,420
私たちは辞書をfopenのつもりだ
読んで、私たちは持っているつもりです

29
00:01:30,420 --> 00:01:34,700
それがそうであれば成功したことを確認します
それはnullを返し、その後、我々はしませんでした

30
00:01:34,700 --> 00:01:37,440
成功した辞書を開く
そして我々はfalseを返す必要があります。

31
00:01:37,440 --> 00:01:41,580
>> しかし、それは成功しなかったと仮定して
オープン、その後、我々は読んでもらいたい

32
00:01:41,580 --> 00:01:42,400
辞書。

33
00:01:42,400 --> 00:01:46,210
我々はいくつかを見つけるまでそのループを保つ
このから抜け出すべき理由

34
00:01:46,210 --> 00:01:47,570
私達が表示されますループ。

35
00:01:47,570 --> 00:01:51,780
そうルーピング保ち、そして今、我々は行っている
単一のノードをのmallocする。

36
00:01:51,780 --> 00:01:56,800
そしてもちろん、我々はチェックをエラーする必要があります
再びmallocingは成功しませんでしたので、もし

37
00:01:56,800 --> 00:02:00,660
そして我々は、我々のいずれかのノードをアンロードする
前のmallocに起こった、閉じ

38
00:02:00,660 --> 00:02:02,590
辞書とfalseを返します。

39
00:02:02,590 --> 00:02:07,440
>> しかし、我々が想定していることを無視し
成功し、その後、我々は関数fscanf利用したい

40
00:02:07,440 --> 00:02:12,400
から単一の単語を読むために私たちの
私たちのノード辞書。

41
00:02:12,400 --> 00:02:17,310
だから、エントリ - >単語が文字であることを忘れないでください
ワードサイズの長さの緩衝液+

42
00:02:17,310 --> 00:02:20,300
我々はするつもりだ1
インチの単語を保存

43
00:02:20,300 --> 00:02:25,280
だから、関数fscanfは限り1を返すために起こっている
それが成功して読み取ることができたとして

44
00:02:25,280 --> 00:02:26,750
ファイルから単語。

45
00:02:26,750 --> 00:02:31,030
>> エラーのいずれかが起こるか、我々が到達した場合
ファイルの最後には、それはないでしょう

46
00:02:31,030 --> 00:02:34,950
そうでない場合は、ケース内の1を返す
1を返す、我々は最終的に破るつもりだ

47
00:02:34,950 --> 00:02:37,280
このwhileループの外。

48
00:02:37,280 --> 00:02:42,770
だから我々は、かつて我々が成功していることがわかります
に単語を読む

49
00:02:42,770 --> 00:02:48,270
エントリー>言葉は、我々は、ハッシュするつもりだ
我々のハッシュ関数を用いてその単語。

50
00:02:48,270 --> 00:02:49,580
それでは見てみましょう
ハッシュ関数。

51
00:02:49,580 --> 00:02:52,430

52
00:02:52,430 --> 00:02:55,610
>> だから、本当に必要はありません。
これを理解する。

53
00:02:55,610 --> 00:02:59,460
そして実際に、私たちは、これを引っ張っ
インターネットから関数をハッシュ。

54
00:02:59,460 --> 00:03:04,010
あなたが認識する必要がある唯一のものです
これはcon​​stのchar *文字の単語を取ることを、

55
00:03:04,010 --> 00:03:08,960
そのためには、入力として文字列を取っているし、
出力として符号なし整数を返す。

56
00:03:08,960 --> 00:03:12,360
だから、すべてのハッシュ関数ですそれは、そうです
入力を取り込み、それはあなたに与えます

57
00:03:12,360 --> 00:03:14,490
ハッシュテーブルへのインデックス。

58
00:03:14,490 --> 00:03:18,530
我々はNUM_BUCKETSで改造していることに注意してください
そのハッシュ値を返す

59
00:03:18,530 --> 00:03:21,730
実際にハッシュテーブルへのインデックスです
以降もインデックスされない

60
00:03:21,730 --> 00:03:24,320
配列の境界。

61
00:03:24,320 --> 00:03:27,855
>> だから、ハッシュ関数、我々が行っていることを考えると
我々は読んで単語をハッシュする

62
00:03:27,855 --> 00:03:31,700
辞書から、その後、我々は行っている
それを使用するためには、挿入する必要が

63
00:03:31,700 --> 00:03:33,750
ハッシュテーブルにエントリ。

64
00:03:33,750 --> 00:03:38,830
今、ハッシュテーブルハッシュは、現在ある
ハッシュテーブルにリストを連結し、かつ

65
00:03:38,830 --> 00:03:41,410
それだけでnullであることは非常に可能性があります。

66
00:03:41,410 --> 00:03:45,640
我々は、我々のエントリを挿入したい
このリンクリストの先頭、など

67
00:03:45,640 --> 00:03:48,910
我々は我々の現在のエントリを持っているつもりです
現在、どのようなハッシュテーブルを指す

68
00:03:48,910 --> 00:03:54,030
ポイントにして、私たちは保存するつもりだ
ハッシュのハッシュ·テーブル内の

69
00:03:54,030 --> 00:03:55,350
現在のエントリ。

70
00:03:55,350 --> 00:03:59,320
>> だから、この2行は正常に挿入
の先頭にエントリー

71
00:03:59,320 --> 00:04:02,270
そのインデックスのリンクリスト
ハッシュテーブルに。

72
00:04:02,270 --> 00:04:04,900
我々はそれに終わったら、知っている
我々は、別の単語を見つけた

73
00:04:04,900 --> 00:04:07,800
辞書と我々は再び増加します。

74
00:04:07,800 --> 00:04:13,960
だから我々はやり続けることはfscanfまで、
最終的に非何か1を返します。

75
00:04:13,960 --> 00:04:18,560
その時点では、我々がする必要があることを覚えておいて
入場無料なので、ここまで、我々はmallocさ

76
00:04:18,560 --> 00:04:21,329
エントリーと我々は何かを読み取ろうとしました
辞書から。

77
00:04:21,329 --> 00:04:24,110
そして、我々は正常に読み込まれませんでした
辞書から何か

78
00:04:24,110 --> 00:04:27,440
我々は我々のエントリを解放する必要がある場合
実際にハッシュテーブルに入れたことがない

79
00:04:27,440 --> 00:04:29,110
そして最終的に分割します。

80
00:04:29,110 --> 00:04:32,750
>> 我々は抜け出すと、我々は、よく、見る必要がある
我々は、理由があっ抜け出すんでした

81
00:04:32,750 --> 00:04:35,840
ファイルからの読み取りエラーが発生したか、
我々は達したので、私たちは抜け出すんでした

82
00:04:35,840 --> 00:04:37,120
ファイルの終わり？

83
00:04:37,120 --> 00:04:40,150
エラーがあったなら、私たちがしたい
負荷がなかったため、falseを返す

84
00:04:40,150 --> 00:04:43,260
成功し、その過程で、私たちがしたい
我々は読んですべての単語をアンロード

85
00:04:43,260 --> 00:04:45,670
と辞書ファイルを閉じます。

86
00:04:45,670 --> 00:04:48,740
我々は成功しなかったと仮定すると、我々だけで
それでも辞書を閉じる必要が

87
00:04:48,740 --> 00:04:51,970
ファイル、そして最後には、以来、trueを返す
我々は正常にロードされました

88
00:04:51,970 --> 00:04:53,040
辞書。

89
00:04:53,040 --> 00:04:54,420
そして、それは、負荷のためにそれだ。

90
00:04:54,420 --> 00:04:59,020
>> だから今、ロードされたハッシュテーブル与えられ、確認してください、
このように起こっている。

91
00:04:59,020 --> 00:05:02,690
そう、それはBOOLを返す、チェックしている
かどうかを示すために起こっている

92
00:05:02,690 --> 00:05:07,530
渡されたchar *文字の単語、かどうか
渡された文字列は、私たちの辞書にある。

93
00:05:07,530 --> 00:05:10,530
だからである場合には、辞書にある場合
当社のハッシュテーブルに、我々は戻ります

94
00:05:10,530 --> 00:05:13,380
真、そうでないなら、
我々はfalseを返します。

95
00:05:13,380 --> 00:05:17,770
これは、渡された単語を考えると、我々はしている
単語をハッシュする予定。

96
00:05:17,770 --> 00:05:22,020
>> 今、認識することが重要なことは
ロードでは、我々は知っていたことをすべてのこと

97
00:05:22,020 --> 00:05:25,820
言葉は小文字であることを行った、
しかしここでは、そのようにわからない。

98
00:05:25,820 --> 00:05:29,510
我々はハッシュ関数を見てみると、
実際に私たちのハッシュ関数

99
00:05:29,510 --> 00:05:32,700
各文字を小文字化されている
言葉の。

100
00:05:32,700 --> 00:05:37,580
だから関係なく、総額
言葉、私たちのハッシュ関数は、しようとしている

101
00:05:37,580 --> 00:05:42,270
何のために同じインデックスを返す
時価総額は、それがなければならないようです。

102
00:05:42,270 --> 00:05:45,280
完全に小文字に返さ
Wordのバージョン。

103
00:05:45,280 --> 00:05:45,950
わかりました。

104
00:05:45,950 --> 00:05:47,410
>> だから、Googleのインデックスです。

105
00:05:47,410 --> 00:05:49,790
それは、この単語のためのハッシュテーブルです。

106
00:05:49,790 --> 00:05:52,940
今、forループはこれが起こっている
リンクリストの上へ

107
00:05:52,940 --> 00:05:55,000
つまり、そのインデックスにあった。

108
00:05:55,000 --> 00:05:59,630
だから我々は、エントリを初期化しているに気づく
そのインデックスを指すように設定します。

109
00:05:59,630 --> 00:06:03,480
私たちは、エントリがない間継続するつもりだ
等しくないNULL、と覚えている

110
00:06:03,480 --> 00:06:08,350
私たちのリンクリストポインタを更新
エントリは次のエントリ->に等しいので、持っている

111
00:06:08,350 --> 00:06:13,840
に私たちの現在のエントリ·ポイント
リンクリストの次のアイテム。

112
00:06:13,840 --> 00:06:14,400
わかりました。

113
00:06:14,400 --> 00:06:19,150
>> だから、リンクリスト内のエントリごとに、
私たちは、strcasecmpを使用するつもりだ。

114
00:06:19,150 --> 00:06:23,780
それははstrcmpはないので、再び、我々
区別せず物事のケースをやってみたい。

115
00:06:23,780 --> 00:06:28,830
だから我々は言葉を比較するためにstrcasecmpを使用
それは、この関数に渡されました

116
00:06:28,830 --> 00:06:31,860
単語に対して、その
このエントリにあります。

117
00:06:31,860 --> 00:06:35,570
それが0を返した場合、それがあったことを意味
我々がしたい、その場合に一致すると、

118
00:06:35,570 --> 00:06:36,630
trueを返します。

119
00:06:36,630 --> 00:06:39,590
我々が正常に見つかった
当社のハッシュテーブル内の単語。

120
00:06:39,590 --> 00:06:43,040
>> 一致するものがなかった場合、我々はしている
再びループに行くと見て

121
00:06:43,040 --> 00:06:43,990
次のエントリー。

122
00:06:43,990 --> 00:06:47,640
そして、我々はしばらくの間そこにループし続けます
このリンクリスト内のエントリです。

123
00:06:47,640 --> 00:06:50,160
私たちは壊れた場合はどうなります
forループこれのうち？

124
00:06:50,160 --> 00:06:55,110
それは我々がそのエントリを見つけられませんでした意味
その場合には、この言葉を一致

125
00:06:55,110 --> 00:07:00,220
私たちは、それを示すためにfalseを返す
ハッシュテーブルには、この単語が含まれていませんでした。

126
00:07:00,220 --> 00:07:01,910
そして、それはチェックのためにそれだ。

127
00:07:01,910 --> 00:07:02,540
わかりました。

128
00:07:02,540 --> 00:07:04,790
>> それでは、サイズを見てみましょう。

129
00:07:04,790 --> 00:07:09,280
今、サイズが非常に簡単になるだろう
以来、単語ごとに、負荷に覚えている

130
00:07:09,280 --> 00:07:12,880
我々はグローバルに増分発見
変数hashtable_size。

131
00:07:12,880 --> 00:07:15,830
だから、size関数はただです
そのグローバルを返しに行く

132
00:07:15,830 --> 00:07:18,150
変数で、それはそれだ。

133
00:07:18,150 --> 00:07:22,300
>> ついに、我々はアンロードする必要があります
辞書すべてが済んだら。

134
00:07:22,300 --> 00:07:25,340
では、どのようにそれをするつもりですか？

135
00:07:25,340 --> 00:07:30,440
右ここでは、すべての上にループしています
当社のハッシュテーブルのバケット。

136
00:07:30,440 --> 00:07:33,240
そうNUM_BUCKETSバケットがあります。

137
00:07:33,240 --> 00:07:37,490
そして、我々のハッシュ内の各リンクリストのための
テーブル、我々をループするつもりだ

138
00:07:37,490 --> 00:07:41,070
リンクリストの全体
各要素を解放する。

139
00:07:41,070 --> 00:07:46,070
今、我々は注意する必要があるので、ここでは
の一時変数を持っている

140
00:07:46,070 --> 00:07:49,740
次のポインタを格納
リンクされたリスト内の要素。

141
00:07:49,740 --> 00:07:52,140
そして、我々は自由になるだろう
現在の要素。

142
00:07:52,140 --> 00:07:55,990
>> 我々は、我々以来、これを行うことを確認する必要があり
ただ、現在の要素を解放することはできません

143
00:07:55,990 --> 00:07:59,260
して、次のポインタにアクセスしよう
以来、一度我々はそれを解放

144
00:07:59,260 --> 00:08:00,870
メモリは無効になります。

145
00:08:00,870 --> 00:08:04,990
だから我々は体へのポインタの周りに維持する必要があります
次の要素は、その後、我々は解放することができます

146
00:08:04,990 --> 00:08:08,360
現在の要素、そして、我々は更新することができます
を指すように私たちの現在の要素

147
00:08:08,360 --> 00:08:09,590
次の要素。

148
00:08:09,590 --> 00:08:12,770
>> 要素が存在している間、我々はよループ
このリンクリスト内。

149
00:08:12,770 --> 00:08:16,450
我々は、すべてのリンクされたリストのことをやる
ハッシュテーブル、そして我々が終わっ回

150
00:08:16,450 --> 00:08:20,180
それにより、我々は完全にアンロードされました
ハッシュテーブル、そして我々は完了です。

151
00:08:20,180 --> 00:08:24,050
だから、アンロードするために、これまでは不可能だ
falseを返し、そして我々が完了したら、我々は

152
00:08:24,050 --> 00:08:25,320
ただtrueを返す。

153
00:08:25,320 --> 00:08:27,563