Mengapa Python menggunakan tabel hash untuk mengimplementasikan dict, tetapi bukan Red-Black Tree? [Tutup]

Mengapa Python menggunakan tabel hash untuk mengimplementasikan dict, tetapi bukan Red-Black Tree?

Apa kuncinya? Performa?

Ini adalah jawaban umum, non-Python-spesifik.

Perbandingan kompleksitas algoritma

       | Hash Table  |   Red-Black Tree    |
-------+-------------+---------------------+
Space  | O(n) : O(n) | O(n)     : O(n)     |
Insert | O(1) : O(n) | O(log n) : O(log n) |
Fetch  | O(1) : O(n) | O(log n) : O(log n) |
Delete | O(1) : O(n) | O(log n) : O(log n) |
       | avg  :worst | average  : worst    |

Masalah dengan tabel hash adalah hash dapat bertabrakan. Ada berbagai mekanisme untuk menyelesaikan tabrakan, misalnya pengalamatan terbuka atau rantai terpisah. Kasus terburuk absolut adalah bahwa semua kunci memiliki kode hash yang sama, dalam hal ini tabel hash akan terdegradasi ke dalam daftar tertaut.

Dalam semua kasus lain, tabel hash adalah struktur data yang hebat yang mudah diimplementasikan dan memberikan kinerja yang baik. Kelemahannya adalah implementasi yang dapat dengan cepat menumbuhkan tabel dan mendistribusikan kembali entri mereka kemungkinan akan menghabiskan memori hampir sebanyak yang sebenarnya digunakan.

RB-Trees adalah penyeimbang diri dan tidak mengubah kompleksitas algoritmiknya dalam kasus terburuk. Namun, mereka lebih sulit diimplementasikan. Kompleksitas rata-rata mereka juga lebih buruk daripada tabel hash.

Pembatasan pada kunci

Semua kunci dalam tabel hash harus hashable dan sebanding untuk kesetaraan antara satu sama lain. Ini terutama mudah untuk string atau integer, tetapi juga cukup mudah untuk diperluas ke tipe yang ditentukan pengguna. Dalam beberapa bahasa seperti Java, properti ini dijamin oleh definisi.

Kunci dalam RB-Tree harus memiliki urutan total: masing-masing kunci harus dapat dibandingkan dengan kunci lainnya, dan kedua tombol harus membandingkan lebih kecil, lebih besar, atau sama. Kesetaraan pemesanan ini harus setara dengan kesetaraan semantik. Ini mudah untuk bilangan bulat dan angka lainnya, juga cukup mudah untuk string (urutan hanya perlu konsisten dan tidak dapat diamati secara eksternal, sehingga urutan tidak perlu mempertimbangkan lokal ^[1] ), tetapi sulit untuk jenis lain yang tidak memiliki urutan bawaan. . Sama sekali tidak mungkin untuk memiliki kunci dari tipe yang berbeda kecuali beberapa perbandingan di antara mereka adalah mungkin.

^{[1]: Sebenarnya, saya salah di sini. Dua string mungkin tidak sama dengan byte tetapi masih setara menurut aturan beberapa bahasa. Lihat misalnya normalisasi Unicode untuk satu contoh di mana dua string yang sama dikodekan secara berbeda. Apakah komposisi karakter Unicode penting untuk kunci hash Anda adalah sesuatu yang tidak diketahui oleh implementasi tabel hash.}

Orang mungkin berpikir bahwa solusi murah untuk kunci RB-Tree adalah dengan terlebih dahulu menguji kesetaraan, kemudian membandingkan identitas (yaitu membandingkan pointer). Namun, pemesanan ini tidak akan transitif: Jika a == bdan id(a) > id(c), maka harus mengikuti itu id(b) > id(c)juga, yang tidak dijamin di sini. Jadi sebagai gantinya, kita mungkin menggunakan kode kunci hash sebagai kunci pencarian. Di sini, pemesanan bekerja dengan benar, tetapi kita mungkin berakhir dengan beberapa kunci berbeda dengan kode hash yang sama, yang akan ditugaskan ke simpul yang sama di pohon RB. Untuk mengatasi tabrakan hash ini kita bisa menggunakan rantai terpisah seperti halnya dengan tabel hash, tetapi ini juga mewarisi perilaku kasus terburuk untuk tabel hash - yang terburuk dari kedua dunia.

Aspek Lainnya

• Saya berharap tabel hash memiliki memori lokalitas lebih baik daripada pohon, karena tabel hash pada dasarnya hanya sebuah array.

• Entri di kedua struktur data memiliki overhead yang cukup tinggi:

  • tabel hash: kunci, nilai, dan pointer entri berikutnya dalam kasus perangkaian terpisah. Menyimpan kode hash juga dapat mempercepat pengubahan ukuran.
  • RB-tree: kunci, nilai, warna, pointer anak kiri, pointer anak kanan. Perhatikan bahwa sementara warna adalah bit tunggal, masalah penyelarasan bisa berarti Anda masih menyia-nyiakan ruang yang cukup untuk hampir seluruh penunjuk, atau bahkan hampir empat petunjuk ketika hanya blok memori berukuran dua dimensi yang dapat dialokasikan. Bagaimanapun, entri RB-tree mengkonsumsi lebih banyak memori daripada entri tabel hash.

• Penyisipan dan penghapusan dalam pohon RB melibatkan rotasi pohon. Ini tidak terlalu mahal, tetapi melibatkan overhead. Dalam hash, penyisipan dan penghapusan tidak lebih mahal daripada akses sederhana (meskipun mengubah ukuran tabel hash setelah penyisipan adalah O(n)upaya).

• Tabel hash secara inheren bisa berubah, sedangkan RB-tree juga bisa diimplementasikan dengan cara yang tidak berubah. Namun, ini jarang bermanfaat.

Ada berbagai alasan yang mungkin benar, tetapi yang utama kemungkinannya adalah:

• Tabel hash lebih mudah diimplementasikan daripada pohon. Tidak sepenuhnya sepele, tetapi tabel hash sedikit lebih mudah, dan dampak pada domain kunci hukum kurang ketat karena Anda hanya perlu fungsi hashing dan fungsi kesetaraan; pohon membutuhkan fungsi urutan total, dan itu jauh lebih sulit untuk ditulis.
• Tabel hash (mungkin) memiliki kinerja yang lebih baik pada ukuran kecil. Ini sangat penting karena sebagian kecil dari pekerjaan hanya secara teoritis berkaitan dengan dataset besar; dalam praktiknya, banyak yang benar-benar berfungsi hanya dengan puluhan atau ratusan kunci, bukan jutaan. Kinerja skala kecil sangat penting, dan Anda tidak dapat menggunakan analisis asimptotik untuk mencari tahu apa yang terbaik di sana; Anda harus benar-benar menerapkan dan mengukur.

Lebih mudah untuk menulis / memelihara, dan pemenang kinerja dalam kasus penggunaan khusus? Tolong daftarkan saya!