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

2
00:00:00,500 --> 00:00:01,900
[MÜZİK OYUN]

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

4
00:00:05,710 --> 00:00:09,150
>> Doug LLOYD: Artık sen
diziler hakkında çok şey biliyorum,

5
00:00:09,150 --> 00:00:11,610
ve bağlantılı listeler hakkında çok şey biliyorum.

6
00:00:11,610 --> 00:00:13,650
Ve biz tartışmak ettik
artıları ve eksileri, biz ettik

7
00:00:13,650 --> 00:00:16,620
listeleri bağlantılı olduğu tartışılan
Daha büyük ve daha küçük alabilirsiniz

8
00:00:16,620 --> 00:00:18,630
ama onlar daha fazla boyutu kadar sürebilir.

9
00:00:18,630 --> 00:00:22,359
Diziler çok daha basit şunlardır
kullanmak, ancak onlar kadar kısıtlayıcı konum

10
00:00:22,359 --> 00:00:24,900
biz boyutunu ayarlamak zorunda
başında dizi

11
00:00:24,900 --> 00:00:26,910
ve sonra biz onunla sıkışmış.

12
00:00:26,910 --> 00:00:30,470
>> Ama bu hemen hemen ettik, var
Bizim konuların hepsi tükenmiş

13
00:00:30,470 --> 00:00:33,040
bağlantılı listeler ve diziler hakkında.

14
00:00:33,040 --> 00:00:34,950
Ya da biz var?

15
00:00:34,950 --> 00:00:37,720
Belki bir şeyler yapabiliriz
daha yaratıcı.

16
00:00:37,720 --> 00:00:40,950
Ve katıyor bu tür
Bir karma tablosu fikir.

17
00:00:40,950 --> 00:00:46,680
>> Yani bir karma tablo biz denemek için gidiyoruz
bağlantılı liste ile bir dizi birleştirir.

18
00:00:46,680 --> 00:00:49,520
Biz avantaj almaya gidiyoruz
dizinin rastgele erişim gibi,

19
00:00:49,520 --> 00:00:53,510
Sadece diziye gitmek edememek
eleman 4 veya dizi elemanı 8

20
00:00:53,510 --> 00:00:55,560
karşısında yineleme zorunda kalmadan.

21
00:00:55,560 --> 00:00:57,260
Bu doğru, çok hızlı değil mi?

22
00:00:57,260 --> 00:01:00,714
>> Ama biz de bizim veri istiyorum
yapı büyür ve küçültmek mümkün.

23
00:01:00,714 --> 00:01:02,630
Biz değil, gerek yok
sınırlı olmak istiyorum.

24
00:01:02,630 --> 00:01:04,588
Ve biz mümkün istiyorum
ekleyebilir ve şeyleri kaldırmak için

25
00:01:04,588 --> 00:01:08,430
çok kolay, hangi hatırlayacak olursak,
bir dizi ile çok karmaşık.

26
00:01:08,430 --> 00:01:11,650
Ve biz bu çağırabilirsiniz
yeni bir şey, bir karma tablo.

27
00:01:11,650 --> 00:01:15,190
>> Ve eğer, doğru bir şekilde uygulandığında
biz tür alıyorsun

28
00:01:15,190 --> 00:01:18,150
Her iki verinin avantajları
Zaten gördüğüm yapılar,

29
00:01:18,150 --> 00:01:19,880
diziler ve bağlantılı listeler.

30
00:01:19,880 --> 00:01:23,070
Ekleme başlayabilirsiniz
1 teta yönelir.

31
00:01:23,070 --> 00:01:26,207
Teta biz gerçekten ele almadığımız,
ama teta sadece ortalama durum,

32
00:01:26,207 --> 00:01:27,540
aslında ne ne olacak.

33
00:01:27,540 --> 00:01:29,680
Her zaman gitmiyorsun
En kötü durum senaryosu,

34
00:01:29,680 --> 00:01:32,555
ve her zaman sahip etmeyeceğiz
En iyi senaryo, yani ne

35
00:01:32,555 --> 00:01:33,900
Ortalama senaryo?

36
00:01:33,900 --> 00:01:36,500
>> Peki ortalama bir ekleme
karma tabloya

37
00:01:36,500 --> 00:01:39,370
yakın zaman sabiti almak için başlayabilirsiniz.

38
00:01:39,370 --> 00:01:41,570
Ve silme alabilirsiniz
sabit zaman kapatın.

39
00:01:41,570 --> 00:01:44,440
Ve arama alabilirsiniz
sabit zaman kapatın.

40
00:01:44,440 --> 00:01:48,600
Bu-- bir veri yok
yapı henüz o yapabilir,

41
00:01:48,600 --> 00:01:51,180
ve bu nedenle bu zaten sesler
oldukça büyük bir şey gibi.

42
00:01:51,180 --> 00:01:57,010
Biz gerçekten hafifletilmiş ettik
kendi başına, her dezavantajları.

43
00:01:57,010 --> 00:01:59,160
>> Bu performansı almak için
olsa biz yükseltme

44
00:01:59,160 --> 00:02:03,580
Biz ekleme nasıl yeniden düşünmek gerekir
yapısı içine verileri.

45
00:02:03,580 --> 00:02:07,380
Özellikle bizim istediğimiz
veri kendisi bize

46
00:02:07,380 --> 00:02:09,725
nerede yapıda gitmek gerekir.

47
00:02:09,725 --> 00:02:12,850
Ve biz o zaman öyle olmadığını görmek için gerekirse
yapısı, onu bulmak gerekiyorsa,

48
00:02:12,850 --> 00:02:16,610
Biz verilere bakmak istiyorum
Tekrar ve etkili muktedir,

49
00:02:16,610 --> 00:02:18,910
verileri kullanarak, rastgele erişmek.

50
00:02:18,910 --> 00:02:20,700
Sadece bakarak
Veri biz olmalı

51
00:02:20,700 --> 00:02:25,890
Tam olarak değil nerede bir fikir
hash tablosunda bulmak için gidiyor.

52
00:02:25,890 --> 00:02:28,770
>> Bir karma Şimdi olumsuz
tablo gerçekten olduğunuzu

53
00:02:28,770 --> 00:02:31,770
Sipariş veya veri sıralama oldukça kötü.

54
00:02:31,770 --> 00:02:34,970
Ve aslında, başlatırsanız
sipariş etmek veya sıralama için bunları kullanmak için

55
00:02:34,970 --> 00:02:37,990
veriler tüm kaybetmek
Avantajları daha önce sen

56
00:02:37,990 --> 00:02:40,710
ekleme ve silme yönünden vardı.

57
00:02:40,710 --> 00:02:44,060
Zaman yaklaştıkça olur
n teta ve biz temelde ettik

58
00:02:44,060 --> 00:02:45,530
bağlantılı liste halinde geriledi.

59
00:02:45,530 --> 00:02:48,850
Ve böylece biz sadece karma kullanmak istiyorum
Tabloları biz umurumda değil eğer

60
00:02:48,850 --> 00:02:51,490
veri sıralanır olmadığını.

61
00:02:51,490 --> 00:02:54,290
Bağlamda için hangi
Eğer CS50 bunları kullanırız

62
00:02:54,290 --> 00:02:58,900
muhtemelen umurumda değil
veri sıralanır.

63
00:02:58,900 --> 00:03:03,170
>> Yani karma tablo bir arada
iki ayrı parçadan

64
00:03:03,170 --> 00:03:04,980
hangi ile biz aşina.

65
00:03:04,980 --> 00:03:07,930
Ilk olarak bir işlev, olduğu
Biz genellikle karma işlevini çağırın.

66
00:03:07,930 --> 00:03:11,760
Ve bu hash fonksiyonu gidiyor
Bazı negatif olmayan tamsayı dönmek hangi

67
00:03:11,760 --> 00:03:14,870
Biz genellikle Tamam, bir hashcode diyorsun?

68
00:03:14,870 --> 00:03:20,230
İkinci parça bir dizidir
tip biz bir veri depolama kapasitesine sahip

69
00:03:20,230 --> 00:03:22,190
veri yapısı içine yerleştirmek istiyorum.

70
00:03:22,190 --> 00:03:24,310
Biz kapalı tutacağım
Şimdilik liste elemanı bağlantılı

71
00:03:24,310 --> 00:03:27,810
ve sadece temelleri ile başlar
Bunun başınızın etrafında almak için tablo karma,

72
00:03:27,810 --> 00:03:30,210
ve sonra belki darbe olacak
Aklını biraz zaman

73
00:03:30,210 --> 00:03:32,920
Birlikte diziler ve bağlantı listelerini birleştirir.

74
00:03:32,920 --> 00:03:35,590
>> Temel fikir olsa
bazı veri almak olduğunu.

75
00:03:35,590 --> 00:03:37,860
Biz bu verileri koşuyoruz
hash fonksiyonu.

76
00:03:37,860 --> 00:03:41,980
Ve böylece veri işlenir
ve Tamam, bir dizi tükürür?

77
00:03:41,980 --> 00:03:44,890
Ve sonra bu sayı ile
Biz sadece veri depolamak

78
00:03:44,890 --> 00:03:48,930
Biz saklamak istediğiniz
o yerde dizisi.

79
00:03:48,930 --> 00:03:53,990
Yani örneğin belki var
dizeleri bu karma tablo.

80
00:03:53,990 --> 00:03:57,350
O kadar, o 10 unsurları var
biz de 10 dizeleri sığdırabilirsiniz.

81
00:03:57,350 --> 00:03:59,320
>> En biz John karma istediğinizi varsayalım.

82
00:03:59,320 --> 00:04:02,979
John Yani veri olarak biz eklemek istediğiniz
bir yerde bu karma tabloya.

83
00:04:02,979 --> 00:04:03,770
Nereye koymak mı?

84
00:04:03,770 --> 00:04:05,728
Peki tipik bir
Dizi şu ana kadar biz muhtemelen

85
00:04:05,728 --> 00:04:07,610
Dizi konumu 0 koymak istiyorum.

86
00:04:07,610 --> 00:04:09,960
Ama şimdi biz bu yeni karma işlevi var.

87
00:04:09,960 --> 00:04:13,180
>> Ve en biz John çalıştırmak diyelim
Bu hash fonksiyonu sayesinde

88
00:04:13,180 --> 00:04:15,417
ve 4 dışarı tükürür var.

89
00:04:15,417 --> 00:04:17,500
Biz nereli Şey işte
John koymak istiyorum olacak.

90
00:04:17,500 --> 00:04:22,050
Biz dizi konumda John koymak istiyorum
4 biz vasıtasıyla yine John karma çünkü eğer

91
00:04:22,050 --> 00:04:23,810
daha sonraki biz diyelim
arama ve görmek istiyorum

92
00:04:23,810 --> 00:04:26,960
John, bu karma varsa
Yapmamız gereken tüm table--

93
00:04:26,960 --> 00:04:30,310
Aynı karma aracılığıyla çalıştırılır
fonksiyonu, 4 numaralı out olsun

94
00:04:30,310 --> 00:04:33,929
ve John bulmak mümkün
hemen bizim veri yapısı içinde.

95
00:04:33,929 --> 00:04:34,720
Bu oldukça iyi.

96
00:04:34,720 --> 00:04:36,928
>> En şimdi bunu diyelim
Yine, biz Paul hash istiyoruz.

97
00:04:36,928 --> 00:04:39,446
Biz Paul eklemek istediğiniz
Bu karma tabloya.

98
00:04:39,446 --> 00:04:42,070
Şimdi bu sefer koşmak diyelim
Hash fonksiyonu sayesinde Paul,

99
00:04:42,070 --> 00:04:44,600
oluşturulan hashCode 6'dır.

100
00:04:44,600 --> 00:04:47,340
Peki şimdi biz Paul koyabilirsiniz
Dizi konumda 6.

101
00:04:47,340 --> 00:04:50,040
Ve biz ister bakmak gerekirse
Pavlus bu hash tablosunda ise,

102
00:04:50,040 --> 00:04:53,900
Yapmamız gereken tüm Paul çalıştırılır
hash fonksiyonu sayesinde tekrar

103
00:04:53,900 --> 00:04:55,830
ve biz tekrar 6 almak için gidiyoruz.

104
00:04:55,830 --> 00:04:57,590
>> Ve sonra biz sadece bakmak
Dizi konumda 6.

105
00:04:57,590 --> 00:04:58,910
Paul var mı?

106
00:04:58,910 --> 00:05:00,160
Eğer öyleyse, o hash tablosunda var.

107
00:05:00,160 --> 00:05:01,875
Pavlus orada mı?

108
00:05:01,875 --> 00:05:03,000
O hash tablosunda değil.

109
00:05:03,000 --> 00:05:05,720
Oldukça basit değil.

110
00:05:05,720 --> 00:05:07,770
>> Şimdi nasıl bir karma işlev tanımlıyorsunuz?

111
00:05:07,770 --> 00:05:11,460
Peki gerçekten sınırı yoktur
olası hash fonksiyonları sayısı.

112
00:05:11,460 --> 00:05:14,350
Aslında bir dizi gerçekten var
internet üzerinde gerçekten iyi olanlar.

113
00:05:14,350 --> 00:05:17,560
Bir dizi, gerçekten var
internette gerçekten kötü olanlar.

114
00:05:17,560 --> 00:05:21,080
Aynı zamanda oldukça kolaydır
kötü bir yazma.

115
00:05:21,080 --> 00:05:23,760
>> Peki ne iyi yapar
hash fonksiyonu, değil mi?

116
00:05:23,760 --> 00:05:27,280
Peki iyi bir karma işlevi olmalı
sadece veri karma olmak kullanın,

117
00:05:27,280 --> 00:05:29,420
ve tüm verilerin karma edilir.

118
00:05:29,420 --> 00:05:32,500
Yani biz herhangibirşey kullanmak istemiyoruz
Biz bir şey dahil değil

119
00:05:32,500 --> 00:05:35,560
veri dışında başka.

120
00:05:35,560 --> 00:05:37,080
Ve biz tüm verileri kullanmak istiyorum.

121
00:05:37,080 --> 00:05:39,830
Biz sadece bir parça kullanmak istemiyorum
Bunun, biz her şeyi kullanmak istiyor.

122
00:05:39,830 --> 00:05:41,710
Bir hash fonksiyonu gerekir
Ayrıca deterministik olabilir.

123
00:05:41,710 --> 00:05:42,550
Bu ne anlama gelir?

124
00:05:42,550 --> 00:05:46,200
Peki bu demektir ki her zaman biz
Verilerin aynı parça geçmesi

125
00:05:46,200 --> 00:05:50,040
hash fonksiyonu içine biz her zaman
Aynı hashcode çıkmak.

126
00:05:50,040 --> 00:05:52,870
Ben içine John geçerseniz
hash fonksiyonu Ben 4 dışarı çık.

127
00:05:52,870 --> 00:05:56,110
Bunu yapmak mümkün olmalıdır 10.000
Zaman ve ben her zaman 4 alırsınız.

128
00:05:56,110 --> 00:06:00,810
Yani hiçbir rasgele sayılar etkin bir
Bizim karma dahil edilebilir tables--

129
00:06:00,810 --> 00:06:02,750
Bizim hash fonksiyonları içinde.

130
00:06:02,750 --> 00:06:05,750
>> Bir hash fonksiyonu da gerekir
düzgün veri dağıtmak.

131
00:06:05,750 --> 00:06:09,700
Her zaman yoluyla veri çalıştırırsanız
hash fonksiyonu, hashcode 0 olsun

132
00:06:09,700 --> 00:06:11,200
Bu doğru, muhtemelen çok büyük değil mi?

133
00:06:11,200 --> 00:06:14,600
Muhtemelen büyük istiyorum
karma kodlar bir dizi.

134
00:06:14,600 --> 00:06:17,190
Ayrıca şeyler yayılmış olabilir
masanın genelinde.

135
00:06:17,190 --> 00:06:23,210
Ve ayrıca eğer gerçekten harika olurdu
John ve Jonathan gibi benzer veri,

136
00:06:23,210 --> 00:06:26,320
Belki tartmak yayılmış
hash tablosunda farklı yerlerde.

137
00:06:26,320 --> 00:06:28,750
Bu güzel bir avantaj olacaktır.

138
00:06:28,750 --> 00:06:31,250
>> İşte hash fonksiyonu bir örnek.

139
00:06:31,250 --> 00:06:33,150
Ben daha önce bu birini yazdı.

140
00:06:33,150 --> 00:06:35,047
Bu özellikle değil
İyi hash fonksiyonu

141
00:06:35,047 --> 00:06:37,380
Gerçekten bilmiyorum nedenlerle
Şu anda girmeden ayı.

142
00:06:37,380 --> 00:06:41,040
Ama burada ne oluyor görüyorsunuz?

143
00:06:41,040 --> 00:06:44,420
Biz değişkeni bildirmek konum gibi görünüyor
toplamı ve 0'a eşit ayarlayarak çağırdı.

144
00:06:44,420 --> 00:06:50,010
Ve sonra görünüşe göre ben bir şey yapıyorum
çok uzun strstr [j], eşit değil gibi

145
00:06:50,010 --> 00:06:52,490
0 ters eğik çizgi için.

146
00:06:52,490 --> 00:06:54,870
Orada ne yapıyorum?

147
00:06:54,870 --> 00:06:57,440
>> Bu temelde sadece başka bir şeydir
[uygulanması yolu? STRL?]

148
00:06:57,440 --> 00:06:59,773
Eğer ettik ne zaman ve tespit
dizenin sonuna ulaştı.

149
00:06:59,773 --> 00:07:02,480
Yani aslında gerek yok
dize uzunluğunu hesaplamak,

150
00:07:02,480 --> 00:07:05,640
Ben vurduğunuzda sadece kullanıyorum
Ters eğik çizgi karakteri 0 biliyorum

151
00:07:05,640 --> 00:07:07,185
Ben dize sonuna ulaştım.

152
00:07:07,185 --> 00:07:09,560
Ve sonra ben tutmak için gidiyorum
Bu dizeyi yineleme,

153
00:07:09,560 --> 00:07:15,310
strstr [j] ekleyerek daha sonra da Özetle, ve
Günün sonunda toplam mod dönecek

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

155
00:07:16,200 --> 00:07:18,700
>> Temelde bütün bu karma
fonksiyonu yukarı ekliyor yapıyor

156
00:07:18,700 --> 00:07:23,450
ASCII tüm değerleri
Benim dize, ve sonra var

157
00:07:23,450 --> 00:07:26,390
Bazı hashcode dönen
HASH_MAX tarafından modded.

158
00:07:26,390 --> 00:07:29,790
Muhtemelen boyutu var
Benim dizi, değil mi?

159
00:07:29,790 --> 00:07:33,160
Ben karma getting istemiyorum
kodlar benim dizi boyutu 10 ise,

160
00:07:33,160 --> 00:07:35,712
Ben alıyorum olmak istemiyorum
dışarı karma kodları 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, ben içine şeyler koyamazsınız
dizinin bu yerler,

162
00:07:38,690 --> 00:07:39,790
bu yasadışı olurdu.

163
00:07:39,790 --> 00:07:42,130
Ben bir segment hataya acı olur.

164
00:07:42,130 --> 00:07:45,230
>> Şimdi, burada bir başka hızlı bir kenara olduğunu.

165
00:07:45,230 --> 00:07:48,470
Genellikle muhtemelen gitmiyorsun
Kendi hash fonksiyonları yazmak istiyorum.

166
00:07:48,470 --> 00:07:50,997
Aslında bir parçasıdır
bir sanat değil, bir bilim.

167
00:07:50,997 --> 00:07:52,580
Ve onlardan gider bir çok şey var.

168
00:07:52,580 --> 00:07:55,288
Dediğim gibi internet, tam
Gerçekten iyi hash fonksiyonları,

169
00:07:55,288 --> 00:07:58,470
ve interneti kullanmak gerekir
Gerçekten çünkü hash fonksiyonları bulmak

170
00:07:58,470 --> 00:08:03,230
sadece tür gereksiz
zaman israfı kendi oluşturmak için.

171
00:08:03,230 --> 00:08:05,490
>> Basit olanları yazabilirsiniz
test amaçlı.

172
00:08:05,490 --> 00:08:08,323
Ama aslında giderken
Veri karma ve saklamadan başlayın

173
00:08:08,323 --> 00:08:10,780
sen bir karma tabloya
Muhtemelen istediğiniz olacak

174
00:08:10,780 --> 00:08:14,580
oluşturulan bazı işlevi kullanmak için
Sizin için, o internette var.

175
00:08:14,580 --> 00:08:17,240
Sadece emin olun yoksa
Kaynaklarınızı alıntı.

176
00:08:17,240 --> 00:08:21,740
Hiçbir sebep yok
Burada bir şey plagiarize.

177
00:08:21,740 --> 00:08:25,370
>> Bilgisayar bilimi topluluk
Kesinlikle değerleri büyüyen ve gerçekten

178
00:08:25,370 --> 00:08:28,796
açık kaynak ve gerçekten önemli
Kaynaklarınızı alıntı böylece insanlar

179
00:08:28,796 --> 00:08:30,670
için atıf alabilirsiniz
they iş

180
00:08:30,670 --> 00:08:32,312
toplum yararına yapıyor.

181
00:08:32,312 --> 00:08:34,020
Bu nedenle her zaman sure-- olmak
ve sadece hash için

182
00:08:34,020 --> 00:08:37,270
fonksiyonlar, ancak genellikle sizi
bir dış kaynaktan kodu kullanın,

183
00:08:37,270 --> 00:08:38,299
her zaman kaynak alıntı.

184
00:08:38,299 --> 00:08:43,500
Yaptığı kişiye kredi vermek
bazı iş böylece gerekmez.

185
00:08:43,500 --> 00:08:46,720
>> Tamam o yüzden bu dönelim
Bir saniye karma tablo.

186
00:08:46,720 --> 00:08:48,780
Biz sol budur
Biz eklenen sonra kapalı

187
00:08:48,780 --> 00:08:53,300
Bu karma tabloya John ve Paul.

188
00:08:53,300 --> 00:08:55,180
Burada bir sorun görüyor musunuz?

189
00:08:55,180 --> 00:08:58,410
Sen iki görebilirsiniz.

190
00:08:58,410 --> 00:09:02,240
Ama özellikle, do you
Bu mümkün sorunu görüyor musun?

191
00:09:02,240 --> 00:09:06,770
>> Ne Ringo karma ve eğer
sonra işleme çıkıyor

192
00:09:06,770 --> 00:09:14,000
hash fonksiyonu sayesinde veri
Ringo da hashcode 6 oluşturulur.

193
00:09:14,000 --> 00:09:16,810
Zaten veri var
hashcode-- dizi yeri 6.

194
00:09:16,810 --> 00:09:22,000
Bu yüzden muhtemelen biraz olacak
Şimdi benim için sorun değil mi?

195
00:09:22,000 --> 00:09:23,060
>> Biz çarpışma diyoruz.

196
00:09:23,060 --> 00:09:26,460
Ve çarpışma sırasında iki oluşuyor
veri parçalarıdır aynı karma koşuyoruz

197
00:09:26,460 --> 00:09:29,200
işlevi aynı hashcode verir.

198
00:09:29,200 --> 00:09:32,850
Muhtemelen biz hala hem almak istiyorum
karma tabloya veri parçalarıdır,

199
00:09:32,850 --> 00:09:36,330
aksi takdirde biz Ringo çalışan olmaz
keyfi hash fonksiyonu sayesinde.

200
00:09:36,330 --> 00:09:40,870
Biz muhtemelen almak istiyorum
Bu diziye ringo.

201
00:09:40,870 --> 00:09:46,070
>> Biz olsa bunu nasıl, o takdirde
Paul hem verim hashCode 6?

202
00:09:46,070 --> 00:09:49,520
Biz Paul üzerine yazmak istemiyorum,
Biz Paul de orada olmak istiyorum.

203
00:09:49,520 --> 00:09:52,790
Yani biz almak için bir yol bulmak gerekir
karma tabloya elemanlarının

204
00:09:52,790 --> 00:09:56,550
Hala bizim hızlı korur
Ekleme ve hızlı bir bakış yukarı.

205
00:09:56,550 --> 00:10:01,350
Ve onunla başa çıkmak için bir yol olduğunu
sondalama lineer denilen bir şey yapmak.

206
00:10:01,350 --> 00:10:04,170
>> Biz varsa, bu yöntemi kullanarak
çarpışma, iyi, biz ne yapacağız?

207
00:10:04,170 --> 00:10:08,580
Peki biz dizi konuma sokamaz
6, ya da her neyse hashCode üretildi,

208
00:10:08,580 --> 00:10:10,820
en hashCode artı 1 onu koyalım.

209
00:10:10,820 --> 00:10:13,670
Ve bu tam diyelim eğer
hashCode artı 2 koydular.

210
00:10:13,670 --> 00:10:17,420
Bu varlığın yararı o eğer
tam olarak değil biz onun olduğunu düşünüyorum nerede,

211
00:10:17,420 --> 00:10:20,850
ve biz aramaya başlamak zorunda,
belki çok ileri gitmek zorunda değilsiniz.

212
00:10:20,850 --> 00:10:23,900
Belki aramak zorunda değilsiniz
karma tablonun tüm unsurları n.

213
00:10:23,900 --> 00:10:25,790
Belki aramak zorunda
Bunlardan bir çift.

214
00:10:25,790 --> 00:10:30,680
>> Ve böylece biz hala doğru eğilimi ediyoruz
Ortalama vaka 1'e yakın vs olmanın o

215
00:10:30,680 --> 00:10:34,280
n yakın, bu yüzden belki bu iş olacak.

216
00:10:34,280 --> 00:10:38,010
Yani bu nasıl görelim
gerçekte dışarı işe yarayabilir.

217
00:10:38,010 --> 00:10:41,460
Ve belki de algılayabilir bakalım
Burada oluşabilecek sorun.

218
00:10:41,460 --> 00:10:42,540
>> En biz Bart hash diyelim.

219
00:10:42,540 --> 00:10:45,581
Yani şimdi yeni bir takım çalıştırmak için gidiyoruz
hash fonksiyonu sayesinde dizeleri,

220
00:10:45,581 --> 00:10:48,460
ve biz karma ile Bart çalıştırmak
işlevi, biz hashcode 6 olsun.

221
00:10:48,460 --> 00:10:52,100
Biz bir göz atın, biz 6 görmek
Boş, biz orada Bart koyabilirsiniz.

222
00:10:52,100 --> 00:10:55,410
>> Şimdi Lisa ve karma
Ayrıca hashcode 6 oluşturur.

223
00:10:55,410 --> 00:10:58,330
Peki şimdi biz bu kullandığınızdan emin
doğrusal, biz 6'da başlayacak yöntemi sondalama

224
00:10:58,330 --> 00:10:59,330
Biz 6 tam olduğunu görüyoruz.

225
00:10:59,330 --> 00:11:00,990
Biz 6'da Lisa koyamazsınız.

226
00:11:00,990 --> 00:11:02,090
Peki nereye gidiyoruz?

227
00:11:02,090 --> 00:11:03,280
En 7'ye gidelim.

228
00:11:03,280 --> 00:11:04,610
7 boş, yani çalışır.

229
00:11:04,610 --> 00:11:06,510
Yani orada Lisa koyalım.

230
00:11:06,510 --> 00:11:10,200
>> Şimdi Homer karma ve biz 7 olsun.

231
00:11:10,200 --> 00:11:13,380
Tamam iyi bildiğimiz 7 tam olduğunu
şimdi, biz orada Homer koyamazsınız.

232
00:11:13,380 --> 00:11:14,850
Yani 8 gidelim.

233
00:11:14,850 --> 00:11:15,664
8 kullanılabilir mi?

234
00:11:15,664 --> 00:11:18,330
Evet, ve 7 8'in yakın, bu yüzden eğer
biz konum aramaya başlamak zorunda

235
00:11:18,330 --> 00:11:20,020
çok ileri gitmek zorunda değil.

236
00:11:20,020 --> 00:11:22,860
Ve bu yüzden 8 de Homer koyalım.

237
00:11:22,860 --> 00:11:25,151
>> Şimdi karma Maggie ve
3 döndürür şükür

238
00:11:25,151 --> 00:11:26,650
Biz sadece orada Maggie koymak mümkün olacaktır.

239
00:11:26,650 --> 00:11:29,070
Biz herhangi birini yapmak zorunda değilsiniz
çeşit bunun için sondalama.

240
00:11:29,070 --> 00:11:32,000
Şimdi Marge karma ve
Marge da 6 döndürür.

241
00:11:32,000 --> 00:11:39,560
>> Peki 6, 8 tam 7 dolu, dolu
9, tamam 9 boş, çok şükür.

242
00:11:39,560 --> 00:11:41,600
Ben 9'da Marge koyabilirsiniz.

243
00:11:41,600 --> 00:11:45,280
Zaten biz başlıyoruz görebilirsiniz
Biz konum şimdi bu sorunu var

244
00:11:45,280 --> 00:11:48,780
tür şeyler germek başlayan
ve uzakta onların karma kodları.

245
00:11:48,780 --> 00:11:52,960
Ve 1 şudur ki, bu ortalama
sabit zaman olma durumunda,

246
00:11:52,960 --> 00:11:56,560
Biraz more-- almaya başlıyor
biraz daha eğilimi başlayan

247
00:11:56,560 --> 00:11:58,050
n teta doğru.

248
00:11:58,050 --> 00:12:01,270
Biz kaybetmeye başlıyoruz
hash tabloları avantajı.

249
00:12:01,270 --> 00:12:03,902
>> Biz sadece gördüğümüz bu sorun
kümeleme denen şeydir.

250
00:12:03,902 --> 00:12:06,360
Ve gerçekten kötü ne
kümeleme bu sizin kez şimdi

251
00:12:06,360 --> 00:12:09,606
tarafı iki unsuru tarafından var
o daha olası hale getirir yan,

252
00:12:09,606 --> 00:12:11,480
çift ​​var
şans, sen gidiyorsun

253
00:12:11,480 --> 00:12:13,516
Başka bir çarpışmayı var
Bu küme ile,

254
00:12:13,516 --> 00:12:14,890
ve küme biri tarafından büyüyecek.

255
00:12:14,890 --> 00:12:19,640
Ve büyüyen ve büyümeye devam edeceğiz
bir çarpışma olması sizin olasılığı.

256
00:12:19,640 --> 00:12:24,470
Ve sonunda o kadar kötü
olarak tüm verileri sıralama değil.

257
00:12:24,470 --> 00:12:27,590
>> Diğer sorun olsa biz ise
Hala, ve şimdiye kadar, bu noktaya kadar,

258
00:12:27,590 --> 00:12:30,336
biz sadece bir çeşit oldum
Bir karma tablo ne anlama

259
00:12:30,336 --> 00:12:31,960
biz hala sadece 10 dizeleri için oda var.

260
00:12:31,960 --> 00:12:37,030
Biz karma devam etmek istiyorsanız,
Springfield vatandaşları,

261
00:12:37,030 --> 00:12:38,790
biz sadece orada 10 tanesi alabilirsiniz.

262
00:12:38,790 --> 00:12:42,619
Ve biz, denemek ve bir 11. veya 12. eklerseniz
Biz onları koymak için bir yer yok.

263
00:12:42,619 --> 00:12:45,660
Biz sadece etrafında dönen olabilir
çevreler, boş bir nokta bulmaya çalışıyor

264
00:12:45,660 --> 00:12:49,000
ve belki takılıp
sonsuz bir döngü içinde.

265
00:12:49,000 --> 00:12:51,810
>> Yani fikir kazandırmıştır bu tür
şey zincirleme denir.

266
00:12:51,810 --> 00:12:55,790
Ve bu bizim getirmek için gidiyoruz nerede
geri resmin içine bağlantılı listeler.

267
00:12:55,790 --> 00:13:01,300
Ne olursa yerine depolama
Dizideki verilerinin kendisi

268
00:13:01,300 --> 00:13:04,471
dizinin her öğesi olabilir
Birden fazla parça veri tutun?

269
00:13:04,471 --> 00:13:05,970
Peki bu doğru, mantıklı değil?

270
00:13:05,970 --> 00:13:09,280
Biz bir dizi sadece can biliyorum
Bir dizinin her öğesi hold--

271
00:13:09,280 --> 00:13:12,930
Sadece bir parça tutabilir
Bu veri türü veri.

272
00:13:12,930 --> 00:13:16,750
>> Ama ne eğer veri türü
bağlantılı liste, değil mi?

273
00:13:16,750 --> 00:13:19,830
Peki, eğer her
Dizinin unsur oldu

274
00:13:19,830 --> 00:13:22,790
Bağlantılı bir listesinin başında bir gösterici?

275
00:13:22,790 --> 00:13:24,680
Ve sonra biz inşa edebileceğini
O bağlantılı listeler

276
00:13:24,680 --> 00:13:27,120
ve keyfi onları büyümeye
bağlı listeler izin çünkü

277
00:13:27,120 --> 00:13:32,090
Bize büyümek ve daha bir çok küçültmek
bir dizi yapar esnek daha.

278
00:13:32,090 --> 00:13:34,210
Peki şimdi kullanırsanız,
biz doğru, bu kaldıraç?

279
00:13:34,210 --> 00:13:37,760
Biz bu zincirleri büyümeye başlar
Bu dizi yerlerden dışarı.

280
00:13:37,760 --> 00:13:40,740
>> Şimdi sonsuz sığabilecek
veri miktarı, ya da sonsuz değil,

281
00:13:40,740 --> 00:13:44,170
rasgele bir miktarda
veri bizim karma tabloya

282
00:13:44,170 --> 00:13:47,760
hiç içine çalıştırmadan
çarpışma sorunu.

283
00:13:47,760 --> 00:13:50,740
Biz de ortadan kaldırmış olduk
bunu yaparak kümeleme.

284
00:13:50,740 --> 00:13:54,380
Ve de biz taktığınızda biliyoruz
bağlantılı liste halinde, hatırlarsan

285
00:13:54,380 --> 00:13:57,779
tek başına, bağlantılı listeler bizim video
bağlı listeler ve çift bağlı listeler,

286
00:13:57,779 --> 00:13:59,070
sabit bir zaman operasyon.

287
00:13:59,070 --> 00:14:00,710
Biz sadece ön ekliyoruz.

288
00:14:00,710 --> 00:14:04,400
>> Ve bakmak up, iyi biz biliyoruz
bir bağlantılı liste bakmak

289
00:14:04,400 --> 00:14:05,785
Doğru, bir sorun olabilir?

290
00:14:05,785 --> 00:14:07,910
Biz aracılığıyla aramak zorunda
başından sonuna kadar o.

291
00:14:07,910 --> 00:14:10,460
Hiçbir tesadüfi yok
Bağlantılı bir listede erişim.

292
00:14:10,460 --> 00:14:15,610
Ama eğer yerine birine sahip bağlantılı
Bir arama n Ey olacağını liste,

293
00:14:15,610 --> 00:14:19,590
biz şimdi 10 bağlantılı listeleri var,
veya 1000 bağlı listeler,

294
00:14:19,590 --> 00:14:24,120
şimdi 10 bölü n O var,
veya n O 1.000 ile bölünmüş.

295
00:14:24,120 --> 00:14:26,940
>> Ve biz konuşurken
teorik karmaşıklığı hakkında

296
00:14:26,940 --> 00:14:30,061
Biz gerçek, sabitleri göz ardı
Bu şeyler aslında önemli dünya

297
00:14:30,061 --> 00:14:30,560
sağ?

298
00:14:30,560 --> 00:14:33,080
Biz aslında fark edeceksiniz
Bu olur

299
00:14:33,080 --> 00:14:36,610
Daha hızlı 10 kez çalıştırmak için,
ya da 1000 kat daha hızlı,

300
00:14:36,610 --> 00:14:41,570
uzun bir dağıtma çünkü
1000 küçük zincirleri karşısında zinciri.

301
00:14:41,570 --> 00:14:45,090
Ve böylece biz her zaman arama
biz o zincirleri biri aracılığıyla

302
00:14:45,090 --> 00:14:50,290
biz umurumda değil 999 zincirleri görmezden
hakkında, ve sadece bu tek arayın.

303
00:14:50,290 --> 00:14:53,220
>> Hangi ortalama üzerinde
1000 kat daha kısa.

304
00:14:53,220 --> 00:14:56,460
Ve böylece biz hala bir çeşit olan
Bu ortalama bir durumda yönelmekte

305
00:14:56,460 --> 00:15:01,610
sürekli kez olmak ancak
Sadece biz yararlanarak çünkü

306
00:15:01,610 --> 00:15:03,730
bazı büyük sabit faktör bölünerek.

307
00:15:03,730 --> 00:15:05,804
Bu nasıl olabilir Bakalım
Aslında olsa bak.

308
00:15:05,804 --> 00:15:08,720
Yani bu biz karma tablo oldu
Biz karma tablo ilan önce

309
00:15:08,720 --> 00:15:10,270
10 dizeleri depolayabilen oldu.

310
00:15:10,270 --> 00:15:11,728
Biz artık bunu gitmiyoruz.

311
00:15:11,728 --> 00:15:13,880
Biz zaten biliyoruz
Bu yöntemin sınırlamalar.

312
00:15:13,880 --> 00:15:20,170
Şimdi karma tablo olacak
10 düğümleri, işaretçiler bir dizi

313
00:15:20,170 --> 00:15:22,120
bağlantılı listeler başkanlarına.

314
00:15:22,120 --> 00:15:23,830
>> Ve şimdi o boş olduğunu.

315
00:15:23,830 --> 00:15:26,170
Bu 10 işaretçileri her biri null.

316
00:15:26,170 --> 00:15:29,870
Hiçbir şey bizim de var
Şu anda tabloyu karma.

317
00:15:29,870 --> 00:15:32,690
>> Şimdi bazı koymak başlayalım
Bu karma tabloya şeyler.

318
00:15:32,690 --> 00:15:35,440
Ve en bu yöntem nasıl görelim
Bize biraz yararına olacak.

319
00:15:35,440 --> 00:15:36,760
Şimdi Joey karma edelim.

320
00:15:36,760 --> 00:15:40,210
Biz dize Joey geçecek edeceğiz
Bir hash fonksiyonu ve biz 6 dönün.

321
00:15:40,210 --> 00:15:41,200
Peki şimdi ne yapacağız?

322
00:15:41,200 --> 00:15:44,090
>> Peki şimdi bağlantılı listeler ile çalışan,
Biz dizilerle çalışmıyor ediyoruz.

323
00:15:44,090 --> 00:15:45,881
Ve biz çalışırken
bağlantılı listeler ile biz

324
00:15:45,881 --> 00:15:49,790
Biz dinamik başlamak gerekir biliyorum
Uzay ve bina zincirleri tahsis.

325
00:15:49,790 --> 00:15:54,020
Bu tür olanlar çekirdek vardır how-- var
bağlantılı liste oluşturma unsurları.

326
00:15:54,020 --> 00:15:57,670
Yani dinamik atalım
Joey için yer tahsis,

327
00:15:57,670 --> 00:16:00,390
ve sonra zincirinin onu ekleyelim.

328
00:16:00,390 --> 00:16:03,170
>> Yani şimdi biz ne yaptık bak.

329
00:16:03,170 --> 00:16:06,440
Biz Joey hash biz hashcode 6 var.

330
00:16:06,440 --> 00:16:11,790
Dizi konumda 6 Şimdi işaretçi
Bağlantılı bir listesinin başında işaret,

331
00:16:11,790 --> 00:16:14,900
Şu anda sadece var
Bir bağlantılı liste öğesi.

332
00:16:14,900 --> 00:16:18,350
Ve bu düğüm
bağlantılı liste Joey.

333
00:16:18,350 --> 00:16:22,300
>> Biz Joey bakmak gerekirse yüzden
Daha sonra, biz sadece tekrar Joey karma,

334
00:16:22,300 --> 00:16:26,300
Nerede biz çünkü yine 6 olsun
hash fonksiyonu deterministik değildir.

335
00:16:26,300 --> 00:16:30,400
Ve sonra biz başında başlayacak
bağlantılı liste işaret

336
00:16:30,400 --> 00:16:33,360
Dizi Konuma tarafından
6 ve biz yineleme yapabilirsiniz

337
00:16:33,360 --> 00:16:35,650
Joey bulmaya çalışıyorum o karşısında.

338
00:16:35,650 --> 00:16:37,780
Ve biz inşa eğer bizim
etkin bir tablo karma,

339
00:16:37,780 --> 00:16:41,790
ve bizim hash fonksiyonu etkin bir şekilde
iyi veri dağıtmak için,

340
00:16:41,790 --> 00:16:45,770
ortalama olanların her bağlantılı
Her dizi yerde listeleri

341
00:16:45,770 --> 00:16:50,110
eğer boyutu 1/10 olacak biz
sadece tek bir dev olarak vardı

342
00:16:50,110 --> 00:16:51,650
Her şeyi ile bağlantılı liste.

343
00:16:51,650 --> 00:16:55,670
>> Biz büyük bağlantılı olduğunu dağıtırsanız
10 bağlantılı listeler arasında liste

344
00:16:55,670 --> 00:16:57,760
Her liste 1/10 boyutta olacaktır.

345
00:16:57,760 --> 00:17:01,432
Böylece 10 kat daha hızlı
arama yapmak.

346
00:17:01,432 --> 00:17:02,390
O yüzden tekrar yapalım.

347
00:17:02,390 --> 00:17:04,290
Şimdi Ross karma edelim.

348
00:17:04,290 --> 00:17:07,540
>> Ve en biz bunu yaparken Ross, diyelim
Biz dönene karma kodu 2 'dir.

349
00:17:07,540 --> 00:17:10,630
Peki şimdi biz dinamik bir tahsis
yeni bir düğüm, biz, o düğüm Ross koymak

350
00:17:10,630 --> 00:17:14,900
ve biz dizi yeri şimdi söylemek
2, null işaret yerine,

351
00:17:14,900 --> 00:17:18,579
Bağlantılı bir kafa işaret
olan tek düğüm listesi Ross.

352
00:17:18,579 --> 00:17:22,660
Ve biz, biz bu bir kez daha yapabiliriz
Rachel karma ve hashcode 4 alabilirsiniz.

353
00:17:22,660 --> 00:17:25,490
yılında Rachel koymak, yeni bir düğüm malloc
düğüm ve dizi konum demek

354
00:17:25,490 --> 00:17:27,839
4 şimdi kafasına işaret
kimin bir bağlantılı liste

355
00:17:27,839 --> 00:17:31,420
tek unsur Rachel olması umulur.

356
00:17:31,420 --> 00:17:33,470
>> Tamam ama ne olur
Biz bir çarpışmayı var?

357
00:17:33,470 --> 00:17:38,560
En biz çarpışmalar nasıl ele görelim
Ayrı zincirleme yöntemiyle.

358
00:17:38,560 --> 00:17:39,800
En Phoebe'ye hash edelim.

359
00:17:39,800 --> 00:17:41,094
Biz hashcode 6 olsun.

360
00:17:41,094 --> 00:17:44,010
Bir önceki örnekte biz sadece vardı
Dizideki dizeleri depolamak.

361
00:17:44,010 --> 00:17:45,980
Bu bir sorun oldu.

362
00:17:45,980 --> 00:17:48,444
>> Biz clobber istemiyoruz
Joey, ve biz zaten ettik

363
00:17:48,444 --> 00:17:51,110
bazı kümeleme alabilirsiniz görülmektedir
problemler çalışırsanız ve adım

364
00:17:51,110 --> 00:17:52,202
aracılığıyla ve prob.

365
00:17:52,202 --> 00:17:54,660
Ama ne olursa biz sadece tür
Bu doğru, aynı şekilde tedavi?

366
00:17:54,660 --> 00:17:57,440
Bu sadece bir öğe ekleyerek gibi
Bir bağlantılı liste başına.

367
00:17:57,440 --> 00:18:00,220
Phoebe için Sadece malloc alan edelim.

368
00:18:00,220 --> 00:18:04,764
>> Biz Phoebe sonraki işaretçi noktaları söylerim
bağlantılı liste eski başkanı,

369
00:18:04,764 --> 00:18:07,180
ve daha sonra 6 sadece işaret
bağlantılı liste yeni başkanı.

370
00:18:07,180 --> 00:18:10,150
Ve şimdi biz Phoebe değiştirdik, bak.

371
00:18:10,150 --> 00:18:14,210
Biz şimdi iki saklayabilirsiniz
hashCode 6 elemanları,

372
00:18:14,210 --> 00:18:17,170
ve biz herhangi bir sorun yok.

373
00:18:17,170 --> 00:18:20,147
>> Bu hemen hemen hepsi
zincirleme orada.

374
00:18:20,147 --> 00:18:21,980
Ve zincirleme kesinlikle
var yöntem

375
00:18:21,980 --> 00:18:27,390
eğer en etkili olacak
Bir karma tablosundaki verileri depolamak.

376
00:18:27,390 --> 00:18:30,890
Ancak bu birleşim
diziler ve bağlantılı listeler

377
00:18:30,890 --> 00:18:36,080
Birlikte gerçekten karma tablo oluşturmak için
önemli ölçüde yeteneğini geliştirir

378
00:18:36,080 --> 00:18:40,550
büyük miktarlarda veri depolamak, ve
çok hızlı ve verimli bir şekilde arama

379
00:18:40,550 --> 00:18:41,630
Bu veri üzerinden.

380
00:18:41,630 --> 00:18:44,150
>> Bir tane daha var hala
Orada veri yapısı

381
00:18:44,150 --> 00:18:48,700
hatta biraz olabilir
garanti açısından daha iyi

382
00:18:48,700 --> 00:18:51,920
Bu bizim ekleme, silme ve
bakmak süreleri daha da hızlıdır.

383
00:18:51,920 --> 00:18:55,630
Ve biz denemeden bir video olduğunu görürsünüz.

384
00:18:55,630 --> 00:18:58,930
Ben Doug Lloyd değilim, bu CS50 olduğunu.

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