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
そして貸すのその種
ハッシュテーブルのアイデア。

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
我々は通常、[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
私たちは、上の延期ます
今のリンクリスト要素

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
生成されたハッシュコードは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
ハッシュ関数は常に私たちに
同じハッシュコードを出します。

126
00:05:50,040 --> 00:05:52,870
私はにジョンを渡した場合
ハッシュ関数は、私は4を得ます。

127
00:05:52,870 --> 00:05:56,110
私はそれを行うことができるはず万
時間と私はいつも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
たびにあなたがを介してデータを実行した場合
ハッシュ関数は、ハッシュコード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
私は前にこの1を書きました。

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
>> これは、基本的にちょうど別です
[を実装する方法はありますか？技研？]

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
合計する[j]をはstrstrを加え、その後に
一日の終わりには、和の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
いくつかのハッシュコードを返します
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
次の2つが表示される場合があります。

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
ハッシュ関数を介して、そのデータ
リンゴもハッシュコード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
そして、衝突が発生したときに、2つの
同じハッシュを通るデータの断片

197
00:09:26,460 --> 00:09:29,200
この関数は、同じハッシュコードをもたらします。

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
>> 彼ならば、我々は、しかし、それをどのようにをしますか
ポールは、両方のハッシュコード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
そして、それに対処するための1つの方法はにあります
プロービング線形と呼ばれる何かをします。

206
00:10:01,350 --> 00:10:04,170
>> 我々が持っている場合は、この方法を使用します
衝突は、よく、私たちは何をしていますか？

207
00:10:04,170 --> 00:10:08,580
さて、私たちは、アレイの場所に彼を置くことができません
6、または任意のハッシュコードを生成しました、

208
00:10:08,580 --> 00:10:10,820
ハッシュコードはプラス1で彼を入れてみましょう。

209
00:10:10,820 --> 00:10:13,670
そしてそれは完全レッツだ場合
ハッシュコードプラス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
私たちは、ハッシュを介しバートを実行します
機能、我々はハッシュコード6を得ます。

221
00:10:48,460 --> 00:10:52,100
我々は6を参照して、外観をされ取ります
空、私たちはそこにバートを置くことができます。

222
00:10:52,100 --> 00:10:55,410
>> 今、私たちはリサとそのハッシュ
また、ハッシュコード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は、8が一杯になる、7がいっぱいである、完全です
図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
に並べている2つの要素を持っています
それもやすくなる側

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
そして、我々は、試してみて、11日または12日を追加した場合
私たちはそれらを置く場所がありません。

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
しかし、もし代わりに、1つを有するのリンク
ルックアップは、nのO、になるリスト

293
00:14:15,610 --> 00:14:19,590
我々は今、10リンクリストを持っています、
または千リンクリスト、

294
00:14:19,590 --> 00:14:24,120
今では、10で割ったn個のOです
あるいはnのO 1000で割ったもの。

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回実行するには、
または1000倍速く、

300
00:14:36,610 --> 00:14:41,570
私たちは長いものを配布しているので、
千小さいチェーン全体のチェーン。

301
00:14:41,570 --> 00:14:45,090
だから私たちが持っているたびに検索します
私たちすることができますこれらのチェインのうちの1つを介して

302
00:14:45,090 --> 00:14:50,290
私たちは気にしない999チェーンを無視
そしてちょうどそのいずれかを検索します。

303
00:14:50,290 --> 00:14:53,220
>> これに平均であります
1000倍短いこと。

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
>> そして今は、nullです。

315
00:15:23,830 --> 00:15:26,170
これらの10のポインタのそれぞれはnullです。

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
我々はジョーイをハッシュするとき、我々はハッシュコード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
我々の場合の10分の1サイズになります
単に1つの巨大なようにそれを持っていました

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
そして、我々は、我々がこの1つのより多くの時間を行うことができます
レイチェルをハッシュし、ハッシュコード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
私たちは、ハッシュコード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
私たちは今、2を格納することができます
ハッシュコード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