Apa perbedaan antara array dan tabel hash dalam bahasa pemrograman?


Jawaban 1:

Tabel hash menggunakan array. Array memiliki properti penting untuk hashing: Anda dapat mengakses elemen apa pun dalam waktu yang konstan jika Anda tahu indeksnya.

Anda dapat menggunakan array untuk bucket. Katakanlah Anda ingin menghitung jumlah setiap huruf dalam sebuah teks, misalnya, untuk mendesain sesuatu seperti kode Morse. Anda membuat array dengan 26 entri (untuk alfabet Romawi sederhana tanpa aksen). Setiap kali Anda melihat surat, Anda menghitung indeks dan pergi ke entri itu dalam array.

Tabel hash memperpanjang ini untuk kunci panjang sewenang-wenang. Anda menghitung hash kunci dan pergi ke indeks itu. Masalahnya adalah ketika beberapa kunci memiliki hash yang sama. Ada berbagai cara untuk mengatasi hal ini, beberapa di antaranya mengalahkan tujuan hash (tetapi mudah diimplementasikan). Beberapa dari mereka tidak dan mempertahankan properti waktu konstan, setidaknya rata-rata.

Yang terbaik yang pernah saya lihat adalah pengulangan add-the-hash, yang jika memori berfungsi dari beberapa dekade yang lalu, Gonnet dan Munroe terbukti memiliki rata-rata sedikit lebih dari 4 akses dengan faktor beban 50%, terlepas dari ukuran tabel hash. Ini, bagaimanapun, membutuhkan menggunakan bilangan prima, dan ini membuatnya sulit untuk diterapkan. Anda harus menemukan bilangan prima entah bagaimana. Untungnya, tabel hash tidak menjadi terlalu besar sehingga ini menjadi konyol.