[NOISE]. Sebelum menyelam ke dalam tabel hash, mari kita pertama meninjau pro dan kontra dari beberapa struktur data sederhana, dimulai dengan array. Ingat bahwa array memungkinkan kita untuk menyimpan elemen tipe data tunggal contiguously dalam memori. Karena setiap elemen dikaitkan dengan indeks, atau lokasi, kita memiliki akses acak untuk semua elemen dalam array. Dengan kata lain, kita dapat mengakses setiap elemen dalam satu langkah dengan mengindeks ke dalam array. Ini adalah masalah besar, karena algoritma seperti pencarian biner tergantung pada random akses. Sebuah Kelemahan dari array adalah bahwa ukuran mereka adalah tetap. Karena array menyimpan data contiguously di memori, Anda harus menentukan ukuran array ketika Anda mendeklarasikan array tersebut. Anda secara efektif meminta operasi sistem untuk memesan jumlah yang tepat memori untuk elemen array itu. Tidak ada jaminan bahwa lebih banyak memori, berdekatan dengan array Anda, akan tersedia untuk digunakan nanti. Jadi array tidak dapat dengan mudah tumbuh. Ingatlah bahwa kita juga belajar tentang terkait daftar, yang dapat tumbuh karena mereka unsur tidak bersebelahan di memori. Setiap node dalam linked list berisi elemen yang ingin kita simpan, serta pointer ke elemen berikutnya dalam daftar. Sayangnya, harga yang kami sudah membayar untuk Ukuran dinamis adalah akses acak untuk elemen. Untuk mengakses elemen tertentu, itu perlu untuk melintasi seluruh yang daftar sampai elemen yang diinginkan tercapai. Jadi, jika saya sedang mencari nomor 9, saya akan ikuti pointer dari node ke node, memeriksa apakah nilai dari setiap node sama dengan 9. Dengan demikian, dalam kasus terburuk, mencari adalah O (n), yang jauh dari efisien. Bisakah kita melakukan lebih baik dari O (n) saat masih memungkinkan struktur data kami untuk tumbuh lebih waktu? Tabel hash menawarkan solusi. Tabel hash digunakan ketika speedy penyisipan, penghapusan, dan pencarian dari elemen adalah prioritas. Secara teori, penyisipan, penghapusan, dan lookup bahkan dapat dicapai dalam konstan waktu. Jadi, apa adalah tabel hash sih? Sebuah tabel hash adalah hanya sebuah array digabungkan dengan fungsi, yang akan kita sebut hash fungsi. Fungsi hash mengambil sepotong data sebagai masukan, kita akan menyebutnya kunci, dan output integer, biasa disebut sebagai nilai hash. Nilai hash peta kunci kami untuk indeks tertentu dalam tabel hash. Anda awalnya akan menggunakan fungsi hash untuk menentukan di mana dalam tabel hash untuk menyimpan kunci yang diberikan. Kemudian, Anda akan menggunakan fungsi hash yang sama untuk menentukan di mana dalam tabel hash untuk mencari kunci yang diberikan. Untuk alasan ini, itu penting bahwa hash fungsi berperilaku konsisten dan output nilai hash yang sama untuk kunci identik. Ketahuilah bahwa tabel hash dapat digunakan untuk menyimpan data dari semua jenis. Tetapi untuk menyederhanakan hal-hal, kita akan berfokus pada string untuk saat ini. Berikut adalah fungsi hash sederhana untuk string. Fungsi hash ini menghitung hash fungsi didasarkan pada huruf pertama dari key. "Apple" dimulai dengan huruf "A", jadi dipetakan ke indeks 0 dalam tabel hash. Demikian pula, "pisang" dipetakan ke indeks 1, dan "kucing" dipetakan ke indeks 2. Jika seorang teman bertanya apakah kata "anjing" dalam meja, kita akan memasukkan "anjing" dalam hash fungsi, akan yang nilai hash keluaran dari 3. Karena "anjing" tidak disimpan pada indeks 3, kami dapat mengatakan dengan yakin bahwa "anjing" tidak dalam tabel, meskipun kita hanya memeriksa salah satu hash tabel 26 indeks. Waktu untuk melemparkan kunci ke hal. Bagaimana jika kita ingin menyimpan "semut" ke dalam tabel juga? "Ant" hash indeks 0, seperti "apel" itu. Ini adalah contoh dari tabrakan, yang Hasil dari dua kunci hashing untuk sama indeks. Bahkan jika tabel hash Anda lebih besar daripada mengatur data Anda, dan Anda telah memilih yang baik hash function, Anda masih perlu rencana untuk berurusan dengan tabrakan, jika dan ketika mereka muncul. Mari kita membahas pro dan kontra dari dua metode umum untuk menyelesaikan tabrakan: linear probing dan chaining terpisah. Dengan linear probing, jika hash kunci indeks yang sama seperti yang tersimpan sebelumnya kunci, itu ditugaskan tersedia berikutnya Slot dalam tabel. Jadi, "semut" sekarang disimpan pada indeks 3, karena indeks 0, 1, dan 2 sudah digunakan. Dan jika kita mencoba untuk menyimpan kata ketiga yang dimulai dengan huruf "A", itu ditugaskan indeks 4, karena indeks 0, 1, 2, dan 3 penuh. Seperti yang Anda lihat bahkan dari ini sederhana Misalnya, setelah tabrakan terjadi, Anda secara signifikan meningkatkan kemungkinan bahwa tabrakan lain akan terjadi di sama daerah. Ini disebut clustering, dan itu adalah kelemahan serius untuk linear probing. Selain itu, kasus terburuk penyisipan, penghapusan, dan waktu pencarian telah diserahkan kepada O (n), sebagai slot yang tersedia berikutnya bisa berpotensi menjadi slot terakhir dalam tabel. Mungkin chaining terpisah akan menawarkan lebih solusi menarik. Dalam model chaining terpisah, hash tabel sebenarnya merupakan array dari pointer ke terkait daftar. Ketika tabrakan terjadi, kunci bisa dimasukkan ke dalam waktu yang konstan di kepala yang linked list yang sesuai. Apa yang terjadi sekarang ketika kita mencari "apple" dalam tabel hash? Dalam kasus terburuk, kita harus melintasi Seluruh linked list, mulai dari indeks 0. The terburuk waktu pencarian untuk hash tabel yang menggunakan chaining terpisah Oleh karena itu, O (n / k), dimana k adalah ukuran tabel hash. Tunggu sebentar, k adalah konstanta. Jadi O (n / k) benar-benar hanya O (n), yang merupakan waktu pencarian terburuk untuk linked list. Apakah kita benar-benar pergi melalui semua kesulitan belajar tentang tabel hash hanya untuk berakhir kembali di mana kita mulai? Itu mungkin menjadi kasus dari teoritis perspektif, tetapi di dunia nyata, O (n / k) bisa menjadi perbaikan besar atas O (n). Berpikirlah seperti ini: menganggap k yang 10 - Anda lebih suka menunggu 100 detik atau 100 / k? 10 detik dari Microsoft Word untuk menyelesaikan spell checking dokumen Anda. Seperti yang baru saja Anda lihat, menyelesaikan tabrakan memerlukan satu jenis pencarian linear atau lain, yang memperlambat segalanya jauh. Oleh karena itu, Anda akan ingin memilih hash fungsi yang meminimalkan kemungkinan tabrakan yang terjadi di tempat pertama. Berikut adalah beberapa sifat yang baik hash fungsi yang perlu diingat. Sebuah fungsi hash yang baik harus menggunakan semua informasi yang diberikan oleh kunci yang diberikan untuk memaksimalkan jumlah nilai hash mungkin. Sebagai contoh, jika kita memiliki dua string, "kucing" dan "ulat", kami ingin mereka untuk hash ke tempat-tempat yang berbeda di atas meja. Jika fungsi hash hanya memperhitungkan yang pertama, dua, atau bahkan tiga huruf string, tabrakan akan terjadi, karena kedua kata dimulai dengan sama tiga huruf. Nilai hash harus tersebar merata seberang meja hash. Hal ini akan mengurangi panjang terkait daftar harus tabrakan terjadi. Ini juga merupakan pertanda baik jika nilai hash Anda mampu menghasilkan sangat berbeda hash nilai untuk kunci yang sama, membuat tabrakan sangat kecil kemungkinannya. Tujuan kami adalah penyisipan cepat, penghapusan, dan lookup. Fungsi hash memainkan peran penting dalam masing-masing proses dan akan disebut sangat sering. Oleh karena itu, pastikan mempekerjakan hanya sangat sederhana, operasi cepat untuk meminimalkan run waktu. Saya harap Anda menikmati ini singkat pengantar untuk hash tabel. Nama saya adalah Lauren, dan ini adalah CS50.