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
插入可以開始
趨向THETA 1。

31
00:01:23,070 --> 00:01:26,207
西塔我們還沒有真正討論過，
但THETA只是平均情況下，

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
的時間變得更接近
THETA的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
我們通常所說的哈希碼，好不好？

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
和因此數據被處理
它吐出一個數字，好不好？

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
並且能夠找到John
立即在我們的數據結構。

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
我前面寫了這一個。

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
好像我們在聲明一個變量
稱為sum並將其設置等於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]的概括，然後再在
到頭來會返回一個總和模

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
>> 好讓我們重溫這
哈希表一秒鐘。

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
通過散列函數數據
林戈也產生了哈希碼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
函數產生相同的哈希碼。

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
而對付它的方法之一是
做一些所謂的線性探測。

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
確定好我們知道，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
是啊，和8的接近7，因此，如果
我們要開始尋找我們

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
>> 現在，我們哈希Maggie和
返回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的THETA，即平均
案件是恆定的時間，

246
00:11:52,960 --> 00:11:56,560
開始變得有點緩慢 - 
開始傾向於多一點

247
00:11:56,560 --> 00:11:58,050
對n個THETA。

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
如果我們嘗試添加一個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
但是，如果不是有一個鏈接
列表，查找會為O n個，

293
00:14:15,610 --> 00:14:19,590
我們現在有10鍊錶，
或1000鍊錶，

294
00:14:19,590 --> 00:14:24,120
現在它除以10，O n的，
或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倍，
或快1000倍，

300
00:14:36,610 --> 00:14:41,570
因為我們分配一個長
鏈跨越1000小型連鎖店。

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
>> 這是對平均
是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
>> 而現在它是空。

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
當我們哈希喬伊，我們得到了哈希碼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
我們可以這樣做一個更多的時間，我們
可以散列Rachel和獲得哈希碼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
現在，我們可以存儲兩個
與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