[MÜZİK OYUN] Doug LLOYD: Artık sen diziler hakkında çok şey biliyorum, ve bağlantılı listeler hakkında çok şey biliyorum. Ve biz tartışmak ettik artıları ve eksileri, biz ettik listeleri bağlantılı olduğu tartışılan Daha büyük ve daha küçük alabilirsiniz ama onlar daha fazla boyutu kadar sürebilir. Diziler çok daha basit şunlardır kullanmak, ancak onlar kadar kısıtlayıcı konum biz boyutunu ayarlamak zorunda başında dizi ve sonra biz onunla sıkışmış. Ama bu hemen hemen ettik, var Bizim konuların hepsi tükenmiş bağlantılı listeler ve diziler hakkında. Ya da biz var? Belki bir şeyler yapabiliriz daha yaratıcı. Ve katıyor bu tür Bir karma tablosu fikir. Yani bir karma tablo biz denemek için gidiyoruz bağlantılı liste ile bir dizi birleştirir. Biz avantaj almaya gidiyoruz dizinin rastgele erişim gibi, Sadece diziye gitmek edememek eleman 4 veya dizi elemanı 8 karşısında yineleme zorunda kalmadan. Bu doğru, çok hızlı değil mi? Ama biz de bizim veri istiyorum yapı büyür ve küçültmek mümkün. Biz değil, gerek yok sınırlı olmak istiyorum. Ve biz mümkün istiyorum ekleyebilir ve şeyleri kaldırmak için çok kolay, hangi hatırlayacak olursak, bir dizi ile çok karmaşık. Ve biz bu çağırabilirsiniz yeni bir şey, bir karma tablo. Ve eğer, doğru bir şekilde uygulandığında biz tür alıyorsun Her iki verinin avantajları Zaten gördüğüm yapılar, diziler ve bağlantılı listeler. Ekleme başlayabilirsiniz 1 teta yönelir. Teta biz gerçekten ele almadığımız, ama teta sadece ortalama durum, aslında ne ne olacak. Her zaman gitmiyorsun En kötü durum senaryosu, ve her zaman sahip etmeyeceğiz En iyi senaryo, yani ne Ortalama senaryo? Peki ortalama bir ekleme karma tabloya yakın zaman sabiti almak için başlayabilirsiniz. Ve silme alabilirsiniz sabit zaman kapatın. Ve arama alabilirsiniz sabit zaman kapatın. Bu-- bir veri yok yapı henüz o yapabilir, ve bu nedenle bu zaten sesler oldukça büyük bir şey gibi. Biz gerçekten hafifletilmiş ettik kendi başına, her dezavantajları. Bu performansı almak için olsa biz yükseltme Biz ekleme nasıl yeniden düşünmek gerekir yapısı içine verileri. Özellikle bizim istediğimiz veri kendisi bize nerede yapıda gitmek gerekir. Ve biz o zaman öyle olmadığını görmek için gerekirse yapısı, onu bulmak gerekiyorsa, Biz verilere bakmak istiyorum Tekrar ve etkili muktedir, verileri kullanarak, rastgele erişmek. Sadece bakarak Veri biz olmalı Tam olarak değil nerede bir fikir hash tablosunda bulmak için gidiyor. Bir karma Şimdi olumsuz tablo gerçekten olduğunuzu Sipariş veya veri sıralama oldukça kötü. Ve aslında, başlatırsanız sipariş etmek veya sıralama için bunları kullanmak için veriler tüm kaybetmek Avantajları daha önce sen ekleme ve silme yönünden vardı. Zaman yaklaştıkça olur n teta ve biz temelde ettik bağlantılı liste halinde geriledi. Ve böylece biz sadece karma kullanmak istiyorum Tabloları biz umurumda değil eğer veri sıralanır olmadığını. Bağlamda için hangi Eğer CS50 bunları kullanırız muhtemelen umurumda değil veri sıralanır. Yani karma tablo bir arada iki ayrı parçadan hangi ile biz aşina. Ilk olarak bir işlev, olduğu Biz genellikle karma işlevini çağırın. Ve bu hash fonksiyonu gidiyor Bazı negatif olmayan tamsayı dönmek hangi Biz genellikle Tamam, bir hashcode diyorsun? İkinci parça bir dizidir tip biz bir veri depolama kapasitesine sahip veri yapısı içine yerleştirmek istiyorum. Biz kapalı tutacağım Şimdilik liste elemanı bağlantılı ve sadece temelleri ile başlar Bunun başınızın etrafında almak için tablo karma, ve sonra belki darbe olacak Aklını biraz zaman Birlikte diziler ve bağlantı listelerini birleştirir. Temel fikir olsa bazı veri almak olduğunu. Biz bu verileri koşuyoruz hash fonksiyonu. Ve böylece veri işlenir ve Tamam, bir dizi tükürür? Ve sonra bu sayı ile Biz sadece veri depolamak Biz saklamak istediğiniz o yerde dizisi. Yani örneğin belki var dizeleri bu karma tablo. O kadar, o 10 unsurları var biz de 10 dizeleri sığdırabilirsiniz. En biz John karma istediğinizi varsayalım. John Yani veri olarak biz eklemek istediğiniz bir yerde bu karma tabloya. Nereye koymak mı? Peki tipik bir Dizi şu ana kadar biz muhtemelen Dizi konumu 0 koymak istiyorum. Ama şimdi biz bu yeni karma işlevi var. Ve en biz John çalıştırmak diyelim Bu hash fonksiyonu sayesinde ve 4 dışarı tükürür var. Biz nereli Şey işte John koymak istiyorum olacak. Biz dizi konumda John koymak istiyorum 4 biz vasıtasıyla yine John karma çünkü eğer daha sonraki biz diyelim arama ve görmek istiyorum John, bu karma varsa Yapmamız gereken tüm table-- Aynı karma aracılığıyla çalıştırılır fonksiyonu, 4 numaralı out olsun ve John bulmak mümkün hemen bizim veri yapısı içinde. Bu oldukça iyi. En şimdi bunu diyelim Yine, biz Paul hash istiyoruz. Biz Paul eklemek istediğiniz Bu karma tabloya. Şimdi bu sefer koşmak diyelim Hash fonksiyonu sayesinde Paul, oluşturulan hashCode 6'dır. Peki şimdi biz Paul koyabilirsiniz Dizi konumda 6. Ve biz ister bakmak gerekirse Pavlus bu hash tablosunda ise, Yapmamız gereken tüm Paul çalıştırılır hash fonksiyonu sayesinde tekrar ve biz tekrar 6 almak için gidiyoruz. Ve sonra biz sadece bakmak Dizi konumda 6. Paul var mı? Eğer öyleyse, o hash tablosunda var. Pavlus orada mı? O hash tablosunda değil. Oldukça basit değil. Şimdi nasıl bir karma işlev tanımlıyorsunuz? Peki gerçekten sınırı yoktur olası hash fonksiyonları sayısı. Aslında bir dizi gerçekten var internet üzerinde gerçekten iyi olanlar. Bir dizi, gerçekten var internette gerçekten kötü olanlar. Aynı zamanda oldukça kolaydır kötü bir yazma. Peki ne iyi yapar hash fonksiyonu, değil mi? Peki iyi bir karma işlevi olmalı sadece veri karma olmak kullanın, ve tüm verilerin karma edilir. Yani biz herhangibirşey kullanmak istemiyoruz Biz bir şey dahil değil veri dışında başka. Ve biz tüm verileri kullanmak istiyorum. Biz sadece bir parça kullanmak istemiyorum Bunun, biz her şeyi kullanmak istiyor. Bir hash fonksiyonu gerekir Ayrıca deterministik olabilir. Bu ne anlama gelir? Peki bu demektir ki her zaman biz Verilerin aynı parça geçmesi hash fonksiyonu içine biz her zaman Aynı hashcode çıkmak. Ben içine John geçerseniz hash fonksiyonu Ben 4 dışarı çık. Bunu yapmak mümkün olmalıdır 10.000 Zaman ve ben her zaman 4 alırsınız. Yani hiçbir rasgele sayılar etkin bir Bizim karma dahil edilebilir tables-- Bizim hash fonksiyonları içinde. Bir hash fonksiyonu da gerekir düzgün veri dağıtmak. Her zaman yoluyla veri çalıştırırsanız hash fonksiyonu, hashcode 0 olsun Bu doğru, muhtemelen çok büyük değil mi? Muhtemelen büyük istiyorum karma kodlar bir dizi. Ayrıca şeyler yayılmış olabilir masanın genelinde. Ve ayrıca eğer gerçekten harika olurdu John ve Jonathan gibi benzer veri, Belki tartmak yayılmış hash tablosunda farklı yerlerde. Bu güzel bir avantaj olacaktır. İşte hash fonksiyonu bir örnek. Ben daha önce bu birini yazdı. Bu özellikle değil İyi hash fonksiyonu Gerçekten bilmiyorum nedenlerle Şu anda girmeden ayı. Ama burada ne oluyor görüyorsunuz? Biz değişkeni bildirmek konum gibi görünüyor toplamı ve 0'a eşit ayarlayarak çağırdı. Ve sonra görünüşe göre ben bir şey yapıyorum çok uzun strstr [j], eşit değil gibi 0 ters eğik çizgi için. Orada ne yapıyorum? Bu temelde sadece başka bir şeydir [uygulanması yolu? STRL?] Eğer ettik ne zaman ve tespit dizenin sonuna ulaştı. Yani aslında gerek yok dize uzunluğunu hesaplamak, Ben vurduğunuzda sadece kullanıyorum Ters eğik çizgi karakteri 0 biliyorum Ben dize sonuna ulaştım. Ve sonra ben tutmak için gidiyorum Bu dizeyi yineleme, strstr [j] ekleyerek daha sonra da Özetle, ve Günün sonunda toplam mod dönecek HASH_MAX. Temelde bütün bu karma fonksiyonu yukarı ekliyor yapıyor ASCII tüm değerleri Benim dize, ve sonra var Bazı hashcode dönen HASH_MAX tarafından modded. Muhtemelen boyutu var Benim dizi, değil mi? Ben karma getting istemiyorum kodlar benim dizi boyutu 10 ise, Ben alıyorum olmak istemiyorum dışarı karma kodları 11, 12, 13, ben içine şeyler koyamazsınız dizinin bu yerler, bu yasadışı olurdu. Ben bir segment hataya acı olur. Şimdi, burada bir başka hızlı bir kenara olduğunu. Genellikle muhtemelen gitmiyorsun Kendi hash fonksiyonları yazmak istiyorum. Aslında bir parçasıdır bir sanat değil, bir bilim. Ve onlardan gider bir çok şey var. Dediğim gibi internet, tam Gerçekten iyi hash fonksiyonları, ve interneti kullanmak gerekir Gerçekten çünkü hash fonksiyonları bulmak sadece tür gereksiz zaman israfı kendi oluşturmak için. Basit olanları yazabilirsiniz test amaçlı. Ama aslında giderken Veri karma ve saklamadan başlayın sen bir karma tabloya Muhtemelen istediğiniz olacak oluşturulan bazı işlevi kullanmak için Sizin için, o internette var. Sadece emin olun yoksa Kaynaklarınızı alıntı. Hiçbir sebep yok Burada bir şey plagiarize. Bilgisayar bilimi topluluk Kesinlikle değerleri büyüyen ve gerçekten açık kaynak ve gerçekten önemli Kaynaklarınızı alıntı böylece insanlar için atıf alabilirsiniz they iş toplum yararına yapıyor. Bu nedenle her zaman sure-- olmak ve sadece hash için fonksiyonlar, ancak genellikle sizi bir dış kaynaktan kodu kullanın, her zaman kaynak alıntı. Yaptığı kişiye kredi vermek bazı iş böylece gerekmez. Tamam o yüzden bu dönelim Bir saniye karma tablo. Biz sol budur Biz eklenen sonra kapalı Bu karma tabloya John ve Paul. Burada bir sorun görüyor musunuz? Sen iki görebilirsiniz. Ama özellikle, do you Bu mümkün sorunu görüyor musun? Ne Ringo karma ve eğer sonra işleme çıkıyor hash fonksiyonu sayesinde veri Ringo da hashcode 6 oluşturulur. Zaten veri var hashcode-- dizi yeri 6. Bu yüzden muhtemelen biraz olacak Şimdi benim için sorun değil mi? Biz çarpışma diyoruz. Ve çarpışma sırasında iki oluşuyor veri parçalarıdır aynı karma koşuyoruz işlevi aynı hashcode verir. Muhtemelen biz hala hem almak istiyorum karma tabloya veri parçalarıdır, aksi takdirde biz Ringo çalışan olmaz keyfi hash fonksiyonu sayesinde. Biz muhtemelen almak istiyorum Bu diziye ringo. Biz olsa bunu nasıl, o takdirde Paul hem verim hashCode 6? Biz Paul üzerine yazmak istemiyorum, Biz Paul de orada olmak istiyorum. Yani biz almak için bir yol bulmak gerekir karma tabloya elemanlarının Hala bizim hızlı korur Ekleme ve hızlı bir bakış yukarı. Ve onunla başa çıkmak için bir yol olduğunu sondalama lineer denilen bir şey yapmak. Biz varsa, bu yöntemi kullanarak çarpışma, iyi, biz ne yapacağız? Peki biz dizi konuma sokamaz 6, ya da her neyse hashCode üretildi, en hashCode artı 1 onu koyalım. Ve bu tam diyelim eğer hashCode artı 2 koydular. Bu varlığın yararı o eğer tam olarak değil biz onun olduğunu düşünüyorum nerede, ve biz aramaya başlamak zorunda, belki çok ileri gitmek zorunda değilsiniz. Belki aramak zorunda değilsiniz karma tablonun tüm unsurları n. Belki aramak zorunda Bunlardan bir çift. Ve böylece biz hala doğru eğilimi ediyoruz Ortalama vaka 1'e yakın vs olmanın o n yakın, bu yüzden belki bu iş olacak. Yani bu nasıl görelim gerçekte dışarı işe yarayabilir. Ve belki de algılayabilir bakalım Burada oluşabilecek sorun. En biz Bart hash diyelim. Yani şimdi yeni bir takım çalıştırmak için gidiyoruz hash fonksiyonu sayesinde dizeleri, ve biz karma ile Bart çalıştırmak işlevi, biz hashcode 6 olsun. Biz bir göz atın, biz 6 görmek Boş, biz orada Bart koyabilirsiniz. Şimdi Lisa ve karma Ayrıca hashcode 6 oluşturur. Peki şimdi biz bu kullandığınızdan emin doğrusal, biz 6'da başlayacak yöntemi sondalama Biz 6 tam olduğunu görüyoruz. Biz 6'da Lisa koyamazsınız. Peki nereye gidiyoruz? En 7'ye gidelim. 7 boş, yani çalışır. Yani orada Lisa koyalım. Şimdi Homer karma ve biz 7 olsun. Tamam iyi bildiğimiz 7 tam olduğunu şimdi, biz orada Homer koyamazsınız. Yani 8 gidelim. 8 kullanılabilir mi? Evet, ve 7 8'in yakın, bu yüzden eğer biz konum aramaya başlamak zorunda çok ileri gitmek zorunda değil. Ve bu yüzden 8 de Homer koyalım. Şimdi karma Maggie ve 3 döndürür şükür Biz sadece orada Maggie koymak mümkün olacaktır. Biz herhangi birini yapmak zorunda değilsiniz çeşit bunun için sondalama. Şimdi Marge karma ve Marge da 6 döndürür. Peki 6, 8 tam 7 dolu, dolu 9, tamam 9 boş, çok şükür. Ben 9'da Marge koyabilirsiniz. Zaten biz başlıyoruz görebilirsiniz Biz konum şimdi bu sorunu var tür şeyler germek başlayan ve uzakta onların karma kodları. Ve 1 şudur ki, bu ortalama sabit zaman olma durumunda, Biraz more-- almaya başlıyor biraz daha eğilimi başlayan n teta doğru. Biz kaybetmeye başlıyoruz hash tabloları avantajı. Biz sadece gördüğümüz bu sorun kümeleme denen şeydir. Ve gerçekten kötü ne kümeleme bu sizin kez şimdi tarafı iki unsuru tarafından var o daha olası hale getirir yan, çift ​​var şans, sen gidiyorsun Başka bir çarpışmayı var Bu küme ile, ve küme biri tarafından büyüyecek. Ve büyüyen ve büyümeye devam edeceğiz bir çarpışma olması sizin olasılığı. Ve sonunda o kadar kötü olarak tüm verileri sıralama değil. Diğer sorun olsa biz ise Hala, ve şimdiye kadar, bu noktaya kadar, biz sadece bir çeşit oldum Bir karma tablo ne anlama biz hala sadece 10 dizeleri için oda var. Biz karma devam etmek istiyorsanız, Springfield vatandaşları, biz sadece orada 10 tanesi alabilirsiniz. Ve biz, denemek ve bir 11. veya 12. eklerseniz Biz onları koymak için bir yer yok. Biz sadece etrafında dönen olabilir çevreler, boş bir nokta bulmaya çalışıyor ve belki takılıp sonsuz bir döngü içinde. Yani fikir kazandırmıştır bu tür şey zincirleme denir. Ve bu bizim getirmek için gidiyoruz nerede geri resmin içine bağlantılı listeler. Ne olursa yerine depolama Dizideki verilerinin kendisi dizinin her öğesi olabilir Birden fazla parça veri tutun? Peki bu doğru, mantıklı değil? Biz bir dizi sadece can biliyorum Bir dizinin her öğesi hold-- Sadece bir parça tutabilir Bu veri türü veri. Ama ne eğer veri türü bağlantılı liste, değil mi? Peki, eğer her Dizinin unsur oldu Bağlantılı bir listesinin başında bir gösterici? Ve sonra biz inşa edebileceğini O bağlantılı listeler ve keyfi onları büyümeye bağlı listeler izin çünkü Bize büyümek ve daha bir çok küçültmek bir dizi yapar esnek daha. Peki şimdi kullanırsanız, biz doğru, bu kaldıraç? Biz bu zincirleri büyümeye başlar Bu dizi yerlerden dışarı. Şimdi sonsuz sığabilecek veri miktarı, ya da sonsuz değil, rasgele bir miktarda veri bizim karma tabloya hiç içine çalıştırmadan çarpışma sorunu. Biz de ortadan kaldırmış olduk bunu yaparak kümeleme. Ve de biz taktığınızda biliyoruz bağlantılı liste halinde, hatırlarsan tek başına, bağlantılı listeler bizim video bağlı listeler ve çift bağlı listeler, sabit bir zaman operasyon. Biz sadece ön ekliyoruz. Ve bakmak up, iyi biz biliyoruz bir bağlantılı liste bakmak Doğru, bir sorun olabilir? Biz aracılığıyla aramak zorunda başından sonuna kadar o. Hiçbir tesadüfi yok Bağlantılı bir listede erişim. Ama eğer yerine birine sahip bağlantılı Bir arama n Ey olacağını liste, biz şimdi 10 bağlantılı listeleri var, veya 1000 bağlı listeler, şimdi 10 bölü n O var, veya n O 1.000 ile bölünmüş. Ve biz konuşurken teorik karmaşıklığı hakkında Biz gerçek, sabitleri göz ardı Bu şeyler aslında önemli dünya sağ? Biz aslında fark edeceksiniz Bu olur Daha hızlı 10 kez çalıştırmak için, ya da 1000 kat daha hızlı, uzun bir dağıtma çünkü 1000 küçük zincirleri karşısında zinciri. Ve böylece biz her zaman arama biz o zincirleri biri aracılığıyla biz umurumda değil 999 zincirleri görmezden hakkında, ve sadece bu tek arayın. Hangi ortalama üzerinde 1000 kat daha kısa. Ve böylece biz hala bir çeşit olan Bu ortalama bir durumda yönelmekte sürekli kez olmak ancak Sadece biz yararlanarak çünkü bazı büyük sabit faktör bölünerek. Bu nasıl olabilir Bakalım Aslında olsa bak. Yani bu biz karma tablo oldu Biz karma tablo ilan önce 10 dizeleri depolayabilen oldu. Biz artık bunu gitmiyoruz. Biz zaten biliyoruz Bu yöntemin sınırlamalar. Şimdi karma tablo olacak 10 düğümleri, işaretçiler bir dizi bağlantılı listeler başkanlarına. Ve şimdi o boş olduğunu. Bu 10 işaretçileri her biri null. Hiçbir şey bizim de var Şu anda tabloyu karma. Şimdi bazı koymak başlayalım Bu karma tabloya şeyler. Ve en bu yöntem nasıl görelim Bize biraz yararına olacak. Şimdi Joey karma edelim. Biz dize Joey geçecek edeceğiz Bir hash fonksiyonu ve biz 6 dönün. Peki şimdi ne yapacağız? Peki şimdi bağlantılı listeler ile çalışan, Biz dizilerle çalışmıyor ediyoruz. Ve biz çalışırken bağlantılı listeler ile biz Biz dinamik başlamak gerekir biliyorum Uzay ve bina zincirleri tahsis. Bu tür olanlar çekirdek vardır how-- var bağlantılı liste oluşturma unsurları. Yani dinamik atalım Joey için yer tahsis, ve sonra zincirinin onu ekleyelim. Yani şimdi biz ne yaptık bak. Biz Joey hash biz hashcode 6 var. Dizi konumda 6 Şimdi işaretçi Bağlantılı bir listesinin başında işaret, Şu anda sadece var Bir bağlantılı liste öğesi. Ve bu düğüm bağlantılı liste Joey. Biz Joey bakmak gerekirse yüzden Daha sonra, biz sadece tekrar Joey karma, Nerede biz çünkü yine 6 olsun hash fonksiyonu deterministik değildir. Ve sonra biz başında başlayacak bağlantılı liste işaret Dizi Konuma tarafından 6 ve biz yineleme yapabilirsiniz Joey bulmaya çalışıyorum o karşısında. Ve biz inşa eğer bizim etkin bir tablo karma, ve bizim hash fonksiyonu etkin bir şekilde iyi veri dağıtmak için, ortalama olanların her bağlantılı Her dizi yerde listeleri eğer boyutu 1/10 olacak biz sadece tek bir dev olarak vardı Her şeyi ile bağlantılı liste. Biz büyük bağlantılı olduğunu dağıtırsanız 10 bağlantılı listeler arasında liste Her liste 1/10 boyutta olacaktır. Böylece 10 kat daha hızlı arama yapmak. O yüzden tekrar yapalım. Şimdi Ross karma edelim. Ve en biz bunu yaparken Ross, diyelim Biz dönene karma kodu 2 'dir. Peki şimdi biz dinamik bir tahsis yeni bir düğüm, biz, o düğüm Ross koymak ve biz dizi yeri şimdi söylemek 2, null işaret yerine, Bağlantılı bir kafa işaret olan tek düğüm listesi Ross. Ve biz, biz bu bir kez daha yapabiliriz Rachel karma ve hashcode 4 alabilirsiniz. yılında Rachel koymak, yeni bir düğüm malloc düğüm ve dizi konum demek 4 şimdi kafasına işaret kimin bir bağlantılı liste tek unsur Rachel olması umulur. Tamam ama ne olur Biz bir çarpışmayı var? En biz çarpışmalar nasıl ele görelim Ayrı zincirleme yöntemiyle. En Phoebe'ye hash edelim. Biz hashcode 6 olsun. Bir önceki örnekte biz sadece vardı Dizideki dizeleri depolamak. Bu bir sorun oldu. Biz clobber istemiyoruz Joey, ve biz zaten ettik bazı kümeleme alabilirsiniz görülmektedir problemler çalışırsanız ve adım aracılığıyla ve prob. Ama ne olursa biz sadece tür Bu doğru, aynı şekilde tedavi? Bu sadece bir öğe ekleyerek gibi Bir bağlantılı liste başına. Phoebe için Sadece malloc alan edelim. Biz Phoebe sonraki işaretçi noktaları söylerim bağlantılı liste eski başkanı, ve daha sonra 6 sadece işaret bağlantılı liste yeni başkanı. Ve şimdi biz Phoebe değiştirdik, bak. Biz şimdi iki saklayabilirsiniz hashCode 6 elemanları, ve biz herhangi bir sorun yok. Bu hemen hemen hepsi zincirleme orada. Ve zincirleme kesinlikle var yöntem eğer en etkili olacak Bir karma tablosundaki verileri depolamak. Ancak bu birleşim diziler ve bağlantılı listeler Birlikte gerçekten karma tablo oluşturmak için önemli ölçüde yeteneğini geliştirir büyük miktarlarda veri depolamak, ve çok hızlı ve verimli bir şekilde arama Bu veri üzerinden. Bir tane daha var hala Orada veri yapısı hatta biraz olabilir garanti açısından daha iyi Bu bizim ekleme, silme ve bakmak süreleri daha da hızlıdır. Ve biz denemeden bir video olduğunu görürsünüz. Ben Doug Lloyd değilim, bu CS50 olduğunu.