Bagikan melalui


Koleksi dan Struktur Data

Data serupa seringkali dapat ditangani dengan lebih efisien bila disimpan dan dimanipulasi sebagai koleksi. Anda dapat menggunakan kelas System.Array atau kelas di namespace System.Collections, System.Collections.Generic, System.Collections.Concurrent, dan System.Collections.Immutable untuk menambahkan, menghapus, dan memodifikasi elemen individual atau rentang elemen dalam kumpulan.

Ada dua jenis utama koleksi; koleksi generik dan koleksi non-generik. Koleksi generik keamanan jenis saat kompilasi. Karena itu, koleksi generik biasanya menawarkan performa yang lebih baik. Koleksi generik menerima parameter jenis saat dibuat dan tidak mengharuskan Anda mentransmisikan ke dan dari jenis Object saat Anda menambahkan atau menghapus item dari koleksi. Selain itu, sebagian besar koleksi generik didukung di aplikasi Windows Store. Koleksi non-generik menyimpan item sebagai Object, memerlukan transmisi, dan sebagian besar tidak didukung untuk pengembangan aplikasi Windows Store. Namun, Anda mungkin melihat koleksi non-generik dalam kode yang lebih lama.

Dimulai dengan .NET Framework 4, koleksi di namespace System.Collections.Concurrent menyediakan operasi aman untuk utas yang efisien untuk mengakses item koleksi dari beberapa utas. Kelas koleksi yang abadi di namespace System.Collections.Immutable (paket NuGet) secara inheren aman untuk utas karena operasi dilakukan pada salinan koleksi asli dan koleksi asli tidak dapat dimodifikasi.

Fitur koleksi umum

Semua koleksi menyediakan metode untuk menambahkan, menghapus, atau menemukan item dalam koleksi. Selain itu, semua koleksi yang secara langsung atau tidak langsung mengimplementasikan antarmuka ICollection atau ICollection<T> membagikan fitur berikut:

Selain itu, banyak kelas koleksi berisi fitur-fitur berikut:

  • Properti Kapasitas dan Hitung

    Kapasitas koleksi adalah jumlah elemen yang dapat dikandungnya. Hitungan koleksi adalah jumlah elemen yang sebenarnya dikandungnya. Beberapa koleksi menyembunyikan kapasitas atau hitungan atau keduanya.

    Sebagian besar koleksi secara otomatis bertambah kapasitasnya saat kapasitas saat ini tercapai. Memori dialokasikan kembali, dan elemen disalin dari koleksi lama ke yang baru. Hal ini mengurangi kode yang diperlukan untuk menggunakan koleksi; namun, performa koleksi mungkin terpengaruh secara negatif. Misalnya, untuk List<T>, jika Count kurang dari Capacity, menambahkan item merupakan operasi O(1). Jika kapasitas perlu ditingkatkan untuk mengakomodasi elemen baru, menambahkan item menjadi operasi O(n), dengan n adalah Count. Cara terbaik untuk menghindari performa buruk yang disebabkan oleh realokasi ganda adalah dengan mengatur kapasitas awal menjadi perkiraan ukuran koleksi.

    BitArray adalah kasus khusus; kapasitasnya sama dengan panjangnya yang sama dengan hitungannya.

  • Batas bawah yang konsisten

    Batas bawah koleksi adalah indeks elemen pertamanya. Semua koleksi terindeks di namespace System.Collections memiliki batas nol yang lebih rendah, yang berarti mereka diindeks 0. Array memiliki batas nol yang lebih rendah secara default, tetapi batas bawah yang berbeda dapat ditentukan saat membuat instans kelas array menggunakan Array.CreateInstance.

  • Sinkronisasi untuk akses dari beberapa utas (hanya kelasSystem.Collections).

    Jenis koleksi non-generik di namespace System.Collections memberikan beberapa keamanan utas dengan sinkronisasi; biasanya diekspos melalui anggota SyncRoot dan IsSynchronized. Koleksi ini tidak aman untuk utas secara default. Jika Anda memerlukan akses multi-utas yang dapat diskalakan dan efisien ke koleksi, gunakan salah satu kelas di namespace System.Collections.Concurrent atau pertimbangkan untuk menggunakan koleksi abadi. Untuk mengetahui informasi selengkapnya, lihat Koleksi yang Aman untuk Untas.

Pilih koleksi

Secara umum, Anda harus menggunakan koleksi generik. Tabel berikut menjelaskan beberapa skenario pengumpulan umum dan kelas pengumpulan yang dapat Anda gunakan untuk skenario tersebut. Jika Anda baru mengenal koleksi generik, tabel ini akan membantu Anda memilih koleksi generik yang paling sesuai untuk tugas Anda.

Saya ingin... Opsi pengumpulan generik Opsi pengumpulan non-generik Opsi pengumpulan yang aman untuk utas atau abadi
Menyimpan item sebagai pasangan kunci/nilai untuk pencarian cepat berdasarkan kunci Dictionary<TKey,TValue> Hashtable

(Kumpulan pasangan kunci/nilai yang diatur berdasarkan kode hash kunci.)
ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

ImmutableDictionary<TKey,TValue>
Mengakses item berdasarkan indeks List<T> Array

ArrayList
ImmutableList<T>

ImmutableArray
Gunakan item first-in-first-out (FIFO) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Menggunakan data Last-In-First-Out (LIFO) Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Mengakses item secara berurutan LinkedList<T> Tidak ada rekomendasi Tidak ada rekomendasi
Terima pemberitahuan saat item dihapus atau ditambahkan ke koleksi. (mengimplementasikan INotifyPropertyChanged and INotifyCollectionChanged) ObservableCollection<T> Tidak ada rekomendasi Tidak ada rekomendasi
Koleksi yang diurutkan SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

ImmutableSortedSet<T>
Satu set untuk fungsi matematika HashSet<T>

SortedSet<T>
Tidak ada rekomendasi ImmutableHashSet<T>

ImmutableSortedSet<T>

Kompleksitas koleksi algoritmik

Saat memilih kelas koleksi, ada baiknya mempertimbangkan potensi tradeoff dalam performa. Gunakan tabel berikut untuk merujuk pada cara berbagai jenis koleksi dapat berubah dibandingkan dalam kompleksitas algoritmik dengan rekan abadi yang sesuai. Jenis koleksi yang abadi sering kali memiliki performa yang lebih rendah tetapi memberikan kekebalan - yang sering kali merupakan manfaat komparatif yang valid.

Bisa diubah Amortisasi Kasus Terburuk Tak bisa diubah Kompleksitas
Stack<T>.Push O(1) O(n) ImmutableStack<T>.Push O(1)
Queue<T>.Enqueue O(1) O(n) ImmutableQueue<T>.Enqueue O(1)
List<T>.Add O(1) O(n) ImmutableList<T>.Add O(log n)
List<T>.Item[Int32] O(1) O(1) ImmutableList<T>.Item[Int32] O(log n)
List<T>.Enumerator O(n) O(n) ImmutableList<T>.Enumerator O(n)
HashSet<T>.Add, pencarian O(1) O(n) ImmutableHashSet<T>.Add O(log n)
SortedSet<T>.Add O(log n) O(n) ImmutableSortedSet<T>.Add O(log n)
Dictionary<T>.Add O(1) O(n) ImmutableDictionary<T>.Add O(log n)
pencarian Dictionary<T> O(1) O(1) – atau O(n) secara ketat pencarian ImmutableDictionary<T> O(log n)
SortedDictionary<T>.Add O(log n) O(n log n) ImmutableSortedDictionary<T>.Add O(log n)

List<T> dapat dijumlahkan secara efisien menggunakan perulangan for atau perulangan foreach. Namun, ImmutableList<T> melakukan pekerjaan yang buruk di dalam perulangan for, karena waktu O(log n) untuk pengindeksnya. Menghitung ImmutableList<T> menggunakan perulangan foreach merupakan hal yang efisien karena ImmutableList<T> menggunakan pohon biner untuk menyimpan datanya alih-alih array sederhana seperti yang digunakan List<T>. Array dapat diindeks dengan sangat cepat, sedangkan pohon biner harus berjalan ke bawah sampai node dengan indeks yang diinginkan ditemukan.

Selain itu, SortedSet<T> memiliki kompleksitas yang sama dengan ImmutableSortedSet<T>. Itu karena keduanya menggunakan pohon biner. Perbedaan yang signifikan, tentu saja, adalah menggunakan pohon biner ImmutableSortedSet<T> yang tidak dapat diubah. Karena ImmutableSortedSet<T> juga menawarkan kelas System.Collections.Immutable.ImmutableSortedSet<T>.Builder yang memungkinkan mutasi, Anda dapat memiliki kekebalan dan performa.

Judul Deskripsi
Memilih Kelas Koleksi Menjelaskan koleksi yang berbeda dan membantu Anda memilih satu untuk skenario Anda.
Jenis Koleksi yang Umum Digunakan Menjelaskan jenis koleksi generik dan nongenerik yang umum digunakan seperti System.Array, System.Collections.Generic.List<T>, dan System.Collections.Generic.Dictionary<TKey,TValue>.
Saat yang Tepat untuk Menggunakan Koleksi Generik Membahas penggunaan jenis koleksi generik.
Perbandingan dan Pengurutan Dalam Koleksi Membahas penggunaan perbandingan kesetaraan dan perbandingan pengurutan dalam koleksi.
Jenis Koleksi yang Diurutkan Menjelaskan performa dan karakteristik koleksi yang diurutkan
Jenis Koleksi Hashtable dan Kamus Menjelaskan fitur jenis kamus berbasis hash generik dan non-generik.
Koleksi yang Aman untuk Utas Menjelaskan jenis koleksi seperti System.Collections.Concurrent.BlockingCollection<T> dan System.Collections.Concurrent.ConcurrentBag<T> yang mendukung akses bersamaan yang aman dan efisien dari beberapa utas.
System.Collections.Immutable Memperkenalkan koleksi yang abadi dan menyediakan tautan ke jenis koleksi.

Referensi

System.Array System.Collections System.Collections.Concurrent System.Collections.Generic System.Collections.Specialized System.Linq System.Collections.Immutable