[Bermain muzik] DOUG LLOYD: Oleh itu, kita telah inching dekat dan lebih dekat bahawa kaedah berpotensi suci data struktur, satu yang kita boleh memasukkan ke dalam, memotong daripada, dan melihat ke atas dalam masa yang berterusan. Betul. Itulah jenis matlamat. Kami mahu menjadi mampu untuk melakukan perkara yang sangat, sangat cepat. 

Kami dapati ia di sini apabila kita berbicara tentang try? Nah, mari kita lihat. Oleh itu, kita telah melihat beberapa struktur data yang berbeza yang mengendalikan pemetaan apa yang dikenali sebagai pasangan kunci-nilai, pemetaan sedikit data kepada beberapa bahagian lain dari data supaya kita tahu di mana untuk mencari maklumat dalam struktur. 

Jadi untuk pelbagai, sebagai contoh, utama ialah indeks unsur atau pelbagai lokasi 0 atau pelbagai 1 dan sebagainya. Dan nilai adalah data yang wujud di lokasi tersebut. Jadi apa yang disimpan dalam array 0? Apa yang disimpan dalam tatasusunan 1 berbanding hanya 0 dan 1, yang akan menjadi kunci. 

Dengan jadual hash ia jenis idea yang sama. Dengan jadual hash, kami mempunyai hash ini fungsi yang menjana kod hash. Jadi, kunci adalah kod hash data. Dan nilai, terutamanya kita bercakap tentang chaining dalam video itu di atas meja hash, ialah senarai dikaitkan data bahawa hash untuk Kodcincang itu. Betul. Bagaimana pula dengan pendekatan lain kaedah ini, walaupun? Bagaimana pula dengan kaedah yang mana utama dijamin unik, tidak seperti jadual hash, di mana kita boleh berakhir dengan dua bahagian data mempunyai Kodcincang yang sama. Dan kemudian kita perlu berurusan dengan dengan memuat menyelesaikan sesuatu atau lebih sebaik-baiknya chaining untuk menyelesaikan masalah itu. 

Oleh sebab itu kami boleh menjamin yang utama kita akan menjadi unik. Dan apa jika nilai kita adalah hanya sesuatu semudah sebagai benar dan palsu yang memberitahu kita sama ada atau tidak bahawa sekeping maklumat wujud dalam struktur? A Boolean boleh menjadi semudah sedikit. Realistik ia mungkin bait lebih mungkin daripada sedikit. Tetapi itu lebih kecil daripada menyimpan mungkin rentetan 50 aksara, contohnya. 

Jadi cuba, sama dengan hash jadual, yang menggabungkan tatasusunan dan senarai bersambung, cuba menggabungkan tatasusunan, struktur, dan petunjuk bersama-sama untuk menyimpan data dalam cara yang menarik itu cukup berbeza daripada apa-apa yang kita lihat setakat ini. Sekarang kita menggunakan data sebagai hala tuju yang untuk mengemudi struktur data ini. Dan jika kita boleh mengikuti pelan tindakan itu, jika kita boleh mengikut data dari awal hingga akhir, kita akan tahu sama ada data yang wujud di indone itu. 

Dan jika kita tidak boleh ikut peta dari bermaksud untuk menamatkan sama sekali, data tidak boleh wujud. Sekali lagi, kunci di sini adalah dijamin unik. Dan sebagainya tidak seperti jadual hash, kita akan tidak pernah perlu berurusan dengan perlanggaran di sini. Dan tidak ada dua bahagian data telah betul-betul pelan hala tuju yang sama kecuali data yang serupa. 

Jika kita memasukkan John, kemudian kita mencari John. Itu dua keping serupa data, betul, kita sedang melalui. Tetapi jika tidak, mana-mana dua keping data adalah dijamin untuk mempunyai peta jalan yang unik melalui struktur data ini. Dan kita akan lihat pada visual ini dalam hanya seketika. 

Kami akan melakukan ini dengan cuba untuk mewujudkan satu struktur data baru, pemetaan pasangan nilai utama berikut. Dalam kes ini, kita tidak akan menggunakan sesuatu yang mudah seperti yang Boolean. Kami benar-benar akan menyimpan tali. Dan tali yang akan menjadi nama sebuah universiti. 

Dan kunci akan menjadi tahun apabila universiti yang diasaskan. Semua tahun bagi universiti akan menjadi empat digit. Dan dengan itu kita akan menggunakan orang-orang empat digit untuk menavigasi melalui struktur data ini. Dan kita akan melihat, sekali lagi, bagaimana kita berbuat demikian dalam masa satu saat. 

Pada akhir jalan, kita akan melihat nama universiti yang sepadan kepada kekunci itu, mereka empat digit. Idea asas di sebalik indone a adalah kita mempunyai laluan pusat. Jadi berfikir mengenainya seperti pokok. Dan ini adalah sama dalam ejaan dan konsepnya dengan pokok. Secara umumnya apabila kita berfikir tentang pokok di dunia sebenar, mereka mempunyai akar yang dalam yang tanah dan mereka membesar menaik dan mereka mempunyai cawangan dan mereka mempunyai daun. Dan pada dasarnya idea indone adalah sama, kecuali akar yang berlabuh di suatu tempat di langit. Dan daun di bahagian bawah. 

Jadi ia adalah jenis seperti mengambil pokok dan hanya membalik terbalik. Tetapi masih terdapat cawangan. Dan orang-orang akan menjadi laluan kami, mereka akan menjadi hubungan kami dari akar ke daun. Dalam kes ini, orang-orang laluan, orang-orang cawangan dilabel dengan digit yang memberitahu kita yang cara untuk pergi dari mana kita berada. 

Jika kita lihat 0, kita pergi ke cawangan ini, jika kita melihat 1, kita turun cawangan ini, dan sebagainya dan sebagainya. Nah, apa maknanya? Nah, itu bermakna pada setiap titik persimpangan dan setiap nod dalam pertengahan dan setiap cawangan, terdapat 10 mungkin tempat-tempat yang kita boleh pergi. Jadi terdapat 10 petunjuk dari setiap lokasi. 

Dan di sinilah try boleh mendapatkan sedikit menakutkan bagi seseorang siapa yang tidak mempunyai banyak pengalaman dalam bidang sains komputer sebelum ini. Tetapi cuba benar-benar cukup menggerunkan. Dan jika anda mempunyai peluang untuk bekerja dengan mereka dan anda bersedia untuk menggali masuk dan bereksperimen dengan mereka, mereka benar-benar agak menarik struktur data untuk bekerja dengan. Jika kita mahu memasukkan unsur ke dalam indone, semua perlu kita lakukan adalah membina jalan yang betul dari akar ke daun. Berikut adalah apa yang setiap langkah cara mungkin kelihatan seperti. Kami akan menentukan data baru struktur bagi nod baru dipanggil indone a. 

Dan di dalam data yang struktur terdapat dua keping. Kami akan menyimpan menamakan sebuah universiti. Dan kita akan menyimpan pelbagai petunjuk untuk nod lain dari jenis yang sama. Jadi, sekali lagi, ini adalah seperti itu daripada konsep di mana-mana kami, kami di 10 mungkin tempat kita boleh pergi. Jika kita lihat 0, kita pergi ke cawangan ini. Jika kita melihat 1, cawangan ini, dan sebagainya dan sebagainya dan sebagainya. Jika kita mengatakan 9, kita turun cawangan ini. Jadi pada setiap titik persimpangan, kita boleh pergi 10 tempat mungkin. Jadi setiap nod mempunyai mengandungi 10 petunjuk kepada nod yang lain, untuk 10 nod lain. 

Dan data yang kita menyimpan adalah hanya nama universiti. Jadi mari kita membina indone a. Mari kita memasukkan pasangan item ke dalam indone kami. Jadi pada bahagian paling atas, ini adalah nod akar kami. Ini mungkin akan menjadi sesuatu anda akan mengisytiharkan secara global. Dan anda akan secara global mengekalkan penunjuk kepada nod ini sentiasa. 

Anda akan berkata, akar sama, dan anda akan malloc diri nod indone. Dan anda tidak akan menyentuh akar lagi. Setiap kali anda mahu mula menavigasi melalui, anda menetapkan penunjuk lain sama dengan punca, seperti trav, yang merupakan contoh yang saya menggunakan dalam banyak video saya di sini pada susunan dan beratur dan senarai link dan sebagainya. 

Anda menetapkan penunjuk lain dipanggil trav untuk penyusuran. Dan anda menggunakan trav untuk mengemudi melalui struktur data. Jadi mari kita lihat bagaimana ini mungkin kelihatan. Jadi sekarang, apa tidak nod kelihatan seperti? Nah, hanya sebagai data kami pengisytiharan struktur dinyatakan, kita mempunyai tali, yang dalam kes ini adalah kosong. Tiada apa-apa di sini. 

Dan pelbagai 10 petunjuk. Dan sekarang, kita hanya 1 nod dalam indone ini. Ada apa-apa lagi di dalamnya. Jadi semua 10 orang petunjuk titik ke nol. Itulah yang merah menunjukkan. 

Mari kita memasukkan tali Harvard. Mari kita memasukkan Universiti Harvard ke indone ini, yang telah ditubuhkan pada tahun 1636. Kami mahu menggunakan kekunci, 1636, untuk memberitahu kami di mana kita berada akan menyimpan Harvard di indone itu. Sekarang, bagaimana kita boleh berbuat demikian? 

Ia mungkin kelihatan seperti ini. Kami bermula dari akar. Dan kita mempunyai 10 tempat kita boleh pergi. Akar adalah seperti mana-mana nod lain indone itu. Terdapat 10 tempat kita boleh pergi dari sini. 

Di manakah kita mungkin mahu untuk pergi jika yang penting adalah 1636? Ada benar-benar dua pilihan. Betul. Kita boleh membina kunci dari kanan ke kiri dan bermula dengan 6. Atau kita boleh membina kunci dari kiri ke kanan dan mulakan dengan 1. 

Ia mungkin lebih intuitif sebagai manusia untuk memahami kita akan hanya pergi kiri ke kanan. Dan jadi jika saya mahu memasukkan Harvard ke indone ini, Saya mungkin ingin memulakan dengan memulakan pada akar, melihat 10 pilihan saya di depan saya, dan berkata Saya mahu pergi ke jalan yang 1. OKAY. 

Sekarang, 1 jalan kini null. Jadi, jika saya mahu meneruskan ke jalan yang untuk memasukkan elemen ini ke dalam indone itu, Saya mempunyai malloc nod baru, mempunyai 1 menunjukkan di sana, dan kemudian saya baik untuk pergi. 

Jadi saya pada dasarnya adalah di titik di mana saya berdiri pada akar pokok atau indone dan terdapat 10 cawangan. Tetapi setiap cawangan mempunyai pintu di hadapannya. Betul. Oleh kerana tiada apa-apa lagi yang ada. Tiada laluan selamat. Ini bermakna bahawa tiada apa-apa bawah mana-mana cawangan. Jika saya ingin memulakan bangunan sesuatu, saya mahu mengeluarkan pintu pagar. Saya mahu mengeluarkan pintu gerbang di hadapan nombor 1. Dan saya mahu berjalan itu. Dan saya mahu membina tempat lain untuk saya pergi. 

Dan itulah yang saya lakukan di sini. Jadi 1 tidak lagi menunjuk kepada nol. Saya telah berkata ia adalah selamat untuk turun di sini sekarang. Saya membina nod yang lain. Dan apabila saya ke nod itu, saya mempunyai satu lagi keputusan untuk membuat. Di mana saya akan pergi dari sini? 

Well, saya telah pergi ke bawah 1. Jadi sekarang saya mungkin mahu turun ke bawah 6. Betul. Sekali lagi, saya mempunyai 10 lokasi saya boleh pilih. Jadi mari kita kini turun nombor 6. Jadi saya membersihkan pintu gerbang di hadapan nombor 6. Dan saya berjalan di bawah sana. Dan saya membina nod yang lain. Dan saya telah mencapai titik persimpangan lain. 

Sekali lagi, saya mempunyai 10 pilihan untuk di mana saya boleh pergi. Saya telah berpindah 1-6. Jadi sekarang saya mungkin mahu pergi ke 3. 3, tidak ada tempat yang saya boleh pergi. Jadi saya perlu untuk membersihkan jalan dan membina diri saya ruang baru. Dan kemudian dari 3, di mana saya mahu pergi? Saya mahu turun ke bawah 6. 

Dan, sekali lagi, saya terpaksa membersihkan jalan untuk melakukannya. Jadi sekarang saya telah menggunakan kekunci saya untuk memasukkan mewujudkan nod dan mula membina indone ini. Saya telah memulakan pada akar. Saya telah pergi ke bawah 1636. Dan sekarang saya di bahagian bawah terdapat pada nod itu. Dan anda mungkin boleh melihatnya di skrin anda. 

Ia berwarna kuning. Itulah di mana saya kini am. Kekunci saya dilakukan. Saya telah habis setiap kedudukan dalam kunci saya. Jadi saya tidak boleh pergi mana-mana lagi. Jadi pada ketika ini, apa yang saya benar-benar perlu lakukan adalah berkata, OK. Ia adalah jenis suka mencari ke bawah di bawah, jika anda membayangkan diri anda sebagai seperti ini jalan dengan sambungan yang berbeza. Semacam melihat ke bawah dan jenis spray lukisan Harvard di atas tanah. Itulah nama ini. Tahu bahawa apa yang di lokasi ini. Jika kita bermula dari akar dan kita turun 1 dan kemudian 6 dan kemudian 3 dan kemudian 6, di mana kita? Baik jika kita melihat ke bawah dan kita lihat Harvard, kemudian kita tahu bahawa Harvard adalah ditubuhkan pada 1636 berdasarkan cara kita melaksanakan struktur data ini. Jadi yang diharapkan mudah. Kami akan melakukan dua lagi sisipan. Dan mudah-mudahan ia akan membantu untuk melihat ini dilakukan dua kali lagi. 

Sekarang, mari kita memasukkan universiti lain. Mari kita memasukkan Yale ke indone ini. Yale ditubuhkan pada 1701. Oleh itu, kita akan bermula pada akar, seperti yang kita selalu lakukan. Dan kami menetapkan penunjuk penyusuran. Kita akan menggunakannya untuk bergerak melalui. Perkara pertama yang kita mahu lakukan adalah pergi ke jalan yang 1. Itulah angka pertama utama kami. Nasib baik, walaupun, kita tidak perlu melakukan apa-apa kerja masa ini. 1 jalan telah dibersihkan. Saya dibersihkan ia sebelum ini apabila saya telah memasukkan Harvard pada 1636. Jadi saya selamat boleh bergerak turun 1 dan hanya pergi ke sana. Jika boleh bergerak ke bawah 1. 

Sekarang, walaupun, saya mahu pergi ke 7. Saya membuka jalan pada 6. Saya tahu saya boleh selamat meneruskan ke jalan yang 6. Tetapi saya perlu meneruskan di jalan yang 7. Jadi, apa yang perlu saya lakukan? Well, seperti sebelum ini, saya hanya perlu untuk membersihkan pintu, keluar dari jalan, dan membina nod baru dari jalan yang 7. Hanya seperti ini. 

Jadi sekarang saya telah berpindah 1 dan kemudian 7. Dan kini melihat, Saya jenis dari pada subbranch baru ini. Betul. Segala-galanya daripada 16 , saya tidak mengambil berat tentang. Saya tidak melakukan 16 apa-apa. Saya melakukan 17 barangan. 

Jadi sekarang dari 17 pada, saya perlu semacam pergi mengikut laluan baru di sini. Digit berikut utama saya ialah 0. Saya dengan jelas tidak boleh mendapatkan mana-mana sahaja. Saya hanya dibina nod ini. Jadi saya tahu tidak ada laluan ke hadapan dari sini. Jadi saya perlu membuat satu diri saya sendiri. 

Jadi saya malloc nod baru dan mempunyai 0 mata di sana. Dan kemudian sekali lagi, saya malloc yang nod baru dan mempunyai satu mata di sana. Sekali lagi, saya telah habis utama saya, 1701. Jadi saya melihat ke bawah dan saya menyembur cat Yale. Itulah nama nod ini. 

Dan sekarang jika saya merasa perlu untuk melihat jika Yale adalah di indone ini, saya bermula dari akar, Saya turun 1701, dan memandang rendah. Dan jika saya melihat semburan Yale dicat ke tanah, kemudian Saya tahu Yale wujud di indone ini. Mari kita buat satu lagi. Mari kita memasukkan Dartmouth ke dalam ini indone, yang ditubuhkan pada 1769. 

Bermula dari akar lagi. Digit pertama saya kunci saya ialah 1. Saya boleh bergerak ke bawah jalan itu. Yang telah wujud. Digit seterusnya utama saya ialah 7. Saya boleh bergerak ke bawah jalan itu. Ia wujud juga. 

Berikut saya ialah 6. Dari sini, dari mana saya kini sedang kuning di sana pada nod pertengahan, 6 sedang dikunci off. Jika saya mahu pergi ke jalan itu, Saya perlu membina sendiri. Jadi saya akan malloc nod baru dan mempunyai 6 titik di sana. Dan kemudian, sekali lagi, saya menjulang-julang laluan baru di sini. 

Jadi saya malloc nod baru supaya dari bahawa bilangan jalan node-- 9-- dan kemudian sekarang jika saya melakukan perjalanan 1769, dan saya melihat ke bawah. Tiada apa-apa pada masa ini semburan dicat di sana. Saya boleh menulis Dartmouth. Dan saya telah dimasukkan Dartmouth ke indone itu. 

Jadi itulah memasukkan sesuatu ke dalam indone itu. Sekarang kita mahu untuk mencari sesuatu. Bagaimana kita mencari perkara-perkara di indone itu? Nah, ia cukup banyak idea yang sama. Sekarang kita hanya menggunakan digit kunci untuk melihat jika kita boleh menavigasi dari akar di mana kita mahu pergi di indone itu. 

Jika kita menemui jalan buntu pada bila-bila, maka kita tahu bahawa elemen yang tidak boleh wujud atau lain jalan yang akan telah pun dibersihkan. Jika kita membuat semuanya jalan ke akhirnya, semua perlu kita lakukan adalah melihat ke bawah dan melihat jika itu unsur yang kami cari. Jika ia, kejayaan. Jika tidak, gagal. 

Jadi mari kita mencari Harvard di indone ini. Kami bermula dari akar. Dan, sekali lagi, kita akan mewujudkan penunjuk penyusuran untuk melakukan tindakan kami untuk kita. Dari akar kita tahu bahawa Tempat pertama kita perlu pergi adalah 1, kita boleh berbuat demikian? Ya kami boleh. Jika selamat wujud. Kita boleh pergi ke sana. 

Sekarang, tempat yang akan datang kita perlu pergi adalah 6. Adakah jalan yang 6 wujud dari sini? Ya, ia tidak. Kita boleh pergi ke jalan yang 6. Dan kita berakhir di sini. 

Bolehkah kita pergi ke jalan yang 3 dari sini? Nah, kerana ia ternyata, ya, yang wujud juga. Dan kita boleh mendapatkan di jalan yang 6 dari sini? Ya kami boleh. 

Kami tidak cukup menjawab soalan lagi. Masih ada satu lagi langkah, yang kini kita perlu melihat ke bawah dan melihat jika itu actually-- jika kita mencari Harvard, adalah bahawa apa yang kita dapati selepas kita menghabiskan kunci? Dalam contoh yang kami gunakan di sini, tahun-tahun sentiasa empat digit. Tetapi anda mungkin menggunakan contoh di mana anda menyimpan sebuah kamus kata-kata. 

Dan sebagainya daripada harus 10 petunjuk lokasi saya, anda mungkin mempunyai 26. Satu untuk setiap huruf abjad. Dan terdapat beberapa perkataan seperti kelawar, yang merupakan subset kelompok, sebagai contoh. Dan sebagainya walaupun anda sampai ke akhir utama dan anda melihat ke bawah, anda mungkin tidak melihat apa yang anda cari. 

Jadi, anda sentiasa perlu merentasi keseluruhan jalan dan kemudian jika anda berjaya dapat untuk merentasi keseluruhan jalan, melihat ke bawah dan lakukan salah satu pengesahan akhir. Adakah itu apa yang saya cari? Well, saya melihat ke bawah selepas memulakan di bahagian atas dan akan 1636. Saya melihat ke bawah. Saya melihat Harvard. Jadi, ya, saya berjaya. Bagaimana jika apa yang saya cari tidak di indone, walaupun. Bagaimana jika saya mencari Princeton, yang ditubuhkan pada 1746. Dan sebagainya 1746 menjadi kunci saya untuk menavigasi melalui indone itu. Well, saya bermula dari akar. Dan tempat pertama yang saya mahu untuk pergi ke jalan yang 1. Bolehkah saya melakukannya? Ya saya boleh. 

Bolehkah saya pergi ke jalan yang 7 dari sana? Ya, saya boleh. Yang wujud juga. Tetapi saya boleh turun 4 jalan dari sini? Itu seperti bertanya soalan, boleh Saya teruskan turun yang sedikit persegi bahawa saya telah ditonjolkan dalam kuning? Tiada apa-apa di sana. Betul. 

Tidak ada cara ke hadapan ke jalan yang 4. Jika Princeton berada di indone ini, bahawa 4 akan telah dibersihkan untuk kita sudah. Dan sebagainya pada ketika ini kita telah mencapai jalan buntu. Kita tidak boleh pergi mana-mana lagi. Dan dengan itu kita boleh berkata, secara muktamad, tidak. Princeton tidak wujud dalam indone ini. 

Jadi apakah ini semua bermakna? Betul. Ada banyak berlaku di sini. Ada petunjuk di seluruh tempat. Dan, seperti yang anda lihat hanya dari rajah, ada banyak nod yang adalah sejenis terbang di sekitar. Tetapi perhatikan setiap kali kita mahu memeriksa sama ada sesuatu yang tidak di indone itu, kita hanya perlu membuat 4 bergerak. 

Setiap kali kita mahu memasukkan sesuatu di indone itu, kita perlu membuat 4 bergerak, mungkin mallocing beberapa barangan di sepanjang jalan. Tetapi seperti yang kita lihat apabila kita dimasukkan Dartmouth ke indone itu, kadang-kadang beberapa jalan mungkin sudah dibersihkan untuk kita. Dan supaya indone kita mendapat lebih besar dan lebih besar, kita perlu melakukan kerja yang kurang setiap kali untuk memasukkan perkara-perkara baru kerana kami telah pun membina banyak perantaraan cawangan di sepanjang jalan. Jika kita hanya pernah perlu melihat 4 perkara, 4 hanya pemalar. Kami benar-benar adalah sejenis menghampiri masa kemasukan berterusan dan masa pencarian yang berterusan. Tradeoff, sudah tentu, adalah bahawa indone ini, seperti yang anda mungkin boleh memberitahu, adalah besar. Setiap nod ini mengambil banyak ruang. 

Tetapi itu pengimbangan. Jika kita mahu benar-benar cepat kemasukan, penghapusan benar-benar cepat, dan lookup benar-benar cepat, kita perlu mempunyai banyak data terbang di sekitar. Kita perlu mengetepikan banyak ruang dan memori untuk struktur data wujud. 

Dan supaya pengimbangan. Tetapi ia kelihatan seperti kita mungkin telah menjumpainya. Kita mungkin telah mendapati bahawa kaedah berpotensi suci struktur data dengan kemasukan cepat, penghapusan, dan carian. Dan mungkin ini akan menjadi satu struktur data yang sesuai untuk digunakan untuk apa-apa maklumat kami cuba untuk menyimpan. Saya Doug Lloyd, ini adalah cs50.