Tabel hash versus pohon biner

Saat menerapkan kamus ('Saya ingin mencari data pelanggan dengan ID pelanggan mereka'), struktur data yang digunakan adalah tabel hash dan pohon pencarian biner. Saya tahu misalnya bahwa perpustakaan C ++ STL mengimplementasikan kamus (mereka menyebutnya peta) menggunakan pohon pencarian biner (seimbang), dan kerangka .NET menggunakan tabel hash di bawah tenda.

Apa kelebihan dan kekurangan dari struktur data ini? Apakah ada opsi lain yang masuk akal dalam situasi tertentu?

Perhatikan bahwa saya tidak terlalu tertarik pada kasus-kasus di mana kunci memiliki struktur dasar yang kuat, katakanlah, mereka semua bilangan bulat antara 1 dan n atau sesuatu.

$n$

Jawaban singkatnya adalah bahwa tabel hash lebih cepat dalam banyak kasus , tetapi bisa sangat buruk pada yang terburuk. Pohon pencarian memiliki banyak keuntungan, termasuk perilaku terburuk yang jinak , tetapi agak lambat dalam kasus-kasus tertentu.

$O(\mathrm{lg}(n))$$\mathrm{log}_2(n)$

$2n$$O(1)$

$O(1)$

• $O(n)$
• $O(1)$

Saat Anda melempar lokalitas data ke dalam campuran, tabel hash berkinerja buruk. Mereka bekerja dengan tepat karena mereka menyimpan elemen terkait secara berjauhan, yang berarti bahwa jika aplikasi mencari elemen yang berbagi awalan secara berurutan, itu tidak akan mendapat manfaat dari efek cache. Ini tidak relevan jika aplikasi pada dasarnya membuat pencarian acak.

Faktor lain yang mendukung pohon pencarian adalah bahwa mereka merupakan struktur data yang tidak dapat diubah : jika Anda perlu mengambil salinan pohon dan mengubah beberapa elemen di dalamnya, Anda dapat berbagi sebagian besar struktur data. Jika Anda mengambil salinan tabel hash, Anda perlu menyalin seluruh array pointer. Juga, jika Anda bekerja dalam bahasa yang murni fungsional, tabel hash seringkali bukan pilihan.

$k_1 \equiv k_2 \implies h(k_1) = h(k_2)$

Secara khusus, jika Anda akan membutuhkan urutan pada tombol, misalnya jika Anda ingin dapat membuat daftar kunci dalam urutan abjad, maka tabel hash tidak membantu (Anda harus mengurutkannya), sedangkan Anda dapat langsung menelusuri pohon pencarian secara berurutan.

Anda dapat menggabungkan pohon pencarian biner dan tabel hash dalam bentuk pohon hash . Pohon hash menyimpan kunci di pohon pencarian sesuai hash mereka. Ini berguna, misalnya, dalam bahasa pemrograman murni fungsional di mana Anda ingin bekerja pada data yang tidak memiliki hubungan urutan yang mudah untuk dihitung.

Ketika kunci adalah string (atau bilangan bulat), trie bisa menjadi pilihan lain. Trie adalah pohon, tetapi diindeks berbeda dari pohon pencarian: Anda menulis kunci dalam biner, dan ke kiri untuk 0 dan kanan untuk 1. Biaya akses dengan demikian sebanding dengan panjang kunci. Mencoba dapat dikompresi untuk menghapus node perantara; ini dikenal sebagai patricia trie atau radix tree . Pohon radix dapat mengungguli pohon seimbang, terutama ketika banyak kunci berbagi awalan yang sama.