[Bermain muzik]
>> DOUG LLOYD: Sekarang anda tahu banyak tentang tatasusunan,
dan anda tahu banyak tentang senarai berkaitan.
Dan kami telah membincangkan kebaikan dan keburukan, kami telah
dibincangkan itu diikat senarai boleh mendapatkan lebih besar dan lebih kecil,
tetapi mereka mengambil saiz lebih.
Tatasusunan adalah lebih mudah untuk digunakan, tetapi ia terbatas dalam sebanyak
kerana kita perlu menetapkan saiz array pada awal-awal
dan kemudian kita terjebak dengannya.
>> Tetapi itu, kami telah cukup banyak habis semua topik kami
tentang senarai berkaitan dan array.
Atau adakah kita?
Mungkin kita boleh melakukan sesuatu lebih kreatif.
Dan yang jenis Bei idea jadual hash.
>> Jadi dalam jadual hash kita akan cuba menggabungkan array dengan senarai berpaut.
Kami akan mengambil kelebihan array, seperti akses rawak,
dapat hanya pergi ke lokasi elemen 4 atau pelbagai elemen 8
tanpa perlu melelar seluruh.
Itu cukup pantas, bukan?
>> Tetapi kita juga mahu mempunyai data kami struktur dapat berkembang dan mengecut.
Kita tidak perlu, kita tidak mahu terhad.
Dan kita mahu dapat untuk menambah dan menghapuskan perkara-perkara
sangat mudah, yang jika anda masih ingat, adalah sangat kompleks dengan pelbagai.
Dan kita boleh memanggil ini perkara yang baru jadual hash.
>> Dan jika dilaksanakan dengan betul, kita semacam mengambil
kelebihan kedua-dua data struktur yang telah anda lihat,
tatasusunan dan senarai berkaitan.
Insertion boleh mula cenderung ke arah theta 1.
Theta kita belum benar-benar dibincangkan, tetapi theta adalah hanya kes-rata,
apa yang sebenarnya akan berlaku.
Anda tidak sentiasa akan mempunyai kes yang teruk,
dan anda tidak sentiasa akan mempunyai senario kes terbaik, jadi apa yang
senario purata?
>> Well yang kemasukan purata ke dalam jadual hash
boleh mula untuk mendapatkan dekat dengan masa yang berterusan.
Dan penghapusan boleh mendapatkan dekat dengan masa yang berterusan.
Dan lookup boleh mendapatkan dekat dengan masa yang berterusan.
That's-- kita tidak mempunyai data struktur lagi yang boleh berbuat demikian,
dan sebagainya ini sudah kedengaran seperti satu perkara yang cukup besar.
Kami benar-benar telah mengurangkan kekurangan masing-masing dengan sendiri.
>> Untuk mendapatkan prestasi ini menaik taraf walaupun, kita
perlu memikirkan semula bagaimana kita menambah data ke dalam struktur.
Secara khusus kita mahu data sendiri untuk memberitahu kami
di mana ia harus pergi dalam struktur.
Dan jika kita kemudian perlu untuk melihat jika ia dalam struktur, jika kita perlu untuk mencari,
kita mahu melihat data lagi dan dapat berkesan,
dengan menggunakan data, secara rawak mengaksesnya.
Hanya dengan melihat data kita perlu ada
idea di mana sebenarnya kami akan merasa dalam jadual hash.
>> Sekarang Kelemahan hash meja adalah bahawa mereka benar-benar
cukup buruk di pesanan atau menyusun data.
Dan sebenarnya, jika anda mula untuk menggunakan mereka untuk memerintahkan atau jenis
data anda kehilangan semua kelebihan anda sebelum ini
mempunyai dari segi kemasukan dan pemadaman.
Masa itu menjadi lebih dekat dengan theta n, dan kami telah pada dasarnya
mundur ke dalam senarai berpaut.
Dan dengan itu kita hanya ingin menggunakan hash jadual jika kita tidak mengambil berat tentang
sama ada data disusun.
Bagi konteks di mana anda akan menggunakannya dalam CS50
anda mungkin tidak peduli bahawa data yang disusun.
>> Jadi jadual hash adalah kombinasi dua keping yang berbeza
yang kita sudah biasa.
Yang pertama adalah fungsi, yang kita biasanya memanggil fungsi hash.
Dan bahawa fungsi hash akan kembali beberapa integer bukan negatif, yang
kita biasanya memanggil Kodcincang yang, OK?
Sekeping kedua adalah pelbagai, yang mampu menyimpan data kita jenis yang
mahu untuk meletakkan ke dalam struktur data.
Kami akan bertahan pada yang dikaitkan unsur senarai buat masa ini
dan hanya mula dengan asas-asas yang hash meja untuk mendapatkan kepala anda di sekitarnya,
dan kemudian kita mungkin akan meniup minda anda sedikit apabila kita
menggabungkan tatasusunan dan senarai pautan bersama-sama.
>> Idea asas walaupun adalah kita mengambil data.
Kami menjalankan data bahawa melalui fungsi hash.
Dan supaya data tersebut diproses dan ia memuntahkannya keluar nombor, OK?
Dan kemudian dengan jumlah itu kita hanya menyimpan data
kami mahu menyimpan dalam lokasi di lokasi tersebut.
Jadi, sebagai contoh kita ada mungkin ini jadual hash rentetan.
Ia mempunyai 10 elemen di dalamnya, supaya kita boleh memuatkan 10 tali di dalamnya.
>> Katakan kita mahu hash John.
Lalu ia sebagai data yang kami mahu memasukkan ke dalam jadual hash ini di suatu tempat.
Di mana kita meletakkan ia?
Well biasanya dengan lokasi setakat ini kita mungkin
akan memasukkannya ke dalam pelbagai lokasi 0.
Tetapi sekarang kita mempunyai fungsi hash baru ini.
>> Dan mari kita mengatakan bahawa kita menjalankan John melalui fungsi hash ini
dan ia memuntahkannya keluar 4.
Nah itulah di mana kita berada akan mahu untuk meletakkan John.
Kami mahu meletakkan John di lokasi array 4, kerana jika kita hash John again--
katakan kemudian kami ingin mencari dan melihat
jika John wujud dalam hash ini table-- semua yang perlu kita lakukan
dijalankan melalui hash yang sama fungsi, dapatkan nombor 4,
dan dapat mencari John serta-merta dalam struktur data kami.
Yang cukup baik.
>> Katakan sekarang kita melakukan ini lagi, kami mahu hash Paul.
Kami mahu menambah Paul ke dalam jadual hash ini.
Mari kita mengatakan bahawa kali ini kita menjalankan Paul melalui fungsi hash,
Kodcincang yang dihasilkan adalah 6.
Sekarang kita boleh meletakkan Paul di lokasi array 6.
Dan jika kita perlu melihat ke atas sama ada Paul dalam jadual hash ini,
semua yang perlu kita lakukan adalah menjalankan Paul melalui fungsi hash lagi
dan kami akan mendapat 6 lagi.
>> Dan kemudian kita hanya melihat di lokasi lokasi 6.
Paul di sana?
Jika ya, dia dalam jadual hash.
Paul tidak ada?
Dia bukan dalam jadual hash.
Ia agak mudah.
>> Sekarang bagaimana anda menentukan fungsi hash?
Nah ada benar-benar tiada had untuk beberapa fungsi hash mungkin.
Malah ada beberapa benar-benar, orang-orang yang benar-benar baik di internet.
Ada beberapa benar-benar, orang-orang yang benar-benar buruk di internet.
Ia juga agak mudah menulis satu yang tidak baik.
>> Jadi apa yang membuat sehingga baik yang fungsi hash, bukan?
Well fungsi hash yang baik perlu menggunakan hanya data yang dicincang,
dan semua data yang dicincang.
Oleh itu, kita tidak mahu menggunakan sesuatupun kita tidak menggabungkan apa-apa
lain selain daripada data.
Dan kita mahu menggunakan semua data.
Kita tidak mahu hanya menggunakan sekeping itu, kita mahu menggunakan semua itu.
Satu fungsi hash perlu juga menjadi berketentuan.
Apa maksudnya?
Baik ia bermakna bahawa setiap kali kita lulus bahagian yang sama dalam data
ke dalam fungsi hash kita sentiasa mendapatkan Kodcincang yang sama keluar.
Jika saya lulus John ke dalam fungsi hash saya keluar 4.
Saya akan dapat berbuat demikian 10000 kali dan saya akan sentiasa mendapat 4.
Jadi tiada nombor rawak berkesan boleh terlibat dalam hash kami tables--
dalam fungsi hash kami.
>> Satu fungsi hash juga perlu seragam mengedarkan data.
Jika setiap kali anda menjalankan data melalui fungsi hash anda Kodcincang 0,
itu mungkin tidak begitu besar, bukan?
Anda mungkin mahu besar pelbagai kod hash.
Juga perkara yang boleh merebak di seluruh meja.
Dan juga ia akan menjadi besar jika benar-benar data yang sama, seperti John dan Jonathan,
mungkin telah tersebar untuk menimbang lokasi yang berbeza dalam jadual hash.
Itu akan menjadi satu kelebihan yang bagus.
>> Berikut adalah satu contoh fungsi hash.
Saya menulis satu ini sehingga awal.
Ia bukan satu terutamanya fungsi hash baik
atas sebab-sebab yang tidak benar-benar menanggung pergi ke sekarang.
Tetapi adakah anda melihat apa yang berlaku di sini?
Ia seolah-olah seperti kita mengisytiharkan pembolehubah yang dipanggil jumlah dan menetapkan ia sama dengan 0.
Dan kemudian nampaknya saya melakukan sesuatu selagi strstr [j] tidak sama
untuk Backslash 0.
Apa yang saya buat di sana?
>> Ini adalah pada dasarnya hanya satu lagi cara melaksanakan [? Strl?]
dan mengesan apabila anda telah sampai ke penghujung tali.
Jadi, saya tidak mempunyai untuk benar-benar hitungkan panjang tali,
Saya hanya menggunakan apabila saya memukul garis miring 0 watak saya tahu
Saya telah sampai ke penghujung tali.
Dan kemudian saya akan terus iterating melalui tali itu,
menambah strstr [j] untuk kesimpulan, dan kemudian di akhirnya akan kembali mod jumlah
HASH_MAX.
>> Pada dasarnya semua hash ini fungsi yang dilakukan adalah menambah sehingga
semua nilai-nilai ASCII rentetan saya, dan kemudian ia
kembali beberapa Kodcincang modded oleh HASH_MAX.
Ia mungkin saiz array saya, bukan?
Saya tidak mahu mendapat hash Kod jika pelbagai saya adalah saiz 10,
Saya tidak mahu menjadi semakin Kod hash daripada 11, 12,
13, saya tidak boleh meletakkan sesuatu ke dalam lokasi-lokasi array,
yang menyalahi undang-undang.
Saya sedang menderita kesalahan segmentasi.
>> Sekarang di sini adalah satu lagi cepat diketepikan.
Secara amnya anda mungkin tidak akan mahu menulis fungsi hash anda sendiri.
Ia sebenarnya sedikit satu seni, bukannya sains.
Dan ada banyak yang masuk ke dalam mereka.
Internet, seperti saya katakan, penuh fungsi hash benar-benar baik,
dan anda perlu menggunakan internet untuk mencari fungsi hash kerana ia benar-benar
hanya jenis yang tidak perlu membuang masa untuk membuat anda sendiri.
>> Anda boleh menulis yang mudah untuk tujuan ujian.
Tetapi apabila anda benar-benar akan mula hashing data dan menyimpannya
ke dalam jadual hash anda mungkin akan mahu
untuk menggunakan beberapa fungsi yang telah dijana untuk anda, yang wujud di internet.
Jika anda hanya pastikan memetik sumber anda.
Tidak ada sebab untuk memplagiat apa-apa di sini.
>> Komuniti sains komputer adalah pasti semakin meningkat, dan benar-benar nilai-nilai
sumber terbuka, dan ia benar-benar penting memetik sumber anda supaya orang ramai
boleh mendapatkan pengiktirafan untuk kerja-kerja yang mereka
lakukan untuk memberi manfaat kepada masyarakat.
Jadi sentiasa sure-- dan bukan hanya untuk hash
fungsi, tetapi secara umumnya apabila anda menggunakan kod dari sumber luar,
sentiasa memetik sumber anda.
Memberi kredit kepada orang yang melakukan beberapa kerja supaya anda tidak perlu.
>> OK jadi mari kita melihat semula ini jadual hash untuk kali kedua.
Ini adalah di mana kita meninggalkan kira selepas kita dimasukkan
Yohanes dan Paulus ke dalam jadual hash ini.
Adakah anda melihat masalah di sini?
Anda mungkin melihat dua.
Tetapi khususnya, adakah anda melihat masalah ini boleh terjadi?
>> Bagaimana jika saya hash Ringo, dan ia Ternyata selepas pemprosesan
data yang melalui fungsi hash Ringo juga menjana Kodcincang 6.
Saya telah mendapat data pada lokasi mudah hashcode-- 6.
Oleh itu, ia mungkin akan menjadi sedikit satu masalah bagi saya sekarang, bukan?
>> Kami memanggil ini perlanggaran.
Dan perlanggaran itu berlaku apabila dua bahagian data dijalankan melalui hash yang sama
fungsi menghasilkan Kodcincang yang sama.
Mungkin kita masih mahu mendapatkan kedua-dua bahagian data ke dalam jadual hash,
jika tidak kami tidak akan berjalan Ringo sewenang-wenangnya melalui fungsi hash.
Kami mungkin ingin mendapatkan Ringo ke dalam pelbagai itu.
>> Bagaimana kita melakukannya walaupun, jika dia dan Paul kedua-dua hasil Kodcincang 6?
Kami tidak mahu menulis ganti Paul, kita mahu Paul untuk berada di sana juga.
Oleh itu, kita perlu mencari cara untuk mendapatkan unsur-unsur ke dalam jadual hash yang
masih mengekalkan cepat kami kemasukan dan pandangan yang cepat naik.
Dan salah satu cara untuk berurusan dengan ia adalah untuk melakukan sesuatu yang dinamakan linear menyelesaikan sesuatu.
>> Dengan menggunakan kaedah ini jika kita mempunyai perlanggaran, baik, apa yang kita lakukan?
Baik kita tidak boleh meletakkan dia di lokasi array 6, atau apa sahaja Kodcincang telah dijana,
mari kita meletakkan dia di Kodcincang campur 1.
Dan jika itu let penuh itu memasukkannya ke dalam Kodcincang campur 2.
Manfaat makhluk ini jika dia tidak betul-betul di mana kita fikir dia adalah,
dan kita perlu mula mencari, mungkin kita tidak perlu pergi terlalu jauh.
Mungkin kita tidak perlu mencari semua n unsur-unsur jadual hash.
Mungkin kita perlu mencari beberapa daripada mereka.
>> Dan dengan itu kita masih cenderung ke arah bahawa kes purata yang hampir dengan 1 vs
berhampiran dengan n, jadi mungkin yang akan bekerja.
Jadi mari kita lihat bagaimana ini mungkin bekerja di dalam realiti.
Dan mari kita lihat jika mungkin kita dapat mengesan masalah yang mungkin berlaku di sini.
>> Katakan kita hash Bart.
Jadi sekarang kita akan menjalankan satu set baru tali melalui fungsi hash,
dan kami menjalankan Bart melalui hash fungsi, kita akan mendapat Kodcincang 6.
Kita lihat, kita lihat 6 adalah kosong, jadi kita boleh meletakkan Bart di sana.
>> Sekarang kita hash Lisa dan juga menjana Kodcincang 6.
Sekarang bahawa kita menggunakan ini linear kaedah yang kami bermula pada 6 menyelesaikan sesuatu,
kita lihat bahawa 6 penuh.
Kita tidak boleh meletakkan Lisa dalam 6.
Jadi di mana kami akan pergi?
Mari kita pergi ke 7.
7 ini kosong, jadi yang bekerja.
Jadi mari kita meletakkan Lisa sana.
>> Sekarang kita hash Homer dan kita akan mendapat 7.
OK juga kita tahu bahawa 7 ini penuh sekarang, jadi kita tidak boleh meletakkan Homer di sana.
Oleh itu, marilah kita pergi ke 8.
Adalah 8 yang ada?
Ya, dan 8 ini hampir 7, jadi jika kita perlu mula mencari kami
tidak akan perlu pergi terlalu jauh.
Dan begitu mari kita meletakkan Homer di 8.
>> Sekarang kita hash Maggie dan mengembalikan 3, syukurlah
kami dapat hanya meletakkan Maggie di sana.
Kami tidak mempunyai melakukan apa-apa semacam menyelesaikan sesuatu untuk itu.
Sekarang kita hash Marge, dan Marge juga mengembalikan 6.
>> Well 6 penuh, 7 adalah penuh, 8 adalah penuh, 9, baiklah bersyukur kepada Tuhan, 9 kosong.
Saya boleh meletakkan Marge di 9.
Sudah kita boleh melihat bahawa kita bermula mempunyai masalah ini di mana kini kami
mula menghulurkan sesuatu jenis daripada jauh dari kod hash mereka.
Dan itu theta 1, purata yang kes menjadi masa yang berterusan,
mula mendapat more-- sedikit mula cenderung sedikit lebih
ke arah theta n.
Kami mula kehilangan yang Gunakan jadual hash.
>> Masalah ini yang kita hanya melihat adalah sesuatu yang dinamakan kelompok.
Dan apa yang benar-benar buruk tentang kelompok adalah bahawa apabila anda sekarang
mempunyai dua elemen yang sebelah sisi ia menjadikannya lebih mungkin lagi,
anda mempunyai dua kali ganda kebetulan, bahawa anda akan
untuk mempunyai perlanggaran lain dengan kelompok itu,
dan kluster akan berkembang sebanyak satu.
Dan anda akan terus berkembang dan berkembang kemungkinan anda mempunyai perlanggaran.
Dan akhirnya ia hanya sebagai lapuk tidak menyusun data pada semua.
>> Masalah lain walaupun adalah kita masih, dan setakat ini sehingga ke tahap ini,
kita baru sahaja menjadi semacam memahami apa jadual hash adalah,
kita masih hanya mempunyai ruang untuk 10 tali.
Jika kita mahu terus hash warga Springfield,
kita hanya boleh mendapat 10 daripada mereka di sana.
Dan jika kita cuba dan menambah ke-11 atau ke-12, kita tidak mempunyai tempat untuk meletakkan mereka.
Kami hanya boleh berputar di sekitar dalam bulatan cuba untuk mencari tempat kosong,
dan kita mungkin terjebak dalam gelung tak terhingga.
>> Jadi seperti ini meminjamkan kepada idea sesuatu yang dinamakan chaining.
Dan di sinilah kita akan membawa senarai berkaitan kembali ke dalam gambar.
Bagaimana jika sebaliknya menyimpan hanya data itu sendiri dalam array,
setiap elemen array boleh memegang beberapa keping data?
Baik yang tidak masuk akal, bukan?
Kita tahu bahawa array hanya boleh hold-- setiap elemen array
hanya boleh memegang satu bahagian daripada data yang jenis data.
>> Tetapi bagaimana jika yang jenis data senarai berpaut, bukan?
Jadi apa jika setiap elemen array adalah
penunjuk kepada ketua senarai berpaut?
Dan kemudian kita boleh membina mereka senarai berkaitan
dan berkembang mereka sewenang-wenangnya, kerana senarai berkaitan membolehkan
kami berkembang dan mengecut banyak lagi fleksibel daripada array tidak.
Jadi apa jika kita gunakan, kami memanfaatkan ini, bukan?
Kami mula berkembang rantaian ini daripada lokasi ini pelbagai.
>> Sekarang kita boleh memuatkan sebuah terhingga jumlah data, atau tidak terhingga,
satu jumlah yang sewenang-wenangnya data, ke dalam jadual hash kami
tanpa pernah berjalan ke masalah perlanggaran.
Kami juga telah dihapuskan kelompok dengan melakukan ini.
Dan juga kita tahu bahawa apabila kita memasukkan ke dalam senarai berpaut, jika anda masih ingat
dari video kami pada senarai berkaitan, secara tunggal senarai berkaitan dan senarai duanya adalah terpakai dikaitkan,
ia adalah satu operasi masa yang berterusan.
Kami hanya menambah ke hadapan.
>> Dan untuk melihat ke atas, baik kita tahu yang kelihatan dalam senarai berpaut
boleh menjadi masalah, bukan?
Kita perlu mencari melalui dari awal hingga akhir.
Tidak ada rawak akses dalam senarai berpaut.
Tetapi jika bukan mempunyai satu berkaitan senarai di mana pencarian akan menjadi O n,
kami kini mempunyai 10 senarai berkaitan, atau 1,000 senarai berkaitan,
kini tiba O n dibahagikan dengan 10, atau O n dibahagikan dengan 1,000.
>> Dan ketika kita bercakap secara teori tentang kerumitan
kita tidak mengambil kira pemalar, dalam keadaan nyata dunia perkara-perkara ini benar-benar penting,
bukan?
Kami benar-benar akan melihat bahawa ini berlaku
untuk menjalankan 10 kali lebih cepat, atau 1,000 kali lebih cepat,
kerana kita mengedarkan satu panjang rantaian seluruh 1000 rantaian yang lebih kecil.
Dan supaya setiap kali kita perlu mencari melalui salah satu rantai yang kita boleh
mengabaikan 999 rantaian kita tidak peduli tentang, dan hanya mencari yang satu.
>> Yang rata-rata untuk 1,000 kali lebih pendek.
Dan dengan itu kita masih adalah jenis cenderung ke arah kes purata ini
menjadi masa yang berterusan, tetapi hanya kerana kita memanfaatkan
membahagikan oleh beberapa faktor yang tetap besar.
Mari kita lihat bagaimana mungkin ini benar-benar melihat walaupun.
Jadi ini adalah jadual hash kami terpaksa sebelum kita mengisytiharkan jadual hash yang
mampu menyimpan 10 tali.
Kami tidak akan melakukannya lagi.
Kami sudah tahu batasan kaedah itu.
Sekarang jadual hash kami akan menjadi pelbagai 10 nod, petunjuk
kepada ketua-ketua senarai berkaitan.
>> Dan sekarang ia null.
Setiap seorang daripada mereka 10 petunjuk adalah batal.
Tiada apa-apa dalam kita hash meja sekarang.
>> Sekarang mari kita mulakan untuk meletakkan beberapa sesuatu ke dalam jadual hash ini.
Dan mari kita lihat bagaimana kaedah ini adalah akan memberi manfaat kepada kita sedikit.
Sekarang mari kita hash Joey.
Kami akan akan berjalan tali Joey melalui fungsi hash dan kita kembali 6.
Juga apa yang kita buat sekarang?
>> Sekarang bekerja dengan senarai berkaitan, kita tidak bekerja dengan tatasusunan.
Dan apabila kita bekerja dengan senarai berkaitan kita
tahu kita perlu bermula secara dinamik memperuntukkan ruang dan bangunan rantai.
Itulah jenis how-- mereka adalah teras unsur-unsur membina senarai berpaut.
Jadi mari kita secara dinamik memperuntukkan ruang untuk Joey,
dan kemudian mari kita menambah beliau untuk rantai.
>> Jadi sekarang melihat apa yang kita lakukan.
Apabila kita hash Joey kami mendapat Kodcincang 6.
Sekarang penunjuk di lokasi lokasi 6 menunjuk kepada ketua senarai berpaut,
dan sekarang ia satu-satunya unsur senarai berpaut.
Dan simpulan dalam itu senarai berpaut adalah Joey.
>> Jadi, jika kita perlu mencari Joey kemudian, kita hanya hash Joey sekali lagi,
kita akan mendapat 6 lagi kerana kami fungsi hash adalah berketentuan.
Dan kemudian kita mula di kepala senarai dikaitkan menegaskan
untuk mengikut lokasi mudah 6, dan kita boleh melelar
seluruh yang cuba untuk mencari Joey.
Dan jika kita membina kami hash meja dengan berkesan,
dan fungsi hash kami dengan berkesan untuk mengedarkan data dengan baik,
secara purata setiap orang-orang yang berkaitan senarai di setiap lokasi mudah
akan menjadi 1/10 saiz jika kita hanya mempunyai ia sebagai besar tunggal
senarai dikaitkan dengan segala isinya.
>> Jika kita mengagihkan yang besar berkaitan senarai di 10 senarai berkaitan
setiap senarai akan menjadi 1/10 saiz.
Dan dengan itu 10 kali lebih cepat untuk mencari melalui.
Jadi mari kita buat ini lagi.
Sekarang mari kita hash Ross.
>> Dan katakan Ross, apabila kita berbuat demikian kod hash kita kembali ialah 2.
Sekarang kita dinamik memperuntukkan nod baru, kita meletakkan Ross dalam nod itu,
dan kami katakan sekarang lokasi mudah 2, bukan menunjuk ke batal,
menunjuk kepada ketua berpaut senarai yang nod sahaja Ross.
Dan yang boleh kita lakukan satu-satu masa ini lagi, kami boleh hash Rachel dan mendapatkan Kodcincang 4.
malloc nod baru, meletakkan Rachel dalam nod, dan berkata lokasi mudah
4 kini menghala ke kepala daripada senarai berpaut yang
hanya unsur kebetulan Rachel.
>> OK, tetapi apa yang berlaku jika kita ada perlanggaran?
Mari kita lihat bagaimana kita mengendalikan perlanggaran menggunakan kaedah chaining yang berasingan.
Mari kita hash Phoebe.
Kita mendapat Kodcincang 6.
Dalam contoh kami sebelum ini kami hanya menyimpan tali dalam array.
Ini adalah masalah.
>> Kami tidak mahu memukul berkali-kali Joey, dan kami telah pun
dilihat bahawa kita boleh mendapatkan beberapa kelompok masalah jika kita cuba dan langkah
melalui dan siasatan.
Tetapi bagaimana jika kita hanya jenis merawat ini dengan cara yang sama, bukan?
Ia hanya seperti menambah unsur kepada ketua senarai berpaut.
Mari kita ruang hanya malloc untuk Phoebe.
>> Kami akan berkata mata penunjuk Phoebe seterusnya ke kepala lama senarai berkaitan,
dan kemudian hanya 6 mata kepada Ketua baru senarai berkaitan.
Dan kini melihat, kami telah berubah Phoebe masuk.
Kami kini boleh menyimpan dua unsur-unsur dengan Kodcincang 6,
dan kami tidak mempunyai sebarang masalah.
>> Yang cukup banyak semua ada untuk rantaian.
Dan chaining pasti kaedah itu
akan menjadi yang paling berkesan untuk anda jika anda sedang menyimpan data dalam jadual hash.
Tetapi gabungan ini tatasusunan dan senarai berkaitan
bersama-sama untuk membentuk satu jadual hash benar-benar dramatik meningkatkan keupayaan anda
untuk menyimpan data yang banyak, dan dengan cepat dan cekap mencari
melalui data tersebut.
>> Masih ada satu lagi struktur data di luar sana
bahawa walaupun mungkin agak lebih baik dari segi jaminan
bahawa kemasukan kami, penghapusan, dan memandang masa adalah lebih cepat.
Dan kita akan melihat bahawa dalam video di cuba.
Saya Doug Lloyd, ini adalah CS50.