Efisiensi kamus C #

Kamus C # adalah cara mudah untuk menemukan apakah ada sesuatu, dll. Namun, saya punya pertanyaan tentang cara kerjanya. Katakanlah alih-alih kamus saya menggunakan ArrayList. Alih-alih menggunakan ContainsKey(atau metode yang setara dalam bahasa lain) saya memutar melalui ArrayList untuk memeriksa apakah ada sesuatu di sana (atau melakukan pencarian biner jika data diurutkan atau yang serupa). Apa perbedaan dalam efisiensi? Apakah ContainsKeymetode ini menggunakan beberapa cara yang lebih efisien daripada perulangan melalui kunci dan memeriksa apakah apa yang saya cari ada?

Jika katakanlah saya telah membuat fungsi hash tertentu yang sesuai dengan jenis data yang saya miliki dan secara khusus dirancang untuk kumpulan data itu maka ya, fungsi hash itu memang lebih cepat daripada perulangan melalui data. Tetapi kamus bersifat umum. Metode ContainsKey tidak spesifik untuk data yang didapatnya, ini adalah metode pencarian umum.

Pada dasarnya yang saya tanyakan adalah. Kamus sangat membantu programmer. Mereka termasuk metode yang membantu banyak hal dan mereka menggabungkan string dengan integer, (kunci dan nilai) dan banyak lagi. Namun menyangkut efisiensi, apa yang mereka tawarkan? Apa perbedaan dalam memiliki dictionaryvs ArrayListdaristructs(string,int)

Anda harus menggali sedikit untuk melihat bagaimana Kamus diimplementasikan dalam C # - Ini tidak sejelas HashMap (tabel hash) atau TreeMap (pohon diurutkan) (atau ConcurrentSkipListMap - daftar lompatan ).

Jika Anda menggali ke bagian "Keterangan":

Kamus generik Kamus menyediakan pemetaan dari serangkaian kunci ke serangkaian nilai. Setiap tambahan ke kamus terdiri dari nilai dan kunci terkait. Mengambil nilai dengan menggunakan kuncinya sangat cepat, dekat dengan O (1), karena kelas Kamus diimplementasikan sebagai tabel hash.

Dan di sana kita memilikinya. Ini tabel hash . Perhatikan bahwa saya telah menautkan artikel Wikipedia di sana - ini adalah bacaan yang cukup bagus. Anda mungkin ingin membaca bagian tentang resolusi tabrakan. Dimungkinkan untuk mendapatkan kumpulan data patologis di mana pencarian beralih ke O (N) (misalnya semua yang Anda masukkan jatuh ke nilai hash yang sama atau indeks dalam tabel hash untuk beberapa alasan dan Anda pergi dengan linear probing ).

Meskipun Kamus adalah solusi tujuan umum, Anda tidak boleh melewati tipe-tipe konkret (seperti Kamus) - Anda harus melewati antarmuka. Dalam hal ini, antarmuka itu adalah IDictionary( docs ). Untuk ini, Anda benar-benar mampu menulis implementasi kamus Anda sendiri yang melakukan hal-hal secara optimal untuk data yang Anda miliki.

Adapun efisiensi berbagai pencarian / berisi?

• Berjalan daftar yang tidak disortir: O (N)
• Pencarian biner dari array yang diurutkan: O (log N)
• Pohon yang disortir: O (log N)
• Tabel hash: O (1)

Bagi kebanyakan orang, tabel hash adalah apa yang mereka inginkan.

Anda mungkin menemukan bahwa SortedDictionary adalah yang Anda inginkan sebagai gantinya:

Kelas SortedDictionary<TKey, TValue>generik adalah pohon pencarian biner dengan pengambilan O (log n), di mana n adalah jumlah elemen dalam kamus. Dalam hal ini, mirip dengan SortedList<TKey, TValue>kelas generik. Kedua kelas memiliki model objek yang serupa, dan keduanya memiliki pengambilan O (log n).

Padahal, sekali lagi, jika struktur data bukan yang berfungsi dengan data Anda secara ideal, Anda diberi alat (antarmuka) untuk dapat menulis yang paling cocok untuk data Anda.

Kamus itu sendiri adalah tipe data abstrak . Anda memberi saya sebuah Kamus dan saya tahu apa yang bisa saya lakukan dengannya dan semua alat yang ada di sana untuk saya gunakan karena sifatnya sebagai Kamus. Jika Anda memberi saya ArrayList, saya akan menemukan diri saya menulis kode sendiri untuk mencari, menyisipkan, atau menghapus item dari daftar. Ini membuang-buang waktu saya dan juga berarti ada lebih banyak kemungkinan bug ketika saya menyalin kode berulang kali dari satu tempat ke tempat lain.