Saya mencoba memahami tabel hash - dapatkah seseorang menjelaskannya kepada saya - dengan jelas?

Saya ingin memahami penggunaan dan implementasi tabel hash yang benar di php (maaf).

Saya membaca di suatu tempat bahwa seorang programmer berpengalaman membuat tabel hash dan kemudian mengulanginya. Sekarang, saya mengerti mengapa itu salah tetapi saya belum memiliki pengetahuan penuh untuk mengetahui apakah pemahaman saya benar (jika Anda tahu apa yang saya maksud).

Jadi bisakah seseorang menjelaskan kepada saya bagaimana menerapkan tabel hash di php (mungkin array asosiatif) dan mungkin yang lebih penting, bagaimana mengakses nilai-nilai 'dengan hash' dan apa artinya sebenarnya?

Ikhtisar Tabel Hash Sederhana

Sebagai penyegaran, tabel hash adalah cara untuk menyimpan nilai di bawah kunci tertentu dalam struktur data. Misalnya, saya bisa menyimpan nilai di "a"bawah kunci 1, dan kemudian mengambilnya dengan mencari kunci 1di tabel hash.

Contoh paling sederhana dari tabel hash yang dapat saya pikirkan dari atas kepala saya adalah tabel hash yang hanya dapat menyimpan bilangan bulat, di mana kunci untuk entri tabel hash juga nilai yang disimpan. Katakanlah meja Anda berukuran 8, dan pada dasarnya sebuah array dalam memori:

---------------------------------
|   |   |   |   |   |   |   |   |
---------------------------------
  0   1   2   3   4   5   6   7  

Fungsi Hash

Fungsi hash memberi Anda indeks di mana menyimpan nilai Anda. Fungsi hash yang cukup sederhana untuk tabel ini adalah menambahkan 1 ke nilai yang ingin Anda simpan, dan kemudian memodenya dengan 8 (ukuran tabel). Dengan kata lain, fungsi hash Anda adalah (n+1)%8, di mana ninteger yang ingin Anda simpan.

Sisipan

Jika Anda ingin memasukkan nilai ke dalam tabel hash ini, Anda memanggil fungsi hash Anda (dalam hal ini (n+1)%8) pada nilai yang ingin Anda masukkan untuk memberi Anda indeks. Misalnya, jika kita ingin menyisipkan 14, kita akan memanggil (14 + 1) % 8dan mendapatkan indeks 7, jadi kita akan memasukkan nilainya dalam indeks 7.

---------------------------------
|   |   |   |   |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Demikian pula, kita dapat memasukkan 33, 82, dan 191 seperti:

---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Tabrakan

Tetapi apa yang terjadi jika kita mencoba memasukkan sesuatu yang akan bertabrakan dengan sebuah entri? 2 harus masuk dalam indeks 3, tetapi diambil oleh 82. Ada beberapa cara untuk menyelesaikan masalah ini, yang paling sederhana adalah memanggil fungsi hash kita berulang kali sampai kita menemukan ruang kosong.

Jadi logikanya adalah sebagai berikut:

1. (2 + 1)% 8 = 3
2. Indeks 3 penuh
3. Pasang 3 kembali ke fungsi hash kami. ( 3 + 1)% 8 = 4 , yang kosong.
4. Masukkan nilai kami ke dalam indeks 4 .

Sekarang tabel hash terlihat seperti ini, dengan nilai 2 disimpan di indeks 4.

---------------------------------
|191|   |33 |82 |2  |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Kelemahan dari solusi ini adalah segera, meja kami akan penuh! Jika Anda tahu bahwa ukuran data Anda terbatas, ini seharusnya tidak menjadi masalah selama tabel Anda cukup besar untuk menampung semua nilai yang mungkin. Jika Anda ingin dapat memegang lebih banyak, Anda dapat menangani tabrakan secara berbeda. Mari kita kembali ke tempat kita sebelum memasukkan 2.

---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Jika Anda ingat, (2+1)%8beri kami indeks 3, yang diambil. Jika Anda tidak ingin tabel hash Anda diisi, Anda dapat menggunakan setiap indeks tabel sebagai daftar tertaut, dan menambahkan daftar pada indeks tersebut. Jadi alih-alih memanggil fungsi hash lagi, kami hanya akan menambahkan daftar di indeks 3:

            -----
            | 2 |
---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Daftar ini kemudian dapat tumbuh sebanyak yang dimungkinkan oleh memori. Saya bisa memasukkan 18, dan itu hanya akan ditambahkan ke 2:

            -----
            |18 |
            -----
            | 2 |
---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Pencarian

Nilai pencarian di tabel hash Anda cepat, mengingat bahwa tabel hash Anda berukuran cukup besar. Anda cukup memanggil fungsi hash Anda, dan mendapatkan indeks. Katakanlah Anda ingin melihat apakah 82 ada di meja Anda. Fungsi pencarian akan memanggil (82+1)%8= 3, dan melihat item dalam indeks 3, dan mengembalikannya untuk Anda. Jika Anda melihat ke atas 16, fungsi pencarian akan terlihat dalam indeks 1, dan melihat bahwa itu tidak ada.

Pencarian Perlu Menangani Tabrakan, juga!

Jika Anda mencoba mencari nilai 2, tabel hash Anda harus menggunakan logika tabrakan yang sama dengan yang digunakan untuk menyimpan data seperti untuk mengambil data. Bergantung pada cara tabel hash Anda bekerja, Anda akan meng hash kunci berulang-ulang sampai Anda menemukan entri yang Anda cari (atau menemukan ruang kosong), atau Anda akan beralih melalui daftar tertaut Anda sampai Anda menemukan item (atau sampai di akhir daftar)

Ringkasan

Jadi, tabel hash adalah cara yang baik untuk menyimpan dan mengakses pasangan nilai kunci dengan cepat. Dalam contoh ini kami menggunakan kunci yang sama dengan nilai, tetapi di tabel hash dunia nyata kunci tidak begitu terbatas. Fungsi hash akan bekerja pada tombol untuk menghasilkan indeks, dan kemudian kunci / nilai dapat disimpan pada indeks itu. Tabel hash tidak benar-benar dimaksudkan untuk diulangi, meskipun mungkin untuk melakukannya. Seperti yang Anda lihat, tabel hash dapat memiliki banyak ruang kosong, dan iterasi melalui mereka akan membuang-buang waktu. Bahkan jika tabel hash memiliki logika untuk melewatkan pencarian ruang kosong di iteratornya, Anda akan lebih cocok menggunakan struktur data yang dirancang untuk iterator, seperti daftar tertaut.

Bayangkan sebuah perpustakaan dengan ribuan buku. Anda perlu mengatur buku-buku sehingga Anda dapat menemukan masing-masing dengan judul secepat mungkin.

Salah satu (umum) cara untuk melakukan ini adalah menyortir buku-buku berdasarkan abjad. Jika judul Anda dimulai dengan mengatakan "G" Anda menemukan area "G", kemudian mencari huruf kedua, katakan "ö", lalu "d", "e", "l", mempersempit pencarian Anda, dan sebagainya , sampai Anda menemukan buku itu. Ini, meskipun, mungkin memakan waktu lama dan di samping itu, ketika buku-buku baru tiba Anda kadang-kadang perlu mengatur ulang tata letak Anda untuk memberikan ruang bagi para pendatang baru.

Itu pencarian biner. Ini baik.

Namun, ada cara yang lebih cepat untuk melakukan ini. Katakanlah Anda menghitung semua rak buku dan rak, dan kemudian untuk setiap buku Anda menghitung angka khusus, semoga unik, yang memetakan ke rak buku / rak tempat buku harus ditemukan. Cara Anda menghitung "kunci" tidak masalah asalkan memberikan angka yang tampak acak. Misalnya, Anda dapat menambahkan kode karakter dari semua huruf dalam judul dan kemudian membaginya dengan beberapa bilangan prima (mungkin bukan metode terbaik, tetapi tetap berfungsi).

Itu hashing. Ini jauh lebih cepat, karena Anda tidak perlu membaca seluruh rak buku dan rak sambil mencari huruf berikutnya dalam judul. Hashing biasanya merupakan operasi sekali tembak, kecuali jika Anda memiliki "tabrakan" ketika dua atau lebih buku menyelesaikan ke tombol yang sama. Tapi tidak apa-apa, Anda tahu mereka terletak bersebelahan dan, tergantung pada kualitas fungsi hash, seharusnya tidak ada terlalu banyak di bawah kunci yang sama.

Tabel hash memiliki beberapa batasan dan keinginan (mengulangi / mengubah ukuran), yang menjadikan pencarian biner sebagai pesaing yang layak. Tidak semua hitam & putih berkenaan dengan metode mana yang lebih baik. Tapi itu cerita yang berbeda.

PS Maaf karena tidak menjawab pertanyaan Anda secara langsung (menulis tabel hash di PHP), tapi itu detail dan itu disebut "pemrograman";)

Tabel hash di PHP, sejauh pengetahuan saya, hanya diimplementasikan melalui:

$my_hash = array(
    1 => "Bob",
    2 => "Alice",
    3 => "Jack"
);

Anda kemudian mengakses data melalui panggilan seperti:

echo $my_hash[2]; // Will echo "Alice"

Anda menggunakan fungsi foreach () untuk beralih di atas isi array.

Cara terbaik untuk memahami tabel hash adalah dengan membaca sesuatu seperti http://en.wikipedia.org/wiki/Hash_table , tetapi kira-kira itu mengarah ke ini: sisi kiri setiap baris di dalam array () panggilan adalah kunci . Kunci-kunci ini akan dimasukkan melalui perhitungan hash dan hasilnya adalah hash. Anda mungkin pernah melihat hash MD5 atau SHA sebelumnya, terlihat sangat mirip dengan ini. Bagian spesifik dari hash ini, biasanya karakter X pertama tetapi terkadang hash lengkap, akan digunakan untuk mengidentifikasi apa yang disebut 'ember', yang merupakan area penyimpanan untuk nilai-nilai (sisi kanan).

Lalu setiap kali Anda mengakses hashtable Anda, Anda menggunakan kunci untuk mendapatkan nilai. Kunci akan dihitung untuk hash lagi dan hash digunakan untuk dengan cepat mencari nilai terkait. Jadi tabel hash memungkinkan untuk melihat lebih cepat daripada hanya mencari linear jika semuanya baru saja disimpan. Satu-satunya downside adalah bahwa beberapa implementasi hash menderita tabrakan, yang merupakan hash yang dihitung sama untuk dua kunci yang berbeda. Secara umum, itu bukan sesuatu yang harus Anda khawatirkan.

Saya harap ini memberikan beberapa latar belakang, tetapi silakan coba membaca lebih lanjut tentang subjek jika Anda tertarik. Penjelasan saya sangat sederhana dan saya yakin ada cukup banyak lubang di sana, tetapi harus cukup untuk penjelasan singkat.