[C#] C#의 Collection

C++에 STL이 있다면 C#에는 Collection이 있다고 할 수 있다. STL을 정리한 김에 Collection도 같이 정리하려 한다.

컬렉션(Collection)이란?

- 컬렉션은 동일 타입의 객체를 여러 개 보관할 수 있는 클래스를 말한다.

- 배열, linked list, tree, hash table 등의 자료구조와 데이터 관리 및 조작을 쉽게 하기 위한 다양한 를 구현한 클래스이다.

- C++의 STL의 Container와 같은 기능을 한다고 볼 수 있다.

- 어떤 타입을 보관할 것인가에 따라 여러 namespace 안에 정의되어 있다.

• System.Collections(비제네릭 컬렉션) : 모든 타입을 obejct로 저장하여 다양한 타입을 혼합해서 사용할 수 있다. 타입 안정성이 좋지 않고, 값을 꺼낼 때 캐스팅이 필요하다.

       주요 클래스 : ArrayList, Queue, Stack, Hashtable

• System.Collections.Generic(제네릭 컬렉션) : 컬렉션에 특정 타입을 지정할 수 있어 타입 안전성이 보장되며, 컴파일 시 타입이 결정되므로 런타임 오류가 줄어든다.

       주요 클래스 : List<T>, Dictionary<TKey, TValue>, Queue<T>, Stack<T>, HashSet<T>

• System.Collections.Specialized(특수 목적 컬렉션) : 문자열 데이터나 소규모 데이터셋 등을 다룰 때 효율적인, 특정 용도에 맞춘 컬렉션이 포함되어 있다. 즉, 특정 타입만 저장할 수 있는 Collection이다.

       주요 클래스 : StringCollection, NameValueCollection, StringDictionary

• System.Collections.Concurrent(동시성 컬렉션) : 멀티 스레드 환경에서 안전하게 사용할 수 있는 동시성 지원 컬렉션이 포함되어 있다.

        스레드 동기화를 내부적으로 처리하여 여러 스레드가 동시에 접근해도 안전하게 동작한다.

 

       주요 클래스 : ConcurrentDictionary<TKey, TValue>, ConcurrentQueue<T>, ConcurrentStack<T>, ConcurrentBag<T>

 

주요 컬렉션의 구현 구조 및 연산 시간 복잡도

List<T>

• C++의 vector와 비슷하게 동적 배열 구조로 구현되어 있으며, 원래 배열의 크기를 초과하면, 2배 더 큰 크기의 배열을 할당받은 뒤 기존 요소를 복사하여 저장한다.
• 접근 : 인덱스를 통해 중간 값에 접근하므로 임의의 원소에 접근하는데 O(1)의 시간이 소요된다.
• 삽입 : 배열의 끝에 삽입하는 경우 O(1)의 시간이 소요되지만, 중간에 삽입하는 경우에는 원소를 한 칸씩 뒤로 이동시켜야 하므로 O(n)의 시간이 소요된다.
• 삭제 : 배열의 끝에 있는 원소를 삭제하면 O(1)이, 중간에 있는 원소를 삭제하는 경우, 뒤에 있는 원소들을 한 칸씩 앞으로 이동시켜야 하므로 O(n)의 시간이 소요된다.
• 원소들이 메모리에 연속적으로 저장된다.

Dictionary<TKey, TValue>

• C++의 unordered_map과 동일하게 해시 테이블로 구현되어 있으며, 키를 해싱하여 적절한 버킷에 값을 저장한다.
• 해시 충돌이 발생할 시, 버킷 내에 연결 리스트를 통해 해시 값을 처리하는 체이닝(Chaining) 방식을 사용한다.
• 접근, 삽입, 삭제, 탐색 모두 해시 충돌이 없는 경우 O(1)의 시간이 소요되지만, 최악의 경우에는 체이닝으로 인해 O(n)의 시간이 소요된다.
• 연결된 리스트 배열을 사용하여 메모리 내의 분산된 공간에 버킷을 저장한다. 해시 충돌이 일어나면 동일 버킷에 연결 리스트를 사용하여 충돌을 해결한다.

SortedDictionary<TKey, TValue>

• C++의 map과 동일한 역할을 하며, 레드 블랙 트리로 구현되어 있다.
• 기본적으로 Key를 기준으로 오름차순 정렬을 사용한다.
• 레드블랙 트리를 사용하므로 접근, 삽입, 삭제, 탐색 모두 O(logN)의 시간복잡도를 가진다.

Queue<T>

• 원형 배열 또는 링 버퍼로 구현되어 있다. FIFO(First In First Out) 방식으로 작동한다.
• 접근 : 맨 앞(Peek())과 맨 뒤(Last()) 요소에만 접근이 가능하고 각각 O(1)의 시간이 소요된다.
• 삽입 : 맨 뒤에만 삽입이 가능하며 O(1)의 시간이 소요된다.
• 삭제 : 맨 앞에서만 삭제가 가능하며 O(1)의 시간이 소요된다.
• 탐색 : 맨 앞에서부터 순차적으로 원소를 탐색할 수 밖에 없으므로 O(n)의 시간이 소요된다.
• 연속된 배열 구조로 저장되며, 큐가 가득 찼을 때 크기를 두 배 늘리는 방식으로 메모리 관리를 한다. 원형 배열을 사용해 메모리 공간을 효율적으로 활용한다.

Stack<T>

• 동적 배열로 구현되어 있으며, LIFO(Last In First Out) 방식으로 작동한다.
• 접근 : 맨 위에만 접근이 가능하므로 O(1)의 시간이 소요된다.
• 삽입 : 맨 위에만 삽입이 가능하므로 O(1)의 시간이 소요된다.
• 삭제 : 맨 위에서만 삭제가 가능하므로 O(1)의 시간이 소요된다.
• 탐색 : 맨 위에서부터 순차적으로 원소를 탐색할 수 밖에 없으므로 O(n)의 시간이 소요된다.
• 동적 배열로 저장되기 때문에 메모리에 연속적으로 저장되며, 배열 크기를 초과하면 두 배로 크기를 늘린다.

LinkedList<T>

• C++의 List와 비슷하게 이중 연결 리스트(doubly linked list)로 구현되어 있다.
• 접근 : 임의의 위치의 원소에 접근하려면 순차적으로 탐색하며 접근해야 하므로 O(n)의 시간이 소요된다.
• 삽입 : 노드 삽입 위치가 주어졌을 때, 참조하는 노드만 바꾸면 되므로 O(1)의 시간이 소요된다.
• 삭제 : 삽입과 마찬가지로 O(1)의 시간이 소요된다.
• 탐색 : 순차적으로 탐색할 수 밖에 없으므로 O(n)의 시간이 소요된다.
• 각 원소가 독립적인 노드 객체로 저장되며, 각 노드가 힙 메모리에 개별적으로 할당된다. 즉, 비연속적으로 메모리 상에 저장된다.

HashSet<T>

• C++의 unordered_set과 비슷한 기능을 하며, 해시 테이블을 사용하여 구현되어 있다.(요소 하나만 저장)
• 해시 충돌이 발생할 시, 버킷 내의 연결 리스트를 통해 해시 값을 처리하는 체이닝(Chaining) 기법을 사용하여 충돌을 처리한다.
• 해시셋의 요소가 많아지면 해시 테이블의 크기를 늘리고 요소를 재배치하는 재해싱 작업을 수행하여 성능을 유지한다.
• 접근, 삽입, 삭제, 탐색 모두 해시 충돌이 없는 경우 O(1)의 시간이 소요되지만, 최악의 경우에는 체이닝으로 인해 O(n)의 시간이 소요된다.
• 메모리 저장도 Dictionary와 비슷하게 분산된 버킷으로 저장된다.

SortedSet<T>

• C++ set과 비슷한 기능을 하며, 레드 블랙 트리를 사용하여 구현되어 있다.
• 기본적으로 오름차순 정렬을 사용한다.
• 접근, 삽입, 삭제, 탐색 모두 O(logN)의 시간 복잡도를 가진다.

Concurrent Collections(예 : ConcurrentDictionary<TKey, TValue>)

• 내부적으로 잠금과 해시 분할을 사용하여 다중 스레드에서도 안전하게 접근할 수 있도록 설계되었다.
• Dictionary와 비슷한 시간 복잡도를 가지며, 여러 스레드가 동시에 접근해도 효율적으로 작동하도록 설계되었다.
• 해시 테이블을 사용하는 collection과 동일하게 메모리에 저장되지만, 각 스레드에 잠금이 필요한 경우 메모리를 별도로 관리하여 동시성을 보장한다.

 

출처 : https://www.geeksforgeeks.org/collections-in-c-sharp/