Apakah perbezaan antara tatasusunan dan jadual hash dalam bahasa pengaturcaraan?


Jawapan 1:

Jadual Hash menggunakan tatasusunan. Array mempunyai harta penting untuk hashing: anda boleh mengakses sebarang elemen dalam masa yang tetap jika anda mengetahui indeksnya.

Anda boleh menggunakan array untuk baldi. Katakan anda mahu anda mengira jumlah setiap huruf dalam teks, katakan, kerana mereka bentuk sesuatu seperti kod Morse. Anda membuat tatasusunan dengan 26 entri (untuk abjad Roman yang tidak dapat diakses). Setiap kali anda melihat surat, anda mengira indeks itu dan pergi ke entri itu dalam array.

Jadual Hash memanjangkan ini untuk kekunci yang sewenang-wenangnya. Anda mengira hash kekunci dan pergi ke indeks itu. Masalahnya ialah apabila pelbagai kunci mempunyai hash yang sama. Terdapat pelbagai cara untuk menangani perkara ini, sebahagiannya mengalahkan tujuan hash (tetapi mudah dilaksanakan). Sesetengah daripada mereka tidak dan mengekalkan harta masa malar, sekurang-kurangnya secara purata.

Yang terbaik yang saya lihat ialah rehash add-the-hash, yang jika memori berfungsi dari dekad yang lalu, Gonnet dan Munroe terbukti mempunyai purata sedikit lebih daripada 4 akses dengan faktor beban 50%, tanpa mengira saiz jadual hash. Walau bagaimanapun, ini memerlukan penggunaan nombor perdana, dan ini menjadikannya sukar untuk dilaksanakan. Anda perlu mencari nombor utama entah bagaimana. Nasib baik, jadual hash tidak begitu besar sehingga ini menjadi tidak masuk akal.