[MUSIC PLAYING]
>> Doug LLOYD: Sekarang Anda tahu banyak tentang array,
dan Anda tahu banyak tentang daftar terkait.
Dan kita sudah membahas pro dan kontra, kami telah
membahas bahwa terkait daftar bisa mendapatkan lebih besar dan lebih kecil,
tetapi mereka mengambil lebih banyak ukuran.
Array jauh lebih mudah untuk menggunakan, tapi mereka membatasi sebanyak
seperti yang kita harus mengatur ukuran array pada awal
dan kemudian kita terjebak dengan itu.
>> Tapi itu, kita sudah cukup banyak habis semua topik kami
tentang daftar terhubung dan array.
Atau harus kita?
Mungkin kita bisa melakukan sesuatu bahkan lebih kreatif.
Dan hal semacam meminjamkan ide tabel hash.
>> Jadi dalam tabel hash kita akan mencoba menggabungkan array dengan linked list.
Kami akan mengambil keuntungan dari array, seperti akses acak,
bisa hanya pergi ke berbagai Elemen 4 atau array elemen 8
tanpa harus beralih di.
Itu cukup cepat, tepat?
>> Tapi kami juga ingin memiliki data kami struktur dapat tumbuh dan menyusut.
Kita tidak perlu, kita tidak ingin dibatasi.
Dan kami ingin dapat untuk menambah dan menghapus hal-hal
sangat mudah, yang jika Anda ingat, sangat kompleks dengan array.
Dan kita bisa menyebutnya hal baru tabel hash.
>> Dan jika diterapkan dengan benar, kita semacam mengambil
keuntungan baik data struktur Anda sudah melihat,
array dan daftar terkait.
Penyisipan dapat mulai cenderung ke arah theta dari 1.
Theta kita belum benar-benar dibahas, tapi theta hanya kasus rata-rata,
apa yang sebenarnya akan terjadi.
Anda tidak selalu akan memiliki skenario kasus terburuk,
dan Anda tidak akan selalu memiliki skenario kasus terbaik, jadi apa
skenario rata-rata?
>> Nah penyisipan rata ke dalam tabel hash
dapat mulai mendekati waktu konstan.
Dan penghapusan bisa mendapatkan dekat dengan waktu konstan.
Dan lookup bisa mendapatkan dekat dengan waktu konstan.
That's-- kita tidak memiliki data Struktur belum yang dapat melakukan itu,
dan jadi ini sudah terdengar seperti hal yang cukup besar.
Kami telah benar-benar meringankan kekurangan masing-masing sendiri.
>> Untuk mendapatkan kinerja ini meng-upgrade meskipun, kita
perlu memikirkan kembali bagaimana kita menambahkan data ke dalam struktur.
Secara khusus kami ingin Data itu sendiri untuk memberitahu kami
di mana ia harus pergi dalam struktur.
Dan jika kita kemudian harus melihat apakah itu di struktur, jika kita harus menemukannya,
kita ingin melihat data lagi dan dapat secara efektif,
menggunakan data, secara acak mengaksesnya.
Hanya dengan melihat Data kita harus memiliki
ide dari mana tepatnya kami akan menemukannya dalam tabel hash.
>> Sekarang downside dari hash tabel adalah bahwa mereka benar-benar
sangat buruk di memesan atau menyortir data.
Dan pada kenyataannya, jika Anda mulai menggunakannya untuk memesan atau semacam
Data Anda kehilangan semua keuntungan sebelumnya
memiliki segi penyisipan dan penghapusan.
Waktu menjadi lebih dekat dengan theta dari n, dan kami sudah pada dasarnya
kemunduran dalam linked list.
Dan jadi kami hanya ingin menggunakan hash tabel jika kita tidak peduli tentang
apakah data diurutkan.
Untuk konteks di mana Anda akan menggunakannya dalam CS50
Anda mungkin tidak peduli bahwa data yang diurutkan.
>> Jadi tabel hash adalah kombinasi dari dua potong yang berbeda
dengan yang kita kenal.
Yang pertama adalah fungsi, yang kita biasanya memanggil fungsi hash.
Dan bahwa fungsi hash akan kembali beberapa bilangan bulat non-negatif, yang
biasanya kita sebut kode hash, oke?
Bagian kedua adalah array, yang merupakan mampu menyimpan data jenis yang kita
ingin menempatkan ke dalam struktur data.
Kami akan menunda pada terkait elemen daftar untuk saat
dan hanya mulai dengan dasar-dasar dari hash table untuk mendapatkan kepala Anda sekitar itu,
dan kemudian kita mungkin akan meniup pikiran Anda sedikit ketika kita
menggabungkan array dan daftar link yang bersama-sama.
>> Ide dasar meskipun adalah kita mengambil beberapa data.
Kami menjalankan bahwa data melalui fungsi hash.
Dan data tersebut diolah dan meludah keluar angka, OK?
Dan kemudian dengan nomor yang kita hanya menyimpan data
kita ingin menyimpan dalam Array di lokasi tersebut.
Jadi misalnya kita harus mungkin tabel hash dari string.
Itu punya 10 elemen di dalamnya, sehingga kita bisa muat 10 string di dalamnya.
>> Katakanlah kita ingin hash John.
Jadi John sebagai data kita ingin memasukkan ke dalam tabel hash ini di suatu tempat.
Di mana kita meletakkannya?
Nah biasanya dengan Array sejauh kita mungkin
akan memasukkannya dalam array lokasi 0.
Tapi sekarang kita memiliki fungsi ini hash baru.
>> Dan mari kita mengatakan bahwa kita menjalankan John melalui fungsi hash ini
dan itu meludah keluar 4.
Nah di situlah kami akan ingin menempatkan John.
Kami ingin menempatkan John di lokasi array yang 4, karena jika kita hash John again--
katakanlah kemudian kami ingin mencari dan melihat
jika John ada di hash ini table-- semua yang perlu kita lakukan
dijalankan melalui hash yang sama fungsi, mendapatkan nomor 4 out,
dan dapat menemukan John segera dalam struktur data kami.
Itu cukup bagus.
>> Katakanlah sekarang kita melakukan ini lagi, kami ingin hash Paul.
Kami ingin menambahkan Paul ke dalam tabel hash ini.
Mari kita mengatakan bahwa saat ini kita menjalankan Paul melalui fungsi hash,
kode hash yang dihasilkan adalah 6.
Nah sekarang kita dapat menempatkan Paul di lokasi array yang 6.
Dan jika kita perlu mencari apakah Paulus dalam tabel hash ini,
semua yang perlu kita lakukan adalah menjalankan Paul melalui fungsi hash lagi
dan kita akan mendapatkan 6 keluar lagi.
>> Dan kemudian kita hanya melihat di berbagai lokasi 6.
Apakah Paulus ada?
Jika demikian, dia dalam tabel hash.
Apakah Paulus tidak ada?
Dia tidak dalam tabel hash.
Ini cukup sederhana.
>> Sekarang bagaimana Anda mendefinisikan fungsi hash?
Nah ada benar-benar ada batasan untuk sejumlah fungsi hash mungkin.
Bahkan ada sejumlah benar-benar, yang benar-benar baik di internet.
Ada sejumlah benar-benar, yang benar-benar buruk di internet.
Ini juga cukup mudah untuk menulis yang buruk.
>> Jadi apa yang membuat baik sebuah Fungsi hash, kan?
Nah fungsi hash yang baik harus hanya menggunakan data yang hashed,
dan semua data yang hashed.
Jadi kita tidak ingin menggunakan anything-- kita tidak memasukkan apa-apa
lain selain data.
Dan kita ingin menggunakan semua data.
Kami tidak ingin hanya menggunakan sepotong itu, kita ingin menggunakan semua itu.
Sebuah fungsi hash harus juga menjadi deterministik.
Maksudnya itu apa?
Nah itu berarti bahwa setiap kali kita lulus potongan yang sama persis data
ke dalam fungsi hash kami selalu mendapatkan kode hash yang sama keluar.
Jika saya melewati John ke Fungsi hash saya keluar 4.
Aku harus bisa melakukan itu 10.000 kali dan saya akan selalu mendapatkan 4.
Jadi tidak ada angka acak efektif dapat terlibat dalam hash kami tables--
dalam fungsi hash kami.
>> Sebuah fungsi hash juga harus seragam mendistribusikan data.
Jika setiap kali Anda menjalankan data melalui Fungsi hash Anda mendapatkan kode hash 0,
itu mungkin tidak begitu besar, kan?
Anda mungkin ingin besar berbagai kode hash.
Juga hal-hal dapat menyebar keluar seluruh meja.
Dan juga itu akan menjadi besar jika benar-benar data yang sama, seperti John dan Jonathan,
mungkin tersebar untuk menimbang lokasi yang berbeda dalam tabel hash.
Itu akan menjadi keuntungan yang bagus.
>> Berikut ini adalah contoh dari fungsi hash.
Aku menulis satu ini sebelumnya.
Ini bukan terutama fungsi hash yang baik
untuk alasan yang tidak benar-benar menanggung pergi ke sekarang.
Tapi apakah Anda melihat apa yang terjadi di sini?
Sepertinya kita mendeklarasikan sebuah variabel disebut sum dan pengaturannya sama dengan 0.
Dan kemudian ternyata aku melakukan sesuatu asalkan strstr [j] tidak sama
untuk backslash 0.
Apa yang saya lakukan di sana?
>> Ini pada dasarnya hanyalah cara menerapkan [? strl?]
dan mendeteksi ketika Anda sudah mencapai akhir dari string.
Jadi saya tidak harus benar-benar menghitung panjang string,
Aku hanya menggunakan ketika saya menekan backslash 0 karakter yang saya tahu
Aku telah mencapai akhir dari string.
Dan kemudian aku akan tetap iterasi melalui string yang,
menambahkan strstr [j] untuk jumlah, dan kemudian di akhir hari akan kembali sum mod
HASH_MAX.
>> Pada dasarnya semua hash ini Fungsi lakukan adalah menambahkan
semua nilai ASCII dari tali saya, dan kemudian itu
kembali beberapa kode hash modded oleh HASH_MAX.
Ini mungkin ukuran array saya, kan?
Saya tidak ingin mendapatkan hash Kode jika array saya adalah ukuran 10,
Saya tidak ingin menjadi semakin Kode hash keluar 11, 12,
13, saya tidak bisa meletakkan segala sesuatu ke lokasi tersebut dari array,
yang akan ilegal.
Saya akan menderita kesalahan segmentasi.
>> Sekarang di sini adalah lain cepat samping.
Umumnya Anda mungkin tidak akan ingin menulis fungsi hash Anda sendiri.
Hal ini sebenarnya sedikit seni, bukan ilmu.
Dan ada banyak yang masuk ke mereka.
Internet, seperti saya katakan, penuh fungsi hash benar-benar baik,
dan Anda harus menggunakan internet untuk menemukan fungsi hash karena itu benar-benar
hanya jenis yang tidak perlu buang waktu untuk membuat Anda sendiri.
>> Anda dapat menulis yang sederhana untuk tujuan pengujian.
Tetapi ketika Anda benar-benar akan mulai hashing data dan menyimpannya
ke dalam tabel hash Anda mungkin akan ingin
untuk menggunakan beberapa fungsi yang dihasilkan untuk Anda, yang ada di internet.
Jika Anda pastikan untuk mengutip sumber-sumber Anda.
Tidak ada alasan untuk menjiplak apa pun di sini.
>> Komunitas ilmu komputer adalah pasti tumbuh, dan benar-benar nilai-nilai
open source, dan itu benar-benar penting untuk mengutip sumber-sumber Anda sehingga orang
bisa mendapatkan atribusi untuk pekerjaan yang mereka
lakukan untuk kepentingan masyarakat.
Jadi selalu sure-- dan bukan hanya untuk hash
fungsi, tetapi umumnya ketika Anda menggunakan kode dari sumber luar,
selalu mengutip sumber Anda.
Memberikan kredit kepada orang yang melakukan beberapa pekerjaan sehingga Anda tidak perlu.
>> OK jadi mari kita kembali ini tabel hash untuk kedua.
Di sinilah kami meninggalkan off setelah kami dimasukkan
John dan Paul ke dalam tabel hash ini.
Apakah Anda melihat masalah di sini?
Anda mungkin melihat dua.
Tapi khususnya, apakah Anda melihat masalah ini mungkin?
>> Bagaimana jika saya hash Ringo, dan Ternyata setelah pengolahan
bahwa data melalui fungsi hash Ringo juga dihasilkan kode hash 6.
Aku sudah punya data pada hashcode-- lokasi Array 6.
Jadi itu mungkin akan menjadi sedikit dari masalah bagi saya sekarang, kan?
>> Kami menyebutnya tabrakan.
Dan tabrakan terjadi ketika dua bagian data dijalankan melalui hash yang sama
fungsi menghasilkan kode hash yang sama.
Agaknya kita masih ingin mendapatkan kedua potongan data ke dalam tabel hash,
jika tidak kita tidak akan berjalan Ringo sewenang-wenang melalui fungsi hash.
Kami mungkin ingin mendapatkan Ringo ke dalam array itu.
>> Bagaimana kita melakukannya meskipun, jika dia dan Paul kedua hasil kode hash 6?
Kami tidak ingin menimpa Paul, kami ingin Paulus berada di sana juga.
Jadi kita perlu menemukan cara untuk mendapatkan elemen ke dalam tabel hash yang
masih mempertahankan cepat kami penyisipan dan cepat melihat ke atas.
Dan salah satu cara untuk menghadapinya adalah dengan melakukan sesuatu yang disebut linear menyelidik.
>> Dengan menggunakan metode ini jika kita memiliki tabrakan, baik, apa yang kita lakukan?
Yah kita tidak bisa menempatkan dia di lokasi array yang 6, atau kode hash apa pun yang dihasilkan,
mari kita menempatkan dia di kode hash ditambah 1.
Dan jika itu penuh mari menempatkan dia di kode hash ditambah 2.
Manfaat dari keberadaan ini jika dia tidak persis di mana kita pikir dia adalah,
dan kita harus mulai mencari, mungkin kita tidak perlu pergi terlalu jauh.
Mungkin kita tidak perlu mencari semua elemen n dari tabel hash.
Mungkin kita harus mencari beberapa dari mereka.
>> Dan jadi kita masih cenderung ke arah bahwa rata-rata kasus yang dekat dengan 1 vs
dekat dengan n, jadi mungkin itu akan bekerja.
Jadi mari kita lihat bagaimana ini mungkin bekerja dalam kenyataan.
Dan mari kita lihat apakah mungkin kita bisa mendeteksi masalah yang mungkin terjadi di sini.
>> Katakanlah kita hash Bart.
Jadi sekarang kita akan menjalankan satu set baru string melalui fungsi hash,
dan kami menjalankan Bart melalui hash fungsi, kita mendapatkan kode hash 6.
Kami melihat, kita lihat 6 adalah kosong, sehingga kita dapat menempatkan Bart ada.
>> Sekarang kita hash Lisa dan yang juga menghasilkan kode hash 6.
Nah sekarang kita menggunakan ini Metode kami mulai 6 linear probing,
kita melihat bahwa 6 penuh.
Kita tidak bisa menempatkan Lisa di 6.
Jadi di mana kita pergi?
Mari kita pergi ke 7.
7 kosong, sehingga bekerja.
Jadi mari kita menempatkan Lisa ada.
>> Sekarang kita hash Homer dan kami mendapatkan 7.
OK baik kita tahu bahwa 7 yang penuh sekarang, jadi kami tidak dapat menempatkan Homer ada.
Jadi mari kita pergi ke 8.
Adalah 8 tersedia?
Ya, dan 8 yang dekat dengan 7, jadi jika kita harus memulai pencarian kita
tidak akan harus pergi terlalu jauh.
Dan mari kita menempatkan Homer pada 8.
>> Sekarang kita hash Maggie dan kembali 3, syukurlah
kami dapat hanya menempatkan Maggie ada.
Kami tidak perlu melakukan semacam menyelidik untuk itu.
Sekarang kita hash Marge, dan Marge juga kembali 6.
>> Nah 6 penuh, 7 penuh, 8 penuh, 9, semua yang benar terima kasih Tuhan, 9 kosong.
Saya dapat menempatkan Marge di 9.
Sudah kita dapat melihat bahwa kita mulai memiliki masalah ini di mana sekarang kita
mulai meregangkan hal semacam dari jauh dari kode hash mereka.
Dan bahwa theta dari 1, rata-rata yang kasus menjadi waktu yang konstan,
mulai mendapatkan more-- sedikit mulai cenderung sedikit lebih
menuju theta dari n.
Kita mulai kehilangan keuntungan dari tabel hash.
>> Masalah ini bahwa kita hanya melihat adalah sesuatu yang disebut clustering.
Dan apa yang benar-benar buruk tentang pengelompokan adalah bahwa sekali Anda sekarang
memiliki dua elemen yang berdampingan sisi itu membuatnya bahkan lebih mungkin,
Anda memiliki dua kali lipat kebetulan, bahwa Anda akan
untuk memiliki tabrakan lain dengan klaster itu,
dan cluster akan tumbuh dengan satu.
Dan Anda akan terus tumbuh dan berkembang kemungkinan Anda memiliki tabrakan.
Dan akhirnya itu hanya sebagai buruk tidak memilah data sama sekali.
>> Masalah lain meskipun adalah kita masih, dan sejauh sampai titik ini,
kami baru saja semacam memahami apa yang tabel hash adalah,
kita masih hanya memiliki ruang untuk 10 string.
Jika kita ingin terus hash warga Springfield,
kita hanya bisa mendapatkan 10 dari mereka di sana.
Dan jika kita mencoba dan menambahkan 11 atau 12, kita tidak memiliki tempat untuk menempatkan mereka.
Kita bisa hanya berputar di sekitar lingkaran berusaha untuk menemukan tempat kosong,
dan kami mungkin terjebak dalam loop tak terbatas.
>> Jadi semacam ini meminjamkan untuk ide dari sesuatu yang disebut chaining.
Dan ini adalah di mana kita akan membawa daftar terkait kembali ke dalam gambar.
Bagaimana jika bukan hanya menyimpan data itu sendiri dalam array,
setiap elemen dari array bisa memegang beberapa bagian data?
Nah itu tidak masuk akal, kan?
Kita tahu bahwa sebuah array hanya dapat hold-- setiap elemen array
hanya bisa menampung satu potong data dari jenis data.
>> Tapi bagaimana jika yang tipe data adalah linked list, kan?
Jadi bagaimana jika setiap elemen dari array adalah
pointer ke kepala linked list?
Dan kemudian kita bisa membangun daftar tersebut terkait
dan tumbuh mereka sewenang-wenang, karena daftar terkait memungkinkan
kita untuk tumbuh dan menyusut lebih banyak fleksibel daripada array tidak.
Jadi bagaimana jika sekarang kita gunakan, kita memanfaatkan ini, kan?
Kami mulai tumbuh rantai ini dari lokasi array yang ini.
>> Sekarang kita bisa muat tak terbatas jumlah data, atau tidak terbatas,
jumlah sewenang-wenang data, ke dalam tabel hash kami
tanpa pernah berlari ke masalah tabrakan.
Kami juga telah menghilangkan pengelompokan dengan melakukan hal ini.
Dan juga kita tahu bahwa ketika kita memasukkan menjadi linked list, jika Anda ingat
dari video kami pada daftar terkait, secara tunggal daftar terhubung dan daftar ganda terkait,
ini adalah operasi waktu yang konstan.
Kami hanya menambahkan ke depan.
>> Dan untuk melihat ke atas, baik kita tahu yang terlihat di sebuah linked list
bisa menjadi masalah, kan?
Kita harus mencari melalui dari awal sampai akhir.
Tidak ada acak akses dalam linked list.
Tetapi jika bukan memiliki satu terkait daftar mana lookup akan menjadi O n,
kita sekarang memiliki 10 daftar terkait, atau 1.000 daftar terkait,
sekarang itu O n dibagi dengan 10, atau O dari n dibagi dengan 1.000.
>> Dan sementara kita berbicara teoritis tentang kompleksitas
kita mengabaikan konstanta, dalam nyata dunia hal ini benar-benar penting,
benar?
Kami benar-benar akan melihat bahwa hal ini terjadi
untuk menjalankan 10 kali lebih cepat, atau 1.000 kali lebih cepat,
karena kita mendistribusikan satu panjang rantai di 1.000 rantai yang lebih kecil.
Dan setiap kali kita harus mencari melalui salah satu rantai yang kita bisa
mengabaikan 999 rantai kita tidak peduli tentang, dan hanya mencari satu.
>> Yang rata-rata untuk menjadi 1.000 kali lebih pendek.
Dan jadi kami masih semacam cenderung ke arah kasus ini rata-rata
menjadi waktu yang konstan, tetapi hanya karena kita memanfaatkan
membagi oleh beberapa faktor konstan besar.
Mari kita lihat bagaimana ini mungkin benar-benar melihat meskipun.
Jadi ini adalah tabel hash yang kami punya sebelum kita menyatakan tabel hash yang
adalah mampu menyimpan 10 string.
Kami tidak akan melakukan itu lagi.
Kami sudah tahu keterbatasan metode tersebut.
Sekarang tabel hash kami akan menjadi array 10 node, pointer
untuk kepala daftar terkait.
>> Dan sekarang itu nol.
Masing-masing dari mereka 10 pointer adalah null.
Tidak ada di kami hash table sekarang.
>> Sekarang mari kita mulai untuk menempatkan beberapa hal ke dalam tabel hash ini.
Dan mari kita lihat bagaimana metode ini adalah akan bermanfaat bagi kita sedikit.
Mari kita sekarang hash Joey.
Kami akan akan menjalankan string Joey melalui fungsi hash dan kami kembali 6.
Nah apa yang kita lakukan sekarang?
>> Nah sekarang bekerja dengan daftar terkait, kita tidak bekerja dengan array.
Dan ketika kita sedang bekerja dengan daftar terkait kami
tahu kita harus mulai secara dinamis mengalokasikan ruang dan bangunan rantai.
Itu semacam how-- mereka adalah inti unsur membangun sebuah linked list.
Jadi mari kita dinamis mengalokasikan ruang untuk Joey,
dan kemudian mari kita menambahkannya ke rantai.
>> Jadi sekarang melihat apa yang kami lakukan.
Ketika kita hash Joey kami mendapat kode hash 6.
Sekarang pointer di berbagai lokasi 6 menunjuk ke kepala linked list,
dan sekarang itu hanya elemen dari linked list.
Dan node dalam linked list adalah Joey.
>> Jadi jika kita perlu mencari Joey kemudian, kami hanya hash Joey lagi,
kita mendapatkan 6 lagi karena kami Fungsi hash adalah deterministik.
Dan kemudian kita mulai kepala dari linked list menunjuk
oleh lokasi array yang 6, dan kami dapat iterate
di yang mencoba untuk menemukan Joey.
Dan jika kita membangun kami hash table efektif,
dan fungsi hash secara efektif untuk mendistribusikan data dengan baik,
rata-rata masing-masing terkait daftar di setiap lokasi array yang
akan 10/1 ukuran jika kita hanya memiliki sebagai besar tunggal
linked list dengan segala sesuatu di dalamnya.
>> Jika kita mendistribusikan besar terkait daftar di 10 daftar terkait
setiap daftar akan 10/1 ukuran.
Dan dengan demikian 10 kali lebih cepat untuk mencari.
Jadi mari kita lakukan ini lagi.
Mari kita sekarang hash Ross.
>> Dan katakanlah Ross, ketika kita melakukan itu kode hash kita kembali adalah 2.
Nah sekarang kita dinamis mengalokasikan node baru, kami menempatkan Ross di simpul itu,
dan kita katakan sekarang lokasi array yang 2, bukannya menunjuk ke null,
menunjuk ke kepala terkait daftar yang hanya node Ross.
Dan kita bisa melakukan ini sekali lagi, kita dapat hash Rachel dan mendapatkan kode hash 4.
malloc node baru, menempatkan Rachel di node, dan mengatakan lokasi array yang
4 sekarang menunjuk ke kepala dari linked list yang
satunya unsur kebetulan Rachel.
>> OK tapi apa yang terjadi jika kami memiliki tabrakan?
Mari kita lihat bagaimana kita menangani tabrakan menggunakan metode chaining terpisah.
Mari hash Phoebe.
Kami mendapatkan kode hash 6.
Dalam contoh kami sebelumnya kami hanya menyimpan string dalam array.
Ini adalah masalah.
>> Kami tidak ingin mengkritik Joey, dan kami sudah sudah
melihat bahwa kita bisa mendapatkan beberapa pengelompokan masalah jika kita mencoba dan langkah
melalui dan penyelidikan.
Tapi bagaimana kalau kita hanya jenis memperlakukan ini dengan cara yang sama, kan?
Ini seperti menambahkan elemen kepala linked list.
Mari ruang hanya malloc untuk Phoebe.
>> Kami akan mengatakan Phoebe poin pointer berikutnya ke kepala lama linked list,
dan kemudian 6 hanya menunjuk ke kepala baru dari linked list.
Dan sekarang lihat, kami telah mengubah Phoebe di.
Kita sekarang dapat menyimpan dua elemen dengan kode hash 6,
dan kami tidak memiliki masalah.
>> Itu cukup banyak semua ada untuk chaining.
Dan chaining pasti metode yang
akan menjadi yang paling efektif untuk Anda jika Anda menyimpan data dalam tabel hash.
Tapi kombinasi array dan daftar terkait
bersama-sama untuk membentuk tabel hash yang benar-benar secara dramatis meningkatkan kemampuan Anda
untuk menyimpan data dalam jumlah besar, dan sangat cepat dan efisien mencari
melalui data tersebut.
>> Masih ada satu lagi struktur data di luar sana
bahkan mungkin sedikit lebih baik dalam hal menjamin
bahwa penyisipan kami, penghapusan, dan mencari kali bahkan lebih cepat.
Dan kita akan melihat bahwa dalam sebuah video di mencoba.
Aku Doug Lloyd, ini CS50.