[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.