1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:01,900
[Bermain muzik]

3
00:00:01,900 --> 00:00:05,710

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: Sekarang anda
tahu banyak tentang tatasusunan,

5
00:00:09,150 --> 00:00:11,610
dan anda tahu banyak tentang senarai berkaitan.

6
00:00:11,610 --> 00:00:13,650
Dan kami telah membincangkan
kebaikan dan keburukan, kami telah

7
00:00:13,650 --> 00:00:16,620
dibincangkan itu diikat senarai
boleh mendapatkan lebih besar dan lebih kecil,

8
00:00:16,620 --> 00:00:18,630
tetapi mereka mengambil saiz lebih.

9
00:00:18,630 --> 00:00:22,359
Tatasusunan adalah lebih mudah untuk
digunakan, tetapi ia terbatas dalam sebanyak

10
00:00:22,359 --> 00:00:24,900
kerana kita perlu menetapkan saiz
array pada awal-awal

11
00:00:24,900 --> 00:00:26,910
dan kemudian kita terjebak dengannya.

12
00:00:26,910 --> 00:00:30,470
>> Tetapi itu, kami telah cukup banyak
habis semua topik kami

13
00:00:30,470 --> 00:00:33,040
tentang senarai berkaitan dan array.

14
00:00:33,040 --> 00:00:34,950
Atau adakah kita?

15
00:00:34,950 --> 00:00:37,720
Mungkin kita boleh melakukan sesuatu
lebih kreatif.

16
00:00:37,720 --> 00:00:40,950
Dan yang jenis Bei
idea jadual hash.

17
00:00:40,950 --> 00:00:46,680
>> Jadi dalam jadual hash kita akan cuba
menggabungkan array dengan senarai berpaut.

18
00:00:46,680 --> 00:00:49,520
Kami akan mengambil kelebihan
array, seperti akses rawak,

19
00:00:49,520 --> 00:00:53,510
dapat hanya pergi ke lokasi
elemen 4 atau pelbagai elemen 8

20
00:00:53,510 --> 00:00:55,560
tanpa perlu melelar seluruh.

21
00:00:55,560 --> 00:00:57,260
Itu cukup pantas, bukan?

22
00:00:57,260 --> 00:01:00,714
>> Tetapi kita juga mahu mempunyai data kami
struktur dapat berkembang dan mengecut.

23
00:01:00,714 --> 00:01:02,630
Kita tidak perlu, kita tidak
mahu terhad.

24
00:01:02,630 --> 00:01:04,588
Dan kita mahu dapat
untuk menambah dan menghapuskan perkara-perkara

25
00:01:04,588 --> 00:01:08,430
sangat mudah, yang jika anda masih ingat,
adalah sangat kompleks dengan pelbagai.

26
00:01:08,430 --> 00:01:11,650
Dan kita boleh memanggil ini
perkara yang baru jadual hash.

27
00:01:11,650 --> 00:01:15,190
>> Dan jika dilaksanakan dengan betul,
kita semacam mengambil

28
00:01:15,190 --> 00:01:18,150
kelebihan kedua-dua data
struktur yang telah anda lihat,

29
00:01:18,150 --> 00:01:19,880
tatasusunan dan senarai berkaitan.

30
00:01:19,880 --> 00:01:23,070
Insertion boleh mula
cenderung ke arah theta 1.

31
00:01:23,070 --> 00:01:26,207
Theta kita belum benar-benar dibincangkan,
tetapi theta adalah hanya kes-rata,

32
00:01:26,207 --> 00:01:27,540
apa yang sebenarnya akan berlaku.

33
00:01:27,540 --> 00:01:29,680
Anda tidak sentiasa akan
mempunyai kes yang teruk,

34
00:01:29,680 --> 00:01:32,555
dan anda tidak sentiasa akan mempunyai
senario kes terbaik, jadi apa yang

35
00:01:32,555 --> 00:01:33,900
senario purata?

36
00:01:33,900 --> 00:01:36,500
>> Well yang kemasukan purata
ke dalam jadual hash

37
00:01:36,500 --> 00:01:39,370
boleh mula untuk mendapatkan dekat dengan masa yang berterusan.

38
00:01:39,370 --> 00:01:41,570
Dan penghapusan boleh mendapatkan
dekat dengan masa yang berterusan.

39
00:01:41,570 --> 00:01:44,440
Dan lookup boleh mendapatkan
dekat dengan masa yang berterusan.

40
00:01:44,440 --> 00:01:48,600
That's-- kita tidak mempunyai data
struktur lagi yang boleh berbuat demikian,

41
00:01:48,600 --> 00:01:51,180
dan sebagainya ini sudah kedengaran
seperti satu perkara yang cukup besar.

42
00:01:51,180 --> 00:01:57,010
Kami benar-benar telah mengurangkan
kekurangan masing-masing dengan sendiri.

43
00:01:57,010 --> 00:01:59,160
>> Untuk mendapatkan prestasi ini
menaik taraf walaupun, kita

44
00:01:59,160 --> 00:02:03,580
perlu memikirkan semula bagaimana kita menambah
data ke dalam struktur.

45
00:02:03,580 --> 00:02:07,380
Secara khusus kita mahu
data sendiri untuk memberitahu kami

46
00:02:07,380 --> 00:02:09,725
di mana ia harus pergi dalam struktur.

47
00:02:09,725 --> 00:02:12,850
Dan jika kita kemudian perlu untuk melihat jika ia dalam
struktur, jika kita perlu untuk mencari,

48
00:02:12,850 --> 00:02:16,610
kita mahu melihat data
lagi dan dapat berkesan,

49
00:02:16,610 --> 00:02:18,910
dengan menggunakan data, secara rawak mengaksesnya.

50
00:02:18,910 --> 00:02:20,700
Hanya dengan melihat
data kita perlu ada

51
00:02:20,700 --> 00:02:25,890
idea di mana sebenarnya kami
akan merasa dalam jadual hash.

52
00:02:25,890 --> 00:02:28,770
>> Sekarang Kelemahan hash
meja adalah bahawa mereka benar-benar

53
00:02:28,770 --> 00:02:31,770
cukup buruk di pesanan atau menyusun data.

54
00:02:31,770 --> 00:02:34,970
Dan sebenarnya, jika anda mula
untuk menggunakan mereka untuk memerintahkan atau jenis

55
00:02:34,970 --> 00:02:37,990
data anda kehilangan semua
kelebihan anda sebelum ini

56
00:02:37,990 --> 00:02:40,710
mempunyai dari segi kemasukan dan pemadaman.

57
00:02:40,710 --> 00:02:44,060
Masa itu menjadi lebih dekat dengan
theta n, dan kami telah pada dasarnya

58
00:02:44,060 --> 00:02:45,530
mundur ke dalam senarai berpaut.

59
00:02:45,530 --> 00:02:48,850
Dan dengan itu kita hanya ingin menggunakan hash
jadual jika kita tidak mengambil berat tentang

60
00:02:48,850 --> 00:02:51,490
sama ada data disusun.

61
00:02:51,490 --> 00:02:54,290
Bagi konteks di mana
anda akan menggunakannya dalam CS50

62
00:02:54,290 --> 00:02:58,900
anda mungkin tidak peduli
bahawa data yang disusun.

63
00:02:58,900 --> 00:03:03,170
>> Jadi jadual hash adalah kombinasi
dua keping yang berbeza

64
00:03:03,170 --> 00:03:04,980
yang kita sudah biasa.

65
00:03:04,980 --> 00:03:07,930
Yang pertama adalah fungsi, yang
kita biasanya memanggil fungsi hash.

66
00:03:07,930 --> 00:03:11,760
Dan bahawa fungsi hash akan
kembali beberapa integer bukan negatif, yang

67
00:03:11,760 --> 00:03:14,870
kita biasanya memanggil Kodcincang yang, OK?

68
00:03:14,870 --> 00:03:20,230
Sekeping kedua adalah pelbagai, yang
mampu menyimpan data kita jenis yang

69
00:03:20,230 --> 00:03:22,190
mahu untuk meletakkan ke dalam struktur data.

70
00:03:22,190 --> 00:03:24,310
Kami akan bertahan pada yang
dikaitkan unsur senarai buat masa ini

71
00:03:24,310 --> 00:03:27,810
dan hanya mula dengan asas-asas yang
hash meja untuk mendapatkan kepala anda di sekitarnya,

72
00:03:27,810 --> 00:03:30,210
dan kemudian kita mungkin akan meniup
minda anda sedikit apabila kita

73
00:03:30,210 --> 00:03:32,920
menggabungkan tatasusunan dan senarai pautan bersama-sama.

74
00:03:32,920 --> 00:03:35,590
>> Idea asas walaupun
adalah kita mengambil data.

75
00:03:35,590 --> 00:03:37,860
Kami menjalankan data bahawa melalui
fungsi hash.

76
00:03:37,860 --> 00:03:41,980
Dan supaya data tersebut diproses
dan ia memuntahkannya keluar nombor, OK?

77
00:03:41,980 --> 00:03:44,890
Dan kemudian dengan jumlah itu
kita hanya menyimpan data

78
00:03:44,890 --> 00:03:48,930
kami mahu menyimpan dalam
lokasi di lokasi tersebut.

79
00:03:48,930 --> 00:03:53,990
Jadi, sebagai contoh kita ada mungkin
ini jadual hash rentetan.

80
00:03:53,990 --> 00:03:57,350
Ia mempunyai 10 elemen di dalamnya, supaya
kita boleh memuatkan 10 tali di dalamnya.

81
00:03:57,350 --> 00:03:59,320
>> Katakan kita mahu hash John.

82
00:03:59,320 --> 00:04:02,979
Lalu ia sebagai data yang kami mahu memasukkan
ke dalam jadual hash ini di suatu tempat.

83
00:04:02,979 --> 00:04:03,770
Di mana kita meletakkan ia?

84
00:04:03,770 --> 00:04:05,728
Well biasanya dengan
lokasi setakat ini kita mungkin

85
00:04:05,728 --> 00:04:07,610
akan memasukkannya ke dalam pelbagai lokasi 0.

86
00:04:07,610 --> 00:04:09,960
Tetapi sekarang kita mempunyai fungsi hash baru ini.

87
00:04:09,960 --> 00:04:13,180
>> Dan mari kita mengatakan bahawa kita menjalankan John
melalui fungsi hash ini

88
00:04:13,180 --> 00:04:15,417
dan ia memuntahkannya keluar 4.

89
00:04:15,417 --> 00:04:17,500
Nah itulah di mana kita berada
akan mahu untuk meletakkan John.

90
00:04:17,500 --> 00:04:22,050
Kami mahu meletakkan John di lokasi array
4, kerana jika kita hash John again--

91
00:04:22,050 --> 00:04:23,810
katakan kemudian kami
ingin mencari dan melihat

92
00:04:23,810 --> 00:04:26,960
jika John wujud dalam hash ini
table-- semua yang perlu kita lakukan

93
00:04:26,960 --> 00:04:30,310
dijalankan melalui hash yang sama
fungsi, dapatkan nombor 4,

94
00:04:30,310 --> 00:04:33,929
dan dapat mencari John
serta-merta dalam struktur data kami.

95
00:04:33,929 --> 00:04:34,720
Yang cukup baik.

96
00:04:34,720 --> 00:04:36,928
>> Katakan sekarang kita melakukan ini
lagi, kami mahu hash Paul.

97
00:04:36,928 --> 00:04:39,446
Kami mahu menambah Paul
ke dalam jadual hash ini.

98
00:04:39,446 --> 00:04:42,070
Mari kita mengatakan bahawa kali ini kita menjalankan
Paul melalui fungsi hash,

99
00:04:42,070 --> 00:04:44,600
Kodcincang yang dihasilkan adalah 6.

100
00:04:44,600 --> 00:04:47,340
Sekarang kita boleh meletakkan Paul
di lokasi array 6.

101
00:04:47,340 --> 00:04:50,040
Dan jika kita perlu melihat ke atas sama ada
Paul dalam jadual hash ini,

102
00:04:50,040 --> 00:04:53,900
semua yang perlu kita lakukan adalah menjalankan Paul
melalui fungsi hash lagi

103
00:04:53,900 --> 00:04:55,830
dan kami akan mendapat 6 lagi.

104
00:04:55,830 --> 00:04:57,590
>> Dan kemudian kita hanya melihat
di lokasi lokasi 6.

105
00:04:57,590 --> 00:04:58,910
Paul di sana?

106
00:04:58,910 --> 00:05:00,160
Jika ya, dia dalam jadual hash.

107
00:05:00,160 --> 00:05:01,875
Paul tidak ada?

108
00:05:01,875 --> 00:05:03,000
Dia bukan dalam jadual hash.

109
00:05:03,000 --> 00:05:05,720
Ia agak mudah.

110
00:05:05,720 --> 00:05:07,770
>> Sekarang bagaimana anda menentukan fungsi hash?

111
00:05:07,770 --> 00:05:11,460
Nah ada benar-benar tiada had untuk
beberapa fungsi hash mungkin.

112
00:05:11,460 --> 00:05:14,350
Malah ada beberapa benar-benar,
orang-orang yang benar-benar baik di internet.

113
00:05:14,350 --> 00:05:17,560
Ada beberapa benar-benar,
orang-orang yang benar-benar buruk di internet.

114
00:05:17,560 --> 00:05:21,080
Ia juga agak mudah
menulis satu yang tidak baik.

115
00:05:21,080 --> 00:05:23,760
>> Jadi apa yang membuat sehingga baik yang
fungsi hash, bukan?

116
00:05:23,760 --> 00:05:27,280
Well fungsi hash yang baik perlu
menggunakan hanya data yang dicincang,

117
00:05:27,280 --> 00:05:29,420
dan semua data yang dicincang.

118
00:05:29,420 --> 00:05:32,500
Oleh itu, kita tidak mahu menggunakan sesuatupun
kita tidak menggabungkan apa-apa

119
00:05:32,500 --> 00:05:35,560
lain selain daripada data.

120
00:05:35,560 --> 00:05:37,080
Dan kita mahu menggunakan semua data.

121
00:05:37,080 --> 00:05:39,830
Kita tidak mahu hanya menggunakan sekeping
itu, kita mahu menggunakan semua itu.

122
00:05:39,830 --> 00:05:41,710
Satu fungsi hash perlu
juga menjadi berketentuan.

123
00:05:41,710 --> 00:05:42,550
Apa maksudnya?

124
00:05:42,550 --> 00:05:46,200
Baik ia bermakna bahawa setiap kali kita
lulus bahagian yang sama dalam data

125
00:05:46,200 --> 00:05:50,040
ke dalam fungsi hash kita sentiasa
mendapatkan Kodcincang yang sama keluar.

126
00:05:50,040 --> 00:05:52,870
Jika saya lulus John ke dalam
fungsi hash saya keluar 4.

127
00:05:52,870 --> 00:05:56,110
Saya akan dapat berbuat demikian 10000
kali dan saya akan sentiasa mendapat 4.

128
00:05:56,110 --> 00:06:00,810
Jadi tiada nombor rawak berkesan
boleh terlibat dalam hash kami tables--

129
00:06:00,810 --> 00:06:02,750
dalam fungsi hash kami.

130
00:06:02,750 --> 00:06:05,750
>> Satu fungsi hash juga perlu
seragam mengedarkan data.

131
00:06:05,750 --> 00:06:09,700
Jika setiap kali anda menjalankan data melalui
fungsi hash anda Kodcincang 0,

132
00:06:09,700 --> 00:06:11,200
itu mungkin tidak begitu besar, bukan?

133
00:06:11,200 --> 00:06:14,600
Anda mungkin mahu besar
pelbagai kod hash.

134
00:06:14,600 --> 00:06:17,190
Juga perkara yang boleh merebak
di seluruh meja.

135
00:06:17,190 --> 00:06:23,210
Dan juga ia akan menjadi besar jika benar-benar
data yang sama, seperti John dan Jonathan,

136
00:06:23,210 --> 00:06:26,320
mungkin telah tersebar untuk menimbang
lokasi yang berbeza dalam jadual hash.

137
00:06:26,320 --> 00:06:28,750
Itu akan menjadi satu kelebihan yang bagus.

138
00:06:28,750 --> 00:06:31,250
>> Berikut adalah satu contoh fungsi hash.

139
00:06:31,250 --> 00:06:33,150
Saya menulis satu ini sehingga awal.

140
00:06:33,150 --> 00:06:35,047
Ia bukan satu terutamanya
fungsi hash baik

141
00:06:35,047 --> 00:06:37,380
atas sebab-sebab yang tidak benar-benar
menanggung pergi ke sekarang.

142
00:06:37,380 --> 00:06:41,040
Tetapi adakah anda melihat apa yang berlaku di sini?

143
00:06:41,040 --> 00:06:44,420
Ia seolah-olah seperti kita mengisytiharkan pembolehubah yang
dipanggil jumlah dan menetapkan ia sama dengan 0.

144
00:06:44,420 --> 00:06:50,010
Dan kemudian nampaknya saya melakukan sesuatu
selagi strstr [j] tidak sama

145
00:06:50,010 --> 00:06:52,490
untuk Backslash 0.

146
00:06:52,490 --> 00:06:54,870
Apa yang saya buat di sana?

147
00:06:54,870 --> 00:06:57,440
>> Ini adalah pada dasarnya hanya satu lagi
cara melaksanakan [? Strl?]

148
00:06:57,440 --> 00:06:59,773
dan mengesan apabila anda telah
sampai ke penghujung tali.

149
00:06:59,773 --> 00:07:02,480
Jadi, saya tidak mempunyai untuk benar-benar
hitungkan panjang tali,

150
00:07:02,480 --> 00:07:05,640
Saya hanya menggunakan apabila saya memukul
garis miring 0 watak saya tahu

151
00:07:05,640 --> 00:07:07,185
Saya telah sampai ke penghujung tali.

152
00:07:07,185 --> 00:07:09,560
Dan kemudian saya akan terus
iterating melalui tali itu,

153
00:07:09,560 --> 00:07:15,310
menambah strstr [j] untuk kesimpulan, dan kemudian di
akhirnya akan kembali mod jumlah

154
00:07:15,310 --> 00:07:16,200
HASH_MAX.

155
00:07:16,200 --> 00:07:18,700
>> Pada dasarnya semua hash ini
fungsi yang dilakukan adalah menambah sehingga

156
00:07:18,700 --> 00:07:23,450
semua nilai-nilai ASCII
rentetan saya, dan kemudian ia

157
00:07:23,450 --> 00:07:26,390
kembali beberapa Kodcincang
modded oleh HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Ia mungkin saiz
array saya, bukan?

159
00:07:29,790 --> 00:07:33,160
Saya tidak mahu mendapat hash
Kod jika pelbagai saya adalah saiz 10,

160
00:07:33,160 --> 00:07:35,712
Saya tidak mahu menjadi semakin
Kod hash daripada 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, saya tidak boleh meletakkan sesuatu ke dalam
lokasi-lokasi array,

162
00:07:38,690 --> 00:07:39,790
yang menyalahi undang-undang.

163
00:07:39,790 --> 00:07:42,130
Saya sedang menderita kesalahan segmentasi.

164
00:07:42,130 --> 00:07:45,230
>> Sekarang di sini adalah satu lagi cepat diketepikan.

165
00:07:45,230 --> 00:07:48,470
Secara amnya anda mungkin tidak akan
mahu menulis fungsi hash anda sendiri.

166
00:07:48,470 --> 00:07:50,997
Ia sebenarnya sedikit
satu seni, bukannya sains.

167
00:07:50,997 --> 00:07:52,580
Dan ada banyak yang masuk ke dalam mereka.

168
00:07:52,580 --> 00:07:55,288
Internet, seperti saya katakan, penuh
fungsi hash benar-benar baik,

169
00:07:55,288 --> 00:07:58,470
dan anda perlu menggunakan internet untuk
mencari fungsi hash kerana ia benar-benar

170
00:07:58,470 --> 00:08:03,230
hanya jenis yang tidak perlu
membuang masa untuk membuat anda sendiri.

171
00:08:03,230 --> 00:08:05,490
>> Anda boleh menulis yang mudah
untuk tujuan ujian.

172
00:08:05,490 --> 00:08:08,323
Tetapi apabila anda benar-benar akan
mula hashing data dan menyimpannya

173
00:08:08,323 --> 00:08:10,780
ke dalam jadual hash anda
mungkin akan mahu

174
00:08:10,780 --> 00:08:14,580
untuk menggunakan beberapa fungsi yang telah dijana
untuk anda, yang wujud di internet.

175
00:08:14,580 --> 00:08:17,240
Jika anda hanya pastikan
memetik sumber anda.

176
00:08:17,240 --> 00:08:21,740
Tidak ada sebab untuk
memplagiat apa-apa di sini.

177
00:08:21,740 --> 00:08:25,370
>> Komuniti sains komputer adalah
pasti semakin meningkat, dan benar-benar nilai-nilai

178
00:08:25,370 --> 00:08:28,796
sumber terbuka, dan ia benar-benar penting
memetik sumber anda supaya orang ramai

179
00:08:28,796 --> 00:08:30,670
boleh mendapatkan pengiktirafan untuk
kerja-kerja yang mereka

180
00:08:30,670 --> 00:08:32,312
lakukan untuk memberi manfaat kepada masyarakat.

181
00:08:32,312 --> 00:08:34,020
Jadi sentiasa sure--
dan bukan hanya untuk hash

182
00:08:34,020 --> 00:08:37,270
fungsi, tetapi secara umumnya apabila anda
menggunakan kod dari sumber luar,

183
00:08:37,270 --> 00:08:38,299
sentiasa memetik sumber anda.

184
00:08:38,299 --> 00:08:43,500
Memberi kredit kepada orang yang melakukan
beberapa kerja supaya anda tidak perlu.

185
00:08:43,500 --> 00:08:46,720
>> OK jadi mari kita melihat semula ini
jadual hash untuk kali kedua.

186
00:08:46,720 --> 00:08:48,780
Ini adalah di mana kita meninggalkan
kira selepas kita dimasukkan

187
00:08:48,780 --> 00:08:53,300
Yohanes dan Paulus ke dalam jadual hash ini.

188
00:08:53,300 --> 00:08:55,180
Adakah anda melihat masalah di sini?

189
00:08:55,180 --> 00:08:58,410
Anda mungkin melihat dua.

190
00:08:58,410 --> 00:09:02,240
Tetapi khususnya, adakah anda
melihat masalah ini boleh terjadi?

191
00:09:02,240 --> 00:09:06,770
>> Bagaimana jika saya hash Ringo, dan ia
Ternyata selepas pemprosesan

192
00:09:06,770 --> 00:09:14,000
data yang melalui fungsi hash
Ringo juga menjana Kodcincang 6.

193
00:09:14,000 --> 00:09:16,810
Saya telah mendapat data pada
lokasi mudah hashcode-- 6.

194
00:09:16,810 --> 00:09:22,000
Oleh itu, ia mungkin akan menjadi sedikit
satu masalah bagi saya sekarang, bukan?

195
00:09:22,000 --> 00:09:23,060
>> Kami memanggil ini perlanggaran.

196
00:09:23,060 --> 00:09:26,460
Dan perlanggaran itu berlaku apabila dua
bahagian data dijalankan melalui hash yang sama

197
00:09:26,460 --> 00:09:29,200
fungsi menghasilkan Kodcincang yang sama.

198
00:09:29,200 --> 00:09:32,850
Mungkin kita masih mahu mendapatkan kedua-dua
bahagian data ke dalam jadual hash,

199
00:09:32,850 --> 00:09:36,330
jika tidak kami tidak akan berjalan Ringo
sewenang-wenangnya melalui fungsi hash.

200
00:09:36,330 --> 00:09:40,870
Kami mungkin ingin mendapatkan
Ringo ke dalam pelbagai itu.

201
00:09:40,870 --> 00:09:46,070
>> Bagaimana kita melakukannya walaupun, jika dia
dan Paul kedua-dua hasil Kodcincang 6?

202
00:09:46,070 --> 00:09:49,520
Kami tidak mahu menulis ganti Paul,
kita mahu Paul untuk berada di sana juga.

203
00:09:49,520 --> 00:09:52,790
Oleh itu, kita perlu mencari cara untuk mendapatkan
unsur-unsur ke dalam jadual hash yang

204
00:09:52,790 --> 00:09:56,550
masih mengekalkan cepat kami
kemasukan dan pandangan yang cepat naik.

205
00:09:56,550 --> 00:10:01,350
Dan salah satu cara untuk berurusan dengan ia adalah untuk
melakukan sesuatu yang dinamakan linear menyelesaikan sesuatu.

206
00:10:01,350 --> 00:10:04,170
>> Dengan menggunakan kaedah ini jika kita mempunyai
perlanggaran, baik, apa yang kita lakukan?

207
00:10:04,170 --> 00:10:08,580
Baik kita tidak boleh meletakkan dia di lokasi array
6, atau apa sahaja Kodcincang telah dijana,

208
00:10:08,580 --> 00:10:10,820
mari kita meletakkan dia di Kodcincang campur 1.

209
00:10:10,820 --> 00:10:13,670
Dan jika itu let penuh itu
memasukkannya ke dalam Kodcincang campur 2.

210
00:10:13,670 --> 00:10:17,420
Manfaat makhluk ini jika dia
tidak betul-betul di mana kita fikir dia adalah,

211
00:10:17,420 --> 00:10:20,850
dan kita perlu mula mencari,
mungkin kita tidak perlu pergi terlalu jauh.

212
00:10:20,850 --> 00:10:23,900
Mungkin kita tidak perlu mencari
semua n unsur-unsur jadual hash.

213
00:10:23,900 --> 00:10:25,790
Mungkin kita perlu mencari
beberapa daripada mereka.

214
00:10:25,790 --> 00:10:30,680
>> Dan dengan itu kita masih cenderung ke arah
bahawa kes purata yang hampir dengan 1 vs

215
00:10:30,680 --> 00:10:34,280
berhampiran dengan n, jadi mungkin yang akan bekerja.

216
00:10:34,280 --> 00:10:38,010
Jadi mari kita lihat bagaimana ini
mungkin bekerja di dalam realiti.

217
00:10:38,010 --> 00:10:41,460
Dan mari kita lihat jika mungkin kita dapat mengesan
masalah yang mungkin berlaku di sini.

218
00:10:41,460 --> 00:10:42,540
>> Katakan kita hash Bart.

219
00:10:42,540 --> 00:10:45,581
Jadi sekarang kita akan menjalankan satu set baru
tali melalui fungsi hash,

220
00:10:45,581 --> 00:10:48,460
dan kami menjalankan Bart melalui hash
fungsi, kita akan mendapat Kodcincang 6.

221
00:10:48,460 --> 00:10:52,100
Kita lihat, kita lihat 6 adalah
kosong, jadi kita boleh meletakkan Bart di sana.

222
00:10:52,100 --> 00:10:55,410
>> Sekarang kita hash Lisa dan
juga menjana Kodcincang 6.

223
00:10:55,410 --> 00:10:58,330
Sekarang bahawa kita menggunakan ini
linear kaedah yang kami bermula pada 6 menyelesaikan sesuatu,

224
00:10:58,330 --> 00:10:59,330
kita lihat bahawa 6 penuh.

225
00:10:59,330 --> 00:11:00,990
Kita tidak boleh meletakkan Lisa dalam 6.

226
00:11:00,990 --> 00:11:02,090
Jadi di mana kami akan pergi?

227
00:11:02,090 --> 00:11:03,280
Mari kita pergi ke 7.

228
00:11:03,280 --> 00:11:04,610
7 ini kosong, jadi yang bekerja.

229
00:11:04,610 --> 00:11:06,510
Jadi mari kita meletakkan Lisa sana.

230
00:11:06,510 --> 00:11:10,200
>> Sekarang kita hash Homer dan kita akan mendapat 7.

231
00:11:10,200 --> 00:11:13,380
OK juga kita tahu bahawa 7 ini penuh
sekarang, jadi kita tidak boleh meletakkan Homer di sana.

232
00:11:13,380 --> 00:11:14,850
Oleh itu, marilah kita pergi ke 8.

233
00:11:14,850 --> 00:11:15,664
Adalah 8 yang ada?

234
00:11:15,664 --> 00:11:18,330
Ya, dan 8 ini hampir 7, jadi jika
kita perlu mula mencari kami

235
00:11:18,330 --> 00:11:20,020
tidak akan perlu pergi terlalu jauh.

236
00:11:20,020 --> 00:11:22,860
Dan begitu mari kita meletakkan Homer di 8.

237
00:11:22,860 --> 00:11:25,151
>> Sekarang kita hash Maggie dan
mengembalikan 3, syukurlah

238
00:11:25,151 --> 00:11:26,650
kami dapat hanya meletakkan Maggie di sana.

239
00:11:26,650 --> 00:11:29,070
Kami tidak mempunyai melakukan apa-apa
semacam menyelesaikan sesuatu untuk itu.

240
00:11:29,070 --> 00:11:32,000
Sekarang kita hash Marge, dan
Marge juga mengembalikan 6.

241
00:11:32,000 --> 00:11:39,560
>> Well 6 penuh, 7 adalah penuh, 8 adalah penuh,
9, baiklah bersyukur kepada Tuhan, 9 kosong.

242
00:11:39,560 --> 00:11:41,600
Saya boleh meletakkan Marge di 9.

243
00:11:41,600 --> 00:11:45,280
Sudah kita boleh melihat bahawa kita bermula
mempunyai masalah ini di mana kini kami

244
00:11:45,280 --> 00:11:48,780
mula menghulurkan sesuatu jenis
daripada jauh dari kod hash mereka.

245
00:11:48,780 --> 00:11:52,960
Dan itu theta 1, purata yang
kes menjadi masa yang berterusan,

246
00:11:52,960 --> 00:11:56,560
mula mendapat more-- sedikit
mula cenderung sedikit lebih

247
00:11:56,560 --> 00:11:58,050
ke arah theta n.

248
00:11:58,050 --> 00:12:01,270
Kami mula kehilangan yang
Gunakan jadual hash.

249
00:12:01,270 --> 00:12:03,902
>> Masalah ini yang kita hanya melihat
adalah sesuatu yang dinamakan kelompok.

250
00:12:03,902 --> 00:12:06,360
Dan apa yang benar-benar buruk tentang
kelompok adalah bahawa apabila anda sekarang

251
00:12:06,360 --> 00:12:09,606
mempunyai dua elemen yang sebelah
sisi ia menjadikannya lebih mungkin lagi,

252
00:12:09,606 --> 00:12:11,480
anda mempunyai dua kali ganda
kebetulan, bahawa anda akan

253
00:12:11,480 --> 00:12:13,516
untuk mempunyai perlanggaran lain
dengan kelompok itu,

254
00:12:13,516 --> 00:12:14,890
dan kluster akan berkembang sebanyak satu.

255
00:12:14,890 --> 00:12:19,640
Dan anda akan terus berkembang dan berkembang
kemungkinan anda mempunyai perlanggaran.

256
00:12:19,640 --> 00:12:24,470
Dan akhirnya ia hanya sebagai lapuk
tidak menyusun data pada semua.

257
00:12:24,470 --> 00:12:27,590
>> Masalah lain walaupun adalah kita
masih, dan setakat ini sehingga ke tahap ini,

258
00:12:27,590 --> 00:12:30,336
kita baru sahaja menjadi semacam
memahami apa jadual hash adalah,

259
00:12:30,336 --> 00:12:31,960
kita masih hanya mempunyai ruang untuk 10 tali.

260
00:12:31,960 --> 00:12:37,030
Jika kita mahu terus hash
warga Springfield,

261
00:12:37,030 --> 00:12:38,790
kita hanya boleh mendapat 10 daripada mereka di sana.

262
00:12:38,790 --> 00:12:42,619
Dan jika kita cuba dan menambah ke-11 atau ke-12,
kita tidak mempunyai tempat untuk meletakkan mereka.

263
00:12:42,619 --> 00:12:45,660
Kami hanya boleh berputar di sekitar dalam
bulatan cuba untuk mencari tempat kosong,

264
00:12:45,660 --> 00:12:49,000
dan kita mungkin terjebak
dalam gelung tak terhingga.

265
00:12:49,000 --> 00:12:51,810
>> Jadi seperti ini meminjamkan kepada idea
sesuatu yang dinamakan chaining.

266
00:12:51,810 --> 00:12:55,790
Dan di sinilah kita akan membawa
senarai berkaitan kembali ke dalam gambar.

267
00:12:55,790 --> 00:13:01,300
Bagaimana jika sebaliknya menyimpan hanya
data itu sendiri dalam array,

268
00:13:01,300 --> 00:13:04,471
setiap elemen array boleh
memegang beberapa keping data?

269
00:13:04,471 --> 00:13:05,970
Baik yang tidak masuk akal, bukan?

270
00:13:05,970 --> 00:13:09,280
Kita tahu bahawa array hanya boleh
hold-- setiap elemen array

271
00:13:09,280 --> 00:13:12,930
hanya boleh memegang satu bahagian
daripada data yang jenis data.

272
00:13:12,930 --> 00:13:16,750
>> Tetapi bagaimana jika yang jenis data
senarai berpaut, bukan?

273
00:13:16,750 --> 00:13:19,830
Jadi apa jika setiap
elemen array adalah

274
00:13:19,830 --> 00:13:22,790
penunjuk kepada ketua senarai berpaut?

275
00:13:22,790 --> 00:13:24,680
Dan kemudian kita boleh membina
mereka senarai berkaitan

276
00:13:24,680 --> 00:13:27,120
dan berkembang mereka sewenang-wenangnya,
kerana senarai berkaitan membolehkan

277
00:13:27,120 --> 00:13:32,090
kami berkembang dan mengecut banyak lagi
fleksibel daripada array tidak.

278
00:13:32,090 --> 00:13:34,210
Jadi apa jika kita gunakan,
kami memanfaatkan ini, bukan?

279
00:13:34,210 --> 00:13:37,760
Kami mula berkembang rantaian ini
daripada lokasi ini pelbagai.

280
00:13:37,760 --> 00:13:40,740
>> Sekarang kita boleh memuatkan sebuah terhingga
jumlah data, atau tidak terhingga,

281
00:13:40,740 --> 00:13:44,170
satu jumlah yang sewenang-wenangnya
data, ke dalam jadual hash kami

282
00:13:44,170 --> 00:13:47,760
tanpa pernah berjalan ke
masalah perlanggaran.

283
00:13:47,760 --> 00:13:50,740
Kami juga telah dihapuskan
kelompok dengan melakukan ini.

284
00:13:50,740 --> 00:13:54,380
Dan juga kita tahu bahawa apabila kita memasukkan
ke dalam senarai berpaut, jika anda masih ingat

285
00:13:54,380 --> 00:13:57,779
dari video kami pada senarai berkaitan, secara tunggal
senarai berkaitan dan senarai duanya adalah terpakai dikaitkan,

286
00:13:57,779 --> 00:13:59,070
ia adalah satu operasi masa yang berterusan.

287
00:13:59,070 --> 00:14:00,710
Kami hanya menambah ke hadapan.

288
00:14:00,710 --> 00:14:04,400
>> Dan untuk melihat ke atas, baik kita tahu
yang kelihatan dalam senarai berpaut

289
00:14:04,400 --> 00:14:05,785
boleh menjadi masalah, bukan?

290
00:14:05,785 --> 00:14:07,910
Kita perlu mencari melalui
dari awal hingga akhir.

291
00:14:07,910 --> 00:14:10,460
Tidak ada rawak
akses dalam senarai berpaut.

292
00:14:10,460 --> 00:14:15,610
Tetapi jika bukan mempunyai satu berkaitan
senarai di mana pencarian akan menjadi O n,

293
00:14:15,610 --> 00:14:19,590
kami kini mempunyai 10 senarai berkaitan,
atau 1,000 senarai berkaitan,

294
00:14:19,590 --> 00:14:24,120
kini tiba O n dibahagikan dengan 10,
atau O n dibahagikan dengan 1,000.

295
00:14:24,120 --> 00:14:26,940
>> Dan ketika kita bercakap
secara teori tentang kerumitan

296
00:14:26,940 --> 00:14:30,061
kita tidak mengambil kira pemalar, dalam keadaan nyata
dunia perkara-perkara ini benar-benar penting,

297
00:14:30,061 --> 00:14:30,560
bukan?

298
00:14:30,560 --> 00:14:33,080
Kami benar-benar akan melihat
bahawa ini berlaku

299
00:14:33,080 --> 00:14:36,610
untuk menjalankan 10 kali lebih cepat,
atau 1,000 kali lebih cepat,

300
00:14:36,610 --> 00:14:41,570
kerana kita mengedarkan satu panjang
rantaian seluruh 1000 rantaian yang lebih kecil.

301
00:14:41,570 --> 00:14:45,090
Dan supaya setiap kali kita perlu mencari
melalui salah satu rantai yang kita boleh

302
00:14:45,090 --> 00:14:50,290
mengabaikan 999 rantaian kita tidak peduli
tentang, dan hanya mencari yang satu.

303
00:14:50,290 --> 00:14:53,220
>> Yang rata-rata untuk
1,000 kali lebih pendek.

304
00:14:53,220 --> 00:14:56,460
Dan dengan itu kita masih adalah jenis
cenderung ke arah kes purata ini

305
00:14:56,460 --> 00:15:01,610
menjadi masa yang berterusan, tetapi
hanya kerana kita memanfaatkan

306
00:15:01,610 --> 00:15:03,730
membahagikan oleh beberapa faktor yang tetap besar.

307
00:15:03,730 --> 00:15:05,804
Mari kita lihat bagaimana mungkin ini
benar-benar melihat walaupun.

308
00:15:05,804 --> 00:15:08,720
Jadi ini adalah jadual hash kami terpaksa
sebelum kita mengisytiharkan jadual hash yang

309
00:15:08,720 --> 00:15:10,270
mampu menyimpan 10 tali.

310
00:15:10,270 --> 00:15:11,728
Kami tidak akan melakukannya lagi.

311
00:15:11,728 --> 00:15:13,880
Kami sudah tahu
batasan kaedah itu.

312
00:15:13,880 --> 00:15:20,170
Sekarang jadual hash kami akan menjadi
pelbagai 10 nod, petunjuk

313
00:15:20,170 --> 00:15:22,120
kepada ketua-ketua senarai berkaitan.

314
00:15:22,120 --> 00:15:23,830
>> Dan sekarang ia null.

315
00:15:23,830 --> 00:15:26,170
Setiap seorang daripada mereka 10 petunjuk adalah batal.

316
00:15:26,170 --> 00:15:29,870
Tiada apa-apa dalam kita
hash meja sekarang.

317
00:15:29,870 --> 00:15:32,690
>> Sekarang mari kita mulakan untuk meletakkan beberapa
sesuatu ke dalam jadual hash ini.

318
00:15:32,690 --> 00:15:35,440
Dan mari kita lihat bagaimana kaedah ini adalah
akan memberi manfaat kepada kita sedikit.

319
00:15:35,440 --> 00:15:36,760
Sekarang mari kita hash Joey.

320
00:15:36,760 --> 00:15:40,210
Kami akan akan berjalan tali Joey melalui
fungsi hash dan kita kembali 6.

321
00:15:40,210 --> 00:15:41,200
Juga apa yang kita buat sekarang?

322
00:15:41,200 --> 00:15:44,090
>> Sekarang bekerja dengan senarai berkaitan,
kita tidak bekerja dengan tatasusunan.

323
00:15:44,090 --> 00:15:45,881
Dan apabila kita bekerja
dengan senarai berkaitan kita

324
00:15:45,881 --> 00:15:49,790
tahu kita perlu bermula secara dinamik
memperuntukkan ruang dan bangunan rantai.

325
00:15:49,790 --> 00:15:54,020
Itulah jenis how-- mereka adalah teras
unsur-unsur membina senarai berpaut.

326
00:15:54,020 --> 00:15:57,670
Jadi mari kita secara dinamik
memperuntukkan ruang untuk Joey,

327
00:15:57,670 --> 00:16:00,390
dan kemudian mari kita menambah beliau untuk rantai.

328
00:16:00,390 --> 00:16:03,170
>> Jadi sekarang melihat apa yang kita lakukan.

329
00:16:03,170 --> 00:16:06,440
Apabila kita hash Joey kami mendapat Kodcincang 6.

330
00:16:06,440 --> 00:16:11,790
Sekarang penunjuk di lokasi lokasi 6
menunjuk kepada ketua senarai berpaut,

331
00:16:11,790 --> 00:16:14,900
dan sekarang ia satu-satunya
unsur senarai berpaut.

332
00:16:14,900 --> 00:16:18,350
Dan simpulan dalam itu
senarai berpaut adalah Joey.

333
00:16:18,350 --> 00:16:22,300
>> Jadi, jika kita perlu mencari Joey
kemudian, kita hanya hash Joey sekali lagi,

334
00:16:22,300 --> 00:16:26,300
kita akan mendapat 6 lagi kerana kami
fungsi hash adalah berketentuan.

335
00:16:26,300 --> 00:16:30,400
Dan kemudian kita mula di kepala
senarai dikaitkan menegaskan

336
00:16:30,400 --> 00:16:33,360
untuk mengikut lokasi mudah
6, dan kita boleh melelar

337
00:16:33,360 --> 00:16:35,650
seluruh yang cuba untuk mencari Joey.

338
00:16:35,650 --> 00:16:37,780
Dan jika kita membina kami
hash meja dengan berkesan,

339
00:16:37,780 --> 00:16:41,790
dan fungsi hash kami dengan berkesan
untuk mengedarkan data dengan baik,

340
00:16:41,790 --> 00:16:45,770
secara purata setiap orang-orang yang berkaitan
senarai di setiap lokasi mudah

341
00:16:45,770 --> 00:16:50,110
akan menjadi 1/10 saiz jika kita
hanya mempunyai ia sebagai besar tunggal

342
00:16:50,110 --> 00:16:51,650
senarai dikaitkan dengan segala isinya.

343
00:16:51,650 --> 00:16:55,670
>> Jika kita mengagihkan yang besar berkaitan
senarai di 10 senarai berkaitan

344
00:16:55,670 --> 00:16:57,760
setiap senarai akan menjadi 1/10 saiz.

345
00:16:57,760 --> 00:17:01,432
Dan dengan itu 10 kali lebih cepat
untuk mencari melalui.

346
00:17:01,432 --> 00:17:02,390
Jadi mari kita buat ini lagi.

347
00:17:02,390 --> 00:17:04,290
Sekarang mari kita hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Dan katakan Ross, apabila kita berbuat demikian
kod hash kita kembali ialah 2.

349
00:17:07,540 --> 00:17:10,630
Sekarang kita dinamik memperuntukkan
nod baru, kita meletakkan Ross dalam nod itu,

350
00:17:10,630 --> 00:17:14,900
dan kami katakan sekarang lokasi mudah
2, bukan menunjuk ke batal,

351
00:17:14,900 --> 00:17:18,579
menunjuk kepada ketua berpaut
senarai yang nod sahaja Ross.

352
00:17:18,579 --> 00:17:22,660
Dan yang boleh kita lakukan satu-satu masa ini lagi, kami
boleh hash Rachel dan mendapatkan Kodcincang 4.

353
00:17:22,660 --> 00:17:25,490
malloc nod baru, meletakkan Rachel dalam
nod, dan berkata lokasi mudah

354
00:17:25,490 --> 00:17:27,839
4 kini menghala ke kepala
daripada senarai berpaut yang

355
00:17:27,839 --> 00:17:31,420
hanya unsur kebetulan Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, tetapi apa yang berlaku jika
kita ada perlanggaran?

357
00:17:33,470 --> 00:17:38,560
Mari kita lihat bagaimana kita mengendalikan perlanggaran
menggunakan kaedah chaining yang berasingan.

358
00:17:38,560 --> 00:17:39,800
Mari kita hash Phoebe.

359
00:17:39,800 --> 00:17:41,094
Kita mendapat Kodcincang 6.

360
00:17:41,094 --> 00:17:44,010
Dalam contoh kami sebelum ini kami hanya
menyimpan tali dalam array.

361
00:17:44,010 --> 00:17:45,980
Ini adalah masalah.

362
00:17:45,980 --> 00:17:48,444
>> Kami tidak mahu memukul berkali-kali
Joey, dan kami telah pun

363
00:17:48,444 --> 00:17:51,110
dilihat bahawa kita boleh mendapatkan beberapa kelompok
masalah jika kita cuba dan langkah

364
00:17:51,110 --> 00:17:52,202
melalui dan siasatan.

365
00:17:52,202 --> 00:17:54,660
Tetapi bagaimana jika kita hanya jenis
merawat ini dengan cara yang sama, bukan?

366
00:17:54,660 --> 00:17:57,440
Ia hanya seperti menambah unsur
kepada ketua senarai berpaut.

367
00:17:57,440 --> 00:18:00,220
Mari kita ruang hanya malloc untuk Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Kami akan berkata mata penunjuk Phoebe seterusnya
ke kepala lama senarai berkaitan,

369
00:18:04,764 --> 00:18:07,180
dan kemudian hanya 6 mata kepada
Ketua baru senarai berkaitan.

370
00:18:07,180 --> 00:18:10,150
Dan kini melihat, kami telah berubah Phoebe masuk.

371
00:18:10,150 --> 00:18:14,210
Kami kini boleh menyimpan dua
unsur-unsur dengan Kodcincang 6,

372
00:18:14,210 --> 00:18:17,170
dan kami tidak mempunyai sebarang masalah.

373
00:18:17,170 --> 00:18:20,147
>> Yang cukup banyak semua
ada untuk rantaian.

374
00:18:20,147 --> 00:18:21,980
Dan chaining pasti
kaedah itu

375
00:18:21,980 --> 00:18:27,390
akan menjadi yang paling berkesan untuk anda jika
anda sedang menyimpan data dalam jadual hash.

376
00:18:27,390 --> 00:18:30,890
Tetapi gabungan ini
tatasusunan dan senarai berkaitan

377
00:18:30,890 --> 00:18:36,080
bersama-sama untuk membentuk satu jadual hash benar-benar
dramatik meningkatkan keupayaan anda

378
00:18:36,080 --> 00:18:40,550
untuk menyimpan data yang banyak, dan
dengan cepat dan cekap mencari

379
00:18:40,550 --> 00:18:41,630
melalui data tersebut.

380
00:18:41,630 --> 00:18:44,150
>> Masih ada satu lagi
struktur data di luar sana

381
00:18:44,150 --> 00:18:48,700
bahawa walaupun mungkin agak
lebih baik dari segi jaminan

382
00:18:48,700 --> 00:18:51,920
bahawa kemasukan kami, penghapusan, dan
memandang masa adalah lebih cepat.

383
00:18:51,920 --> 00:18:55,630
Dan kita akan melihat bahawa dalam video di cuba.

384
00:18:55,630 --> 00:18:58,930
Saya Doug Lloyd, ini adalah CS50.

385
00:18:58,930 --> 00:19:00,214