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

2
00:00:00,500 --> 00:00:01,900
[MUSIC PLAYING]

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 array,

5
00:00:09,150 --> 00:00:11,610
dan Anda tahu banyak tentang daftar terkait.

6
00:00:11,610 --> 00:00:13,650
Dan kita sudah membahas
pro dan kontra, kami telah

7
00:00:13,650 --> 00:00:16,620
membahas bahwa terkait daftar
bisa mendapatkan lebih besar dan lebih kecil,

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

9
00:00:18,630 --> 00:00:22,359
Array jauh lebih mudah untuk
menggunakan, tapi mereka membatasi sebanyak

10
00:00:22,359 --> 00:00:24,900
seperti yang kita harus mengatur ukuran
array pada awal

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

12
00:00:26,910 --> 00:00:30,470
>> Tapi itu, kita sudah cukup banyak
habis semua topik kami

13
00:00:30,470 --> 00:00:33,040
tentang daftar terhubung dan array.

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

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

16
00:00:37,720 --> 00:00:40,950
Dan hal semacam meminjamkan
ide tabel hash.

17
00:00:40,950 --> 00:00:46,680
>> Jadi dalam tabel hash kita akan mencoba
menggabungkan array dengan linked list.

18
00:00:46,680 --> 00:00:49,520
Kami akan mengambil keuntungan
dari array, seperti akses acak,

19
00:00:49,520 --> 00:00:53,510
bisa hanya pergi ke berbagai
Elemen 4 atau array elemen 8

20
00:00:53,510 --> 00:00:55,560
tanpa harus beralih di.

21
00:00:55,560 --> 00:00:57,260
Itu cukup cepat, tepat?

22
00:00:57,260 --> 00:01:00,714
>> Tapi kami juga ingin memiliki data kami
struktur dapat tumbuh dan menyusut.

23
00:01:00,714 --> 00:01:02,630
Kita tidak perlu, kita tidak
ingin dibatasi.

24
00:01:02,630 --> 00:01:04,588
Dan kami ingin dapat
untuk menambah dan menghapus hal-hal

25
00:01:04,588 --> 00:01:08,430
sangat mudah, yang jika Anda ingat,
sangat kompleks dengan array.

26
00:01:08,430 --> 00:01:11,650
Dan kita bisa menyebutnya
hal baru tabel hash.

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

28
00:01:15,190 --> 00:01:18,150
keuntungan baik data
struktur Anda sudah melihat,

29
00:01:18,150 --> 00:01:19,880
array dan daftar terkait.

30
00:01:19,880 --> 00:01:23,070
Penyisipan dapat mulai
cenderung ke arah theta dari 1.

31
00:01:23,070 --> 00:01:26,207
Theta kita belum benar-benar dibahas,
tapi theta hanya kasus rata-rata,

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

33
00:01:27,540 --> 00:01:29,680
Anda tidak selalu akan
memiliki skenario kasus terburuk,

34
00:01:29,680 --> 00:01:32,555
dan Anda tidak akan selalu memiliki
skenario kasus terbaik, jadi apa

35
00:01:32,555 --> 00:01:33,900
skenario rata-rata?

36
00:01:33,900 --> 00:01:36,500
>> Nah penyisipan rata
ke dalam tabel hash

37
00:01:36,500 --> 00:01:39,370
dapat mulai mendekati waktu konstan.

38
00:01:39,370 --> 00:01:41,570
Dan penghapusan bisa mendapatkan
dekat dengan waktu konstan.

39
00:01:41,570 --> 00:01:44,440
Dan lookup bisa mendapatkan
dekat dengan waktu konstan.

40
00:01:44,440 --> 00:01:48,600
That's-- kita tidak memiliki data
Struktur belum yang dapat melakukan itu,

41
00:01:48,600 --> 00:01:51,180
dan jadi ini sudah terdengar
seperti hal yang cukup besar.

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

43
00:01:57,010 --> 00:01:59,160
>> Untuk mendapatkan kinerja ini
meng-upgrade meskipun, kita

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

45
00:02:03,580 --> 00:02:07,380
Secara khusus kami ingin
Data itu 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 harus melihat apakah itu di
struktur, jika kita harus menemukannya,

48
00:02:12,850 --> 00:02:16,610
kita ingin melihat data
lagi dan dapat secara efektif,

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

50
00:02:18,910 --> 00:02:20,700
Hanya dengan melihat
Data kita harus memiliki

51
00:02:20,700 --> 00:02:25,890
ide dari mana tepatnya kami
akan menemukannya dalam tabel hash.

52
00:02:25,890 --> 00:02:28,770
>> Sekarang downside dari hash
tabel adalah bahwa mereka benar-benar

53
00:02:28,770 --> 00:02:31,770
sangat buruk di memesan atau menyortir data.

54
00:02:31,770 --> 00:02:34,970
Dan pada kenyataannya, jika Anda mulai
menggunakannya untuk memesan atau semacam

55
00:02:34,970 --> 00:02:37,990
Data Anda kehilangan semua
keuntungan sebelumnya

56
00:02:37,990 --> 00:02:40,710
memiliki segi penyisipan dan penghapusan.

57
00:02:40,710 --> 00:02:44,060
Waktu menjadi lebih dekat dengan
theta dari n, dan kami sudah pada dasarnya

58
00:02:44,060 --> 00:02:45,530
kemunduran dalam linked list.

59
00:02:45,530 --> 00:02:48,850
Dan jadi kami hanya ingin menggunakan hash
tabel jika kita tidak peduli tentang

60
00:02:48,850 --> 00:02:51,490
apakah data diurutkan.

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

62
00:02:54,290 --> 00:02:58,900
Anda mungkin tidak peduli
bahwa data yang diurutkan.

63
00:02:58,900 --> 00:03:03,170
>> Jadi tabel hash adalah kombinasi
dari dua potong yang berbeda

64
00:03:03,170 --> 00:03:04,980
dengan yang kita kenal.

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 bahwa fungsi hash akan
kembali beberapa bilangan bulat non-negatif, yang

67
00:03:11,760 --> 00:03:14,870
biasanya kita sebut kode hash, oke?

68
00:03:14,870 --> 00:03:20,230
Bagian kedua adalah array, yang merupakan
mampu menyimpan data jenis yang kita

69
00:03:20,230 --> 00:03:22,190
ingin menempatkan ke dalam struktur data.

70
00:03:22,190 --> 00:03:24,310
Kami akan menunda pada
terkait elemen daftar untuk saat

71
00:03:24,310 --> 00:03:27,810
dan hanya mulai dengan dasar-dasar dari
hash table untuk mendapatkan kepala Anda sekitar itu,

72
00:03:27,810 --> 00:03:30,210
dan kemudian kita mungkin akan meniup
pikiran Anda sedikit ketika kita

73
00:03:30,210 --> 00:03:32,920
menggabungkan array dan daftar link yang bersama-sama.

74
00:03:32,920 --> 00:03:35,590
>> Ide dasar meskipun
adalah kita mengambil beberapa data.

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

76
00:03:37,860 --> 00:03:41,980
Dan data tersebut diolah
dan meludah keluar angka, OK?

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

78
00:03:44,890 --> 00:03:48,930
kita ingin menyimpan dalam
Array di lokasi tersebut.

79
00:03:48,930 --> 00:03:53,990
Jadi misalnya kita harus mungkin
tabel hash dari string.

80
00:03:53,990 --> 00:03:57,350
Itu punya 10 elemen di dalamnya, sehingga
kita bisa muat 10 string di dalamnya.

81
00:03:57,350 --> 00:03:59,320
>> Katakanlah kita ingin hash John.

82
00:03:59,320 --> 00:04:02,979
Jadi John sebagai data kita ingin memasukkan
ke dalam tabel hash ini di suatu tempat.

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

84
00:04:03,770 --> 00:04:05,728
Nah biasanya dengan
Array sejauh kita mungkin

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

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

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

88
00:04:13,180 --> 00:04:15,417
dan itu meludah keluar 4.

89
00:04:15,417 --> 00:04:17,500
Nah di situlah kami
akan ingin menempatkan John.

90
00:04:17,500 --> 00:04:22,050
Kami ingin menempatkan John di lokasi array yang
4, karena jika kita hash John again--

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

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

93
00:04:26,960 --> 00:04:30,310
dijalankan melalui hash yang sama
fungsi, mendapatkan nomor 4 out,

94
00:04:30,310 --> 00:04:33,929
dan dapat menemukan John
segera dalam struktur data kami.

95
00:04:33,929 --> 00:04:34,720
Itu cukup bagus.

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

97
00:04:36,928 --> 00:04:39,446
Kami ingin menambahkan Paul
ke dalam tabel hash ini.

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

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

100
00:04:44,600 --> 00:04:47,340
Nah sekarang kita dapat menempatkan Paul
di lokasi array yang 6.

101
00:04:47,340 --> 00:04:50,040
Dan jika kita perlu mencari apakah
Paulus dalam tabel 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 kita akan mendapatkan 6 keluar lagi.

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

105
00:04:57,590 --> 00:04:58,910
Apakah Paulus ada?

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

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

108
00:05:01,875 --> 00:05:03,000
Dia tidak dalam tabel hash.

109
00:05:03,000 --> 00:05:05,720
Ini cukup sederhana.

110
00:05:05,720 --> 00:05:07,770
>> Sekarang bagaimana Anda mendefinisikan fungsi hash?

111
00:05:07,770 --> 00:05:11,460
Nah ada benar-benar ada batasan untuk
sejumlah fungsi hash mungkin.

112
00:05:11,460 --> 00:05:14,350
Bahkan ada sejumlah benar-benar,
yang benar-benar baik di internet.

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

114
00:05:17,560 --> 00:05:21,080
Ini juga cukup mudah
untuk menulis yang buruk.

115
00:05:21,080 --> 00:05:23,760
>> Jadi apa yang membuat baik sebuah
Fungsi hash, kan?

116
00:05:23,760 --> 00:05:27,280
Nah fungsi hash yang baik harus
hanya menggunakan data yang hashed,

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

118
00:05:29,420 --> 00:05:32,500
Jadi kita tidak ingin menggunakan anything--
kita tidak memasukkan apa-apa

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

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

121
00:05:37,080 --> 00:05:39,830
Kami tidak ingin hanya menggunakan sepotong
itu, kita ingin menggunakan semua itu.

122
00:05:39,830 --> 00:05:41,710
Sebuah fungsi hash harus
juga menjadi deterministik.

123
00:05:41,710 --> 00:05:42,550
Maksudnya itu apa?

124
00:05:42,550 --> 00:05:46,200
Nah itu berarti bahwa setiap kali kita
lulus potongan yang sama persis data

125
00:05:46,200 --> 00:05:50,040
ke dalam fungsi hash kami selalu
mendapatkan kode hash yang sama keluar.

126
00:05:50,040 --> 00:05:52,870
Jika saya melewati John ke
Fungsi hash saya keluar 4.

127
00:05:52,870 --> 00:05:56,110
Aku harus bisa melakukan itu 10.000
kali dan saya akan selalu mendapatkan 4.

128
00:05:56,110 --> 00:06:00,810
Jadi tidak ada angka acak efektif
dapat 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
>> Sebuah fungsi hash juga harus
seragam mendistribusikan data.

131
00:06:05,750 --> 00:06:09,700
Jika setiap kali Anda menjalankan data melalui
Fungsi hash Anda mendapatkan kode hash 0,

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

133
00:06:11,200 --> 00:06:14,600
Anda mungkin ingin besar
berbagai kode hash.

134
00:06:14,600 --> 00:06:17,190
Juga hal-hal dapat menyebar
keluar seluruh meja.

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

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

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

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

139
00:06:31,250 --> 00:06:33,150
Aku menulis satu ini sebelumnya.

140
00:06:33,150 --> 00:06:35,047
Ini bukan terutama
fungsi hash yang baik

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

142
00:06:37,380 --> 00:06:41,040
Tapi apakah Anda melihat apa yang terjadi di sini?

143
00:06:41,040 --> 00:06:44,420
Sepertinya kita mendeklarasikan sebuah variabel
disebut sum dan pengaturannya sama dengan 0.

144
00:06:44,420 --> 00:06:50,010
Dan kemudian ternyata aku melakukan sesuatu
asalkan 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 lakukan di sana?

147
00:06:54,870 --> 00:06:57,440
>> Ini pada dasarnya hanyalah
cara menerapkan [? strl?]

148
00:06:57,440 --> 00:06:59,773
dan mendeteksi ketika Anda sudah
mencapai akhir dari string.

149
00:06:59,773 --> 00:07:02,480
Jadi saya tidak harus benar-benar
menghitung panjang string,

150
00:07:02,480 --> 00:07:05,640
Aku hanya menggunakan ketika saya menekan
backslash 0 karakter yang saya tahu

151
00:07:05,640 --> 00:07:07,185
Aku telah mencapai akhir dari string.

152
00:07:07,185 --> 00:07:09,560
Dan kemudian aku akan tetap
iterasi melalui string yang,

153
00:07:09,560 --> 00:07:15,310
menambahkan strstr [j] untuk jumlah, dan kemudian di
akhir hari akan kembali sum mod

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 lakukan adalah menambahkan

156
00:07:18,700 --> 00:07:23,450
semua nilai ASCII dari
tali saya, dan kemudian itu

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

158
00:07:26,390 --> 00:07:29,790
Ini mungkin ukuran
array saya, kan?

159
00:07:29,790 --> 00:07:33,160
Saya tidak ingin mendapatkan hash
Kode jika array saya adalah ukuran 10,

160
00:07:33,160 --> 00:07:35,712
Saya tidak ingin menjadi semakin
Kode hash keluar 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, saya tidak bisa meletakkan segala sesuatu ke
lokasi tersebut dari array,

162
00:07:38,690 --> 00:07:39,790
yang akan ilegal.

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

164
00:07:42,130 --> 00:07:45,230
>> Sekarang di sini adalah lain cepat samping.

165
00:07:45,230 --> 00:07:48,470
Umumnya Anda mungkin tidak akan
ingin menulis fungsi hash Anda sendiri.

166
00:07:48,470 --> 00:07:50,997
Hal ini sebenarnya sedikit
seni, bukan ilmu.

167
00:07:50,997 --> 00:07:52,580
Dan ada banyak yang masuk ke 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 harus menggunakan internet untuk
menemukan fungsi hash karena itu benar-benar

170
00:07:58,470 --> 00:08:03,230
hanya jenis yang tidak perlu
buang waktu untuk membuat Anda sendiri.

171
00:08:03,230 --> 00:08:05,490
>> Anda dapat menulis yang sederhana
untuk tujuan pengujian.

172
00:08:05,490 --> 00:08:08,323
Tetapi ketika Anda benar-benar akan
mulai hashing data dan menyimpannya

173
00:08:08,323 --> 00:08:10,780
ke dalam tabel hash Anda
mungkin akan ingin

174
00:08:10,780 --> 00:08:14,580
untuk menggunakan beberapa fungsi yang dihasilkan
untuk Anda, yang ada di internet.

175
00:08:14,580 --> 00:08:17,240
Jika Anda pastikan
untuk mengutip sumber-sumber Anda.

176
00:08:17,240 --> 00:08:21,740
Tidak ada alasan untuk
menjiplak apa pun di sini.

177
00:08:21,740 --> 00:08:25,370
>> Komunitas ilmu komputer adalah
pasti tumbuh, dan benar-benar nilai-nilai

178
00:08:25,370 --> 00:08:28,796
open source, dan itu benar-benar penting
untuk mengutip sumber-sumber Anda sehingga orang

179
00:08:28,796 --> 00:08:30,670
bisa mendapatkan atribusi untuk
pekerjaan yang mereka

180
00:08:30,670 --> 00:08:32,312
lakukan untuk kepentingan masyarakat.

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

182
00:08:34,020 --> 00:08:37,270
fungsi, tetapi umumnya ketika Anda
menggunakan kode dari sumber luar,

183
00:08:37,270 --> 00:08:38,299
selalu mengutip sumber Anda.

184
00:08:38,299 --> 00:08:43,500
Memberikan kredit kepada orang yang melakukan
beberapa pekerjaan sehingga Anda tidak perlu.

185
00:08:43,500 --> 00:08:46,720
>> OK jadi mari kita kembali ini
tabel hash untuk kedua.

186
00:08:46,720 --> 00:08:48,780
Di sinilah kami meninggalkan
off setelah kami dimasukkan

187
00:08:48,780 --> 00:08:53,300
John dan Paul ke dalam tabel hash ini.

188
00:08:53,300 --> 00:08:55,180
Apakah 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
Tapi khususnya, apakah Anda
melihat masalah ini mungkin?

191
00:09:02,240 --> 00:09:06,770
>> Bagaimana jika saya hash Ringo, dan
Ternyata setelah pengolahan

192
00:09:06,770 --> 00:09:14,000
bahwa data melalui fungsi hash
Ringo juga dihasilkan kode hash 6.

193
00:09:14,000 --> 00:09:16,810
Aku sudah punya data pada
hashcode-- lokasi Array 6.

194
00:09:16,810 --> 00:09:22,000
Jadi itu mungkin akan menjadi sedikit
dari masalah bagi saya sekarang, kan?

195
00:09:22,000 --> 00:09:23,060
>> Kami menyebutnya tabrakan.

196
00:09:23,060 --> 00:09:26,460
Dan tabrakan terjadi ketika dua
bagian data dijalankan melalui hash yang sama

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

198
00:09:29,200 --> 00:09:32,850
Agaknya kita masih ingin mendapatkan kedua
potongan data ke dalam tabel hash,

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

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

201
00:09:40,870 --> 00:09:46,070
>> Bagaimana kita melakukannya meskipun, jika dia
dan Paul kedua hasil kode hash 6?

202
00:09:46,070 --> 00:09:49,520
Kami tidak ingin menimpa Paul,
kami ingin Paulus berada di sana juga.

203
00:09:49,520 --> 00:09:52,790
Jadi kita perlu menemukan cara untuk mendapatkan
elemen ke dalam tabel hash yang

204
00:09:52,790 --> 00:09:56,550
masih mempertahankan cepat kami
penyisipan dan cepat melihat ke atas.

205
00:09:56,550 --> 00:10:01,350
Dan salah satu cara untuk menghadapinya adalah dengan
melakukan sesuatu yang disebut linear menyelidik.

206
00:10:01,350 --> 00:10:04,170
>> Dengan menggunakan metode ini jika kita memiliki
tabrakan, baik, apa yang kita lakukan?

207
00:10:04,170 --> 00:10:08,580
Yah kita tidak bisa menempatkan dia di lokasi array yang
6, atau kode hash apa pun yang dihasilkan,

208
00:10:08,580 --> 00:10:10,820
mari kita menempatkan dia di kode hash ditambah 1.

209
00:10:10,820 --> 00:10:13,670
Dan jika itu penuh mari
menempatkan dia di kode hash ditambah 2.

210
00:10:13,670 --> 00:10:17,420
Manfaat dari keberadaan ini jika dia
tidak persis di mana kita pikir dia adalah,

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

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

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

214
00:10:25,790 --> 00:10:30,680
>> Dan jadi kita masih cenderung ke arah
bahwa rata-rata kasus yang dekat dengan 1 vs

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

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

217
00:10:38,010 --> 00:10:41,460
Dan mari kita lihat apakah mungkin kita bisa mendeteksi
masalah yang mungkin terjadi di sini.

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

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

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

221
00:10:48,460 --> 00:10:52,100
Kami melihat, kita lihat 6 adalah
kosong, sehingga kita dapat menempatkan Bart ada.

222
00:10:52,100 --> 00:10:55,410
>> Sekarang kita hash Lisa dan yang
juga menghasilkan kode hash 6.

223
00:10:55,410 --> 00:10:58,330
Nah sekarang kita menggunakan ini
Metode kami mulai 6 linear probing,

224
00:10:58,330 --> 00:10:59,330
kita melihat bahwa 6 penuh.

225
00:10:59,330 --> 00:11:00,990
Kita tidak bisa menempatkan Lisa di 6.

226
00:11:00,990 --> 00:11:02,090
Jadi di mana kita 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 kosong, sehingga bekerja.

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

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

231
00:11:10,200 --> 00:11:13,380
OK baik kita tahu bahwa 7 yang penuh
sekarang, jadi kami tidak dapat menempatkan Homer ada.

232
00:11:13,380 --> 00:11:14,850
Jadi mari kita pergi ke 8.

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

234
00:11:15,664 --> 00:11:18,330
Ya, dan 8 yang dekat dengan 7, jadi jika
kita harus memulai pencarian kita

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

236
00:11:20,020 --> 00:11:22,860
Dan mari kita menempatkan Homer pada 8.

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

238
00:11:25,151 --> 00:11:26,650
kami dapat hanya menempatkan Maggie ada.

239
00:11:26,650 --> 00:11:29,070
Kami tidak perlu melakukan
semacam menyelidik untuk itu.

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

241
00:11:32,000 --> 00:11:39,560
>> Nah 6 penuh, 7 penuh, 8 penuh,
9, semua yang benar terima kasih Tuhan, 9 kosong.

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

243
00:11:41,600 --> 00:11:45,280
Sudah kita dapat melihat bahwa kita mulai
memiliki masalah ini di mana sekarang kita

244
00:11:45,280 --> 00:11:48,780
mulai meregangkan hal semacam
dari jauh dari kode hash mereka.

245
00:11:48,780 --> 00:11:52,960
Dan bahwa theta dari 1, rata-rata yang
kasus menjadi waktu yang konstan,

246
00:11:52,960 --> 00:11:56,560
mulai mendapatkan more-- sedikit
mulai cenderung sedikit lebih

247
00:11:56,560 --> 00:11:58,050
menuju theta dari n.

248
00:11:58,050 --> 00:12:01,270
Kita mulai kehilangan
keuntungan dari tabel hash.

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

250
00:12:03,902 --> 00:12:06,360
Dan apa yang benar-benar buruk tentang
pengelompokan adalah bahwa sekali Anda sekarang

251
00:12:06,360 --> 00:12:09,606
memiliki dua elemen yang berdampingan
sisi itu membuatnya bahkan lebih mungkin,

252
00:12:09,606 --> 00:12:11,480
Anda memiliki dua kali lipat
kebetulan, bahwa Anda akan

253
00:12:11,480 --> 00:12:13,516
untuk memiliki tabrakan lain
dengan klaster itu,

254
00:12:13,516 --> 00:12:14,890
dan cluster akan tumbuh dengan satu.

255
00:12:14,890 --> 00:12:19,640
Dan Anda akan terus tumbuh dan berkembang
kemungkinan Anda memiliki tabrakan.

256
00:12:19,640 --> 00:12:24,470
Dan akhirnya itu hanya sebagai buruk
tidak memilah data sama sekali.

257
00:12:24,470 --> 00:12:27,590
>> Masalah lain meskipun adalah kita
masih, dan sejauh sampai titik ini,

258
00:12:27,590 --> 00:12:30,336
kami baru saja semacam
memahami apa yang tabel hash adalah,

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

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

261
00:12:37,030 --> 00:12:38,790
kita hanya bisa mendapatkan 10 dari mereka di sana.

262
00:12:38,790 --> 00:12:42,619
Dan jika kita mencoba dan menambahkan 11 atau 12,
kita tidak memiliki tempat untuk menempatkan mereka.

263
00:12:42,619 --> 00:12:45,660
Kita bisa hanya berputar di sekitar
lingkaran berusaha untuk menemukan tempat kosong,

264
00:12:45,660 --> 00:12:49,000
dan kami mungkin terjebak
dalam loop tak terbatas.

265
00:12:49,000 --> 00:12:51,810
>> Jadi semacam ini meminjamkan untuk ide
dari sesuatu yang disebut chaining.

266
00:12:51,810 --> 00:12:55,790
Dan ini adalah di mana kita akan membawa
daftar terkait kembali ke dalam gambar.

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

268
00:13:01,300 --> 00:13:04,471
setiap elemen dari array bisa
memegang beberapa bagian data?

269
00:13:04,471 --> 00:13:05,970
Nah itu tidak masuk akal, kan?

270
00:13:05,970 --> 00:13:09,280
Kita tahu bahwa sebuah array hanya dapat
hold-- setiap elemen array

271
00:13:09,280 --> 00:13:12,930
hanya bisa menampung satu potong
data dari jenis data.

272
00:13:12,930 --> 00:13:16,750
>> Tapi bagaimana jika yang tipe data
adalah linked list, kan?

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

274
00:13:19,830 --> 00:13:22,790
pointer ke kepala linked list?

275
00:13:22,790 --> 00:13:24,680
Dan kemudian kita bisa membangun
daftar tersebut terkait

276
00:13:24,680 --> 00:13:27,120
dan tumbuh mereka sewenang-wenang,
karena daftar terkait memungkinkan

277
00:13:27,120 --> 00:13:32,090
kita untuk tumbuh dan menyusut lebih banyak
fleksibel daripada array tidak.

278
00:13:32,090 --> 00:13:34,210
Jadi bagaimana jika sekarang kita gunakan,
kita memanfaatkan ini, kan?

279
00:13:34,210 --> 00:13:37,760
Kami mulai tumbuh rantai ini
dari lokasi array yang ini.

280
00:13:37,760 --> 00:13:40,740
>> Sekarang kita bisa muat tak terbatas
jumlah data, atau tidak terbatas,

281
00:13:40,740 --> 00:13:44,170
jumlah sewenang-wenang
data, ke dalam tabel hash kami

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

283
00:13:47,760 --> 00:13:50,740
Kami juga telah menghilangkan
pengelompokan dengan melakukan hal ini.

284
00:13:50,740 --> 00:13:54,380
Dan juga kita tahu bahwa ketika kita memasukkan
menjadi linked list, jika Anda ingat

285
00:13:54,380 --> 00:13:57,779
dari video kami pada daftar terkait, secara tunggal
daftar terhubung dan daftar ganda terkait,

286
00:13:57,779 --> 00:13:59,070
ini adalah operasi waktu yang konstan.

287
00:13:59,070 --> 00:14:00,710
Kami hanya menambahkan ke depan.

288
00:14:00,710 --> 00:14:04,400
>> Dan untuk melihat ke atas, baik kita tahu
yang terlihat di sebuah linked list

289
00:14:04,400 --> 00:14:05,785
bisa menjadi masalah, kan?

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

291
00:14:07,910 --> 00:14:10,460
Tidak ada acak
akses dalam linked list.

292
00:14:10,460 --> 00:14:15,610
Tetapi jika bukan memiliki satu terkait
daftar mana lookup akan menjadi O n,

293
00:14:15,610 --> 00:14:19,590
kita sekarang memiliki 10 daftar terkait,
atau 1.000 daftar terkait,

294
00:14:19,590 --> 00:14:24,120
sekarang itu O n dibagi dengan 10,
atau O dari n dibagi dengan 1.000.

295
00:14:24,120 --> 00:14:26,940
>> Dan sementara kita berbicara
teoritis tentang kompleksitas

296
00:14:26,940 --> 00:14:30,061
kita mengabaikan konstanta, dalam nyata
dunia hal ini benar-benar penting,

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

298
00:14:30,560 --> 00:14:33,080
Kami benar-benar akan melihat
bahwa hal ini terjadi

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
karena kita mendistribusikan satu panjang
rantai di 1.000 rantai yang lebih kecil.

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

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

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

304
00:14:53,220 --> 00:14:56,460
Dan jadi kami masih semacam
cenderung ke arah kasus ini rata-rata

305
00:14:56,460 --> 00:15:01,610
menjadi waktu yang konstan, tetapi
hanya karena kita memanfaatkan

306
00:15:01,610 --> 00:15:03,730
membagi oleh beberapa faktor konstan besar.

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

308
00:15:05,804 --> 00:15:08,720
Jadi ini adalah tabel hash yang kami punya
sebelum kita menyatakan tabel hash yang

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

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

311
00:15:11,728 --> 00:15:13,880
Kami sudah tahu
keterbatasan metode tersebut.

312
00:15:13,880 --> 00:15:20,170
Sekarang tabel hash kami akan menjadi
array 10 node, pointer

313
00:15:20,170 --> 00:15:22,120
untuk kepala daftar terkait.

314
00:15:22,120 --> 00:15:23,830
>> Dan sekarang itu nol.

315
00:15:23,830 --> 00:15:26,170
Masing-masing dari mereka 10 pointer adalah null.

316
00:15:26,170 --> 00:15:29,870
Tidak ada di kami
hash table sekarang.

317
00:15:29,870 --> 00:15:32,690
>> Sekarang mari kita mulai untuk menempatkan beberapa
hal ke dalam tabel hash ini.

318
00:15:32,690 --> 00:15:35,440
Dan mari kita lihat bagaimana metode ini adalah
akan bermanfaat bagi kita sedikit.

319
00:15:35,440 --> 00:15:36,760
Mari kita sekarang hash Joey.

320
00:15:36,760 --> 00:15:40,210
Kami akan akan menjalankan string Joey melalui
fungsi hash dan kami kembali 6.

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

322
00:15:41,200 --> 00:15:44,090
>> Nah sekarang bekerja dengan daftar terkait,
kita tidak bekerja dengan array.

323
00:15:44,090 --> 00:15:45,881
Dan ketika kita sedang bekerja
dengan daftar terkait kami

324
00:15:45,881 --> 00:15:49,790
tahu kita harus mulai secara dinamis
mengalokasikan ruang dan bangunan rantai.

325
00:15:49,790 --> 00:15:54,020
Itu semacam how-- mereka adalah inti
unsur membangun sebuah linked list.

326
00:15:54,020 --> 00:15:57,670
Jadi mari kita dinamis
mengalokasikan ruang untuk Joey,

327
00:15:57,670 --> 00:16:00,390
dan kemudian mari kita menambahkannya ke rantai.

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

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

330
00:16:06,440 --> 00:16:11,790
Sekarang pointer di berbagai lokasi 6
menunjuk ke kepala linked list,

331
00:16:11,790 --> 00:16:14,900
dan sekarang itu hanya
elemen dari linked list.

332
00:16:14,900 --> 00:16:18,350
Dan node dalam
linked list adalah Joey.

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

334
00:16:22,300 --> 00:16:26,300
kita mendapatkan 6 lagi karena kami
Fungsi hash adalah deterministik.

335
00:16:26,300 --> 00:16:30,400
Dan kemudian kita mulai kepala
dari linked list menunjuk

336
00:16:30,400 --> 00:16:33,360
oleh lokasi array yang
6, dan kami dapat iterate

337
00:16:33,360 --> 00:16:35,650
di yang mencoba untuk menemukan Joey.

338
00:16:35,650 --> 00:16:37,780
Dan jika kita membangun kami
hash table efektif,

339
00:16:37,780 --> 00:16:41,790
dan fungsi hash secara efektif
untuk mendistribusikan data dengan baik,

340
00:16:41,790 --> 00:16:45,770
rata-rata masing-masing terkait
daftar di setiap lokasi array yang

341
00:16:45,770 --> 00:16:50,110
akan 10/1 ukuran jika kita
hanya memiliki sebagai besar tunggal

342
00:16:50,110 --> 00:16:51,650
linked list dengan segala sesuatu di dalamnya.

343
00:16:51,650 --> 00:16:55,670
>> Jika kita mendistribusikan besar terkait
daftar di 10 daftar terkait

344
00:16:55,670 --> 00:16:57,760
setiap daftar akan 10/1 ukuran.

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

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

347
00:17:02,390 --> 00:17:04,290
Mari kita sekarang hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Dan katakanlah Ross, ketika kita melakukan itu
kode hash kita kembali adalah 2.

349
00:17:07,540 --> 00:17:10,630
Nah sekarang kita dinamis mengalokasikan
node baru, kami menempatkan Ross di simpul itu,

350
00:17:10,630 --> 00:17:14,900
dan kita katakan sekarang lokasi array yang
2, bukannya menunjuk ke null,

351
00:17:14,900 --> 00:17:18,579
menunjuk ke kepala terkait
daftar yang hanya node Ross.

352
00:17:18,579 --> 00:17:22,660
Dan kita bisa melakukan ini sekali lagi, kita
dapat hash Rachel dan mendapatkan kode hash 4.

353
00:17:22,660 --> 00:17:25,490
malloc node baru, menempatkan Rachel di
node, dan mengatakan lokasi array yang

354
00:17:25,490 --> 00:17:27,839
4 sekarang menunjuk ke kepala
dari linked list yang

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

356
00:17:31,420 --> 00:17:33,470
>> OK tapi apa yang terjadi jika
kami memiliki tabrakan?

357
00:17:33,470 --> 00:17:38,560
Mari kita lihat bagaimana kita menangani tabrakan
menggunakan metode chaining terpisah.

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

359
00:17:39,800 --> 00:17:41,094
Kami mendapatkan kode hash 6.

360
00:17:41,094 --> 00:17:44,010
Dalam contoh kami sebelumnya kami hanya
menyimpan string 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 ingin mengkritik
Joey, dan kami sudah sudah

363
00:17:48,444 --> 00:17:51,110
melihat bahwa kita bisa mendapatkan beberapa pengelompokan
masalah jika kita mencoba dan langkah

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

365
00:17:52,202 --> 00:17:54,660
Tapi bagaimana kalau kita hanya jenis
memperlakukan ini dengan cara yang sama, kan?

366
00:17:54,660 --> 00:17:57,440
Ini seperti menambahkan elemen
kepala linked list.

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

368
00:18:00,220 --> 00:18:04,764
>> Kami akan mengatakan Phoebe poin pointer berikutnya
ke kepala lama linked list,

369
00:18:04,764 --> 00:18:07,180
dan kemudian 6 hanya menunjuk ke
kepala baru dari linked list.

370
00:18:07,180 --> 00:18:10,150
Dan sekarang lihat, kami telah mengubah Phoebe di.

371
00:18:10,150 --> 00:18:14,210
Kita sekarang dapat menyimpan dua
elemen dengan kode hash 6,

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

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

374
00:18:20,147 --> 00:18:21,980
Dan chaining pasti
metode yang

375
00:18:21,980 --> 00:18:27,390
akan menjadi yang paling efektif untuk Anda jika
Anda menyimpan data dalam tabel hash.

376
00:18:27,390 --> 00:18:30,890
Tapi kombinasi
array dan daftar terkait

377
00:18:30,890 --> 00:18:36,080
bersama-sama untuk membentuk tabel hash yang benar-benar
secara dramatis meningkatkan kemampuan Anda

378
00:18:36,080 --> 00:18:40,550
untuk menyimpan data dalam jumlah besar, dan
sangat cepat dan efisien 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
bahkan mungkin sedikit
lebih baik dalam hal menjamin

382
00:18:48,700 --> 00:18:51,920
bahwa penyisipan kami, penghapusan, dan
mencari kali bahkan lebih cepat.

383
00:18:51,920 --> 00:18:55,630
Dan kita akan melihat bahwa dalam sebuah video di mencoba.

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

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