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:

• Kemampuan untuk menghitung koleksi

  Koleksi .NET mengimplementasikan System.Collections.IEnumerable atau System.Collections.Generic.IEnumerable<T> untuk memungkinkan koleksi diulang. Pencacah dapat dianggap sebagai penunjuk bergerak ke elemen apa pun dalam koleksi. Pernyataan foreach, in dan For Each...Next Statement menggunakan pencacah yang diekspos oleh metode GetEnumerator dan menyembunyikan kompleksitas dari manipulasi pencacah. Selain itu, koleksi apa pun yang mengimplementasikan System.Collections.Generic.IEnumerable<T> dianggap sebagai jenis yang dapat dikueri dan dapat dikueri dengan LINQ. Kueri LINQ menyediakan pola umum untuk mengakses data. Pola tersebut biasanya lebih ringkas dan mudah dibaca daripada perulangan standar foreach, dan menyediakan kemampuan pemfilteran, pemesanan, dan pengelompokan. Kueri LINQ juga dapat meningkatkan kinerja. Untuk mengetahui informasi selengkapnya, lihat LINQ ke Objek (C#), LINQ ke Objek (Visual Basic), LINQ Paralel (PLINQ), Pengantar Kueri LINQ (C#), dan Operasi Kueri Dasar (Visual Basic).

• Kemampuan untuk menyalin konten koleksi ke array

  Semua koleksi dapat disalin ke array menggunakan metode CopyTo; namun, urutan elemen dalam array baru didasarkan pada urutan tempat pencacah mengembalikannya. Array yang dihasilkan selalu satu dimensi dengan batas bawah nol.

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.

Topik Terkait

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