.NET 데이터 구조:ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary — 속도, 메모리 및 각각을 언제 사용합니까?

Question

.NET에는 복잡한 데이터 구조가 많이 있습니다.불행하게도 그 중 일부는 상당히 유사하여 언제 하나를 사용해야 할지, 언제 다른 것을 사용해야 할지 항상 확신할 수 없습니다.내 C# 및 Visual Basic 책의 대부분은 이에 대해 어느 정도 설명하지만 실제 세부 사항은 다루지 않습니다.

Array, ArrayList, List, Hashtable, Dictionary, SortedList 및 SortedDictionary의 차이점은 무엇입니까?

열거 가능한 항목은 무엇입니까(IList - 'foreach' 루프를 수행할 수 있음)?키/값 쌍(IDict)을 사용하는 것은 무엇입니까?

메모리 공간은 어떻습니까?삽입 속도?검색 속도?

언급할 만한 다른 데이터 구조가 있나요?

메모리 사용량과 속도(Big-O 표기법)에 대한 자세한 내용을 계속 찾고 있습니다.

Answer 1

내 머리 꼭대기에서 :

• Array* - 구식 메모리 배열을 나타냅니다. type[] 정렬. 열거 할 수 있습니다. 자동으로 성장할 수 없습니다. 나는 매우 빠른 삽입과 회고 속도를 가정합니다.

• ArrayList - 자동으로 성장하는 배열. 더 많은 오버 헤드를 추가합니다. 열거 할 수 있습니다. 아마도 일반 어레이보다 느리지 만 여전히 꽤 빠릅니다. 이것들은 .NET에 많이 사용됩니다

• List - 내 favs 중 하나 - 제네릭과 함께 사용할 수 있으므로 강력하게 입력 한 배열 (예 : List<string>. 그 외에는 매우 비슷합니다 ArrayList

• Hashtable - 평범한 오래된 해시 가능. o (1)에서 O (n) 최악의 경우. 값 및 키 속성을 열거하고 키/val 쌍을 수행 할 수 있습니다.

• Dictionary - 위와 동일 : Dictionary<string, string>

• SortedList - 정렬 된 일반 목록. 물건을 어디에 두어야하는지 알아 내야하므로 삽입 속도가 느려졌습니다. CAN ENUM., 아마도 검색시 동일 할 것입니다.

나는 사용하는 경향이있다 List 그리고 Dictionary 항상 - 제네릭으로 강력하게 타이핑을 시작하면 표준 비 게 릭으로 돌아 가기가 어렵습니다.

다른 데이터 구조도 많이 있습니다. KeyValuePair 흥미로운 일을하기 위해 사용할 수 있는데 SortedDictionary 유용 할 수 있습니다.

Answer 2

가능하다면 제네릭을 사용하십시오. 여기에는 다음이 포함됩니다.

• ArrayList 대신 목록
• 해시 테이블 대신 사전

Answer 3

먼저 .NET의 모든 컬렉션은 ienumerable을 구현합니다.

둘째, 프레임 워크의 버전 2.0에 제네릭이 추가 되었기 때문에 많은 컬렉션이 중복됩니다.

따라서 일반 컬렉션은 기능을 추가 할 가능성이 있지만 대부분 :

• 목록은 ArrayList의 일반적인 구현입니다.
• 사전은 hashtable의 일반적인 구현입니다

배열은 주어진 인덱스에 저장된 값을 변경할 수있는 고정 크기 컬렉션입니다.

SortedDictionary는 키를 기반으로 정렬되는 유물입니다. SortedList는 필요한 ICOMPARER를 기반으로 정렬되는 유물입니다.

따라서 유물 구현 (keyvaluepairs를 지원하는 사람들)은 다음과 같습니다.

.NET 3.5에 추가 된 또 다른 컬렉션은 해시 세트입니다. 세트 작업을 지원하는 컬렉션입니다.

또한 LinkedList는 표준 링크리스트 구현입니다 (목록은 더 빠른 검색을위한 배열 목록입니다).

Answer 4

좋은 치트 시트 데이터 구조, 알고리즘 등의 복잡성을 언급합니다.

Answer 5

다음은 몇 가지 일반적인 팁입니다.

• 당신이 사용할 수있는 foreach 구현하는 유형 IEnumerable. IList 본질적으로 IEnumberable ~와 함께 Count 그리고 Item (제로 기반 인덱스를 사용하여 항목에 액세스) 속성. IDictionary 반면에, 당신은 모든 호시 가능한 색인으로 품목에 액세스 할 수 있음을 의미합니다.

• Array, ArrayList 그리고 List 모든 구현 IList. Dictionary, SortedDictionary, 그리고 Hashtable 구현하다 IDictionary.

• .NET 2.0 이상을 사용하는 경우 언급 된 유형의 일반적인 대응 물을 사용하는 것이 좋습니다.

• 이러한 유형에 대한 다양한 작업의 시간과 공간 복잡성을 위해서는 문서를 참조해야합니다.

• .NET 데이터 구조가 있습니다 System.Collections 네임 스페이스. 다음과 같은 유형 라이브러리가 있습니다 PowerCollections 추가 데이터 구조를 제공합니다.

• 데이터 구조에 대한 철저한 이해를 얻으려면 다음과 같은 리소스를 참조하십시오. clrs.

Answer 6

.NET 데이터 구조 :

ArrayList와 List가 실제로 다른 이유에 대한 대화에 대한 추가 정보

배열

한 사용자가 말하면 배열은 "구식"컬렉션입니다 (예, 배열은 일부는 아니지만 컬렉션으로 간주됩니다. System.Collections). 그러나 다른 컬렉션과 비교할 때 어레이에 대한 "구식"은 무엇입니까, 즉 제목에 나열된 컬렉션 (여기, Arraylist 및 List (t))는 무엇입니까? 배열을 보면 기본 사항부터 시작하겠습니다.

시작한다, 배열 Microsoft .NET에서 "여러 [논리적으로 관련된] 항목을 단일 컬렉션으로 취급 할 수있는 메커니즘"(링크 된 기사 참조)입니다. 그게 무슨 뜻입니까? 배열은 개별 멤버 (요소)를 순차적으로 저장하고, 다른 하나는 시작 주소가있는 메모리에 있습니다. 배열을 사용하면 해당 주소에서 시작하는 순차적으로 저장된 요소에 쉽게 액세스 할 수 있습니다.

그 외에도 프로그래밍과 반대로 101 일반적인 개념에 반하여 배열은 실제로 매우 복잡 할 수 있습니다.

배열은 단일 치수, 다차원 또는 Jadded (Jagged Array가 읽을 가치가 있음) 일 수 있습니다. 배열 자체는 역동적이지 않습니다 : 일단 초기화되면 배열 N 크기는 충분한 공간을 보유 할 수 있습니다 N 객체 수. 배열의 요소 수는 성장하거나 줄어들 수 없습니다. Dim _array As Int32() = New Int32(100) 배열에 100 개의 INT32 원시 유형 객체를 포함 할 수있는 메모리 블록에 충분한 공간을 보유합니다 (이 경우 배열은 0S로 초기화됩니다). 이 블록의 주소가 반환됩니다 _array.

기사에 따르면, 공통 언어 사양 (CLS)는 모든 배열이 0 기반이어야합니다. .NET의 어레이는 0이 아닌 기반 배열을 지원합니다. 그러나 이것은 덜 일반적입니다. 제로 기반 배열의 "공통"의 결과로 Microsoft는 성능을 최적화하는 많은 시간; 따라서 SZS는이를 조작하기위한 특정 중개 언어 지침이 있기 때문에 단일 치수, 제로 기반 (SZ) 배열은 "특별한" - 실제로는 배열의 가장 좋은 구현입니다 (다차원 등과 반대로).

배열은 항상 참조로 전달됩니다 (메모리 주소) - 알아야 할 배열 퍼즐의 중요한 부분입니다. 바운드 점검을 수행하는 동안 (오류가 발생 함), 배열에서도 경계 점검도 비활성화 될 수 있습니다.

다시 말하지만, 어레이에 대한 가장 큰 장애는 재조정 할 수 없다는 것입니다. 그들은 "고정 된"용량을 가지고 있습니다. 우리의 역사에 Arraylist 및 List (t)를 소개합니다.

Arraylist- 비 게 니체 목록

그만큼 배열 목록 (와 함께 List(Of T) - 몇 가지 중요한 차이점이 있지만 여기, 나중에 설명) - 아마도 다음 컬렉션 (넓은 의미에서)에 추가 된 것으로 생각 될 것입니다. Arraylist는에서 상속합니다 일리스트 ( 'icollection'의 후손) 인터페이스. 배열리스트는 그 자체입니다 부러진 - 더 필요합니다 간접비 - 목록보다.

IList 구현이 배열리스트를 고정 크기 목록 (예 : 배열)으로 취급 할 수 있도록합니다. 그러나 ArrayLists에 의해 추가 된 추가 기능성을 넘어서이 경우 ArrayList (오버 어레이)로 고정 된 크기 인 ArrayList를 사용하는 것은 실제 이점이 없습니다.

내 독서에서 ArrayLists는 들쭉날쭉해질 수 없습니다. "다차원 배열을 요소로 사용하는 것은 지원되지 않습니다". 다시, 배열 목록 관의 또 다른 못. Arraylist는 또한 "유형"되지 않습니다. 즉, 모든 것에서 배열 목록은 단순히 동적 객체 배열입니다. Object[]. 이를 위해서는 ArrayList를 구현할 때 많은 권투 (암시 적) 및 Unboxing (명시 적)이 필요하며 다시 오버 헤드를 추가해야합니다.

근거없는 생각 : 나는 어레이 목록이 배열에서 목록 유형 컬렉션으로 이동하려는 시도의 일종의 개념적 자식이라는 점을 읽거나 들었던 것을 기억합니다. 컬렉션과 관련하여 추가 개발이 이루어 졌으므로 더 이상 최선의 선택이 아닙니다.

목록 (t) : ArrayList가 된 것 (그리고 희망)

메모리 사용량의 차이는 동일한 원시 유형을 포함하는 Arraylist보다 56% 적은 메모리를 소비 한 경우 (위의 신사의 링크 된 데모에서 8MB vs. 19MB : 다시, 연결 여기) - 이것은 64 비트 기계에 의해 복잡한 결과이지만. 이 차이는 실제로 두 가지를 보여줍니다. 첫 번째 (1), 박스형 int32- 타입 "객체"(Arraylist)는 순수한 INT32 원시 유형 (목록)보다 훨씬 큽니다. 둘째 (2), 차이는 64 비트 기계의 내부 작업의 결과로 지수입니다.

그래서 차이점은 무엇이며 무엇이 목록 (t)? MSDN 정의 a List(Of T) "... 인덱스에 의해 액세스 할 수있는 강력하게 입력 된 객체 목록." 여기서 중요성은 "강하게 입력 된"비트입니다. 목록 (t)은 유형을 인식하고 객체를 유형으로 저장합니다. 그래서, Int32 로 저장됩니다 Int32 그리고 아닙니다 Object 유형. 이렇게하면 복싱 및 Unboxing으로 인한 문제가 제거됩니다.

MSDN 은이 차이가 기준 유형이 아닌 원시 유형을 저장할 때만 작동합니다. 또한 차이는 실제로 500 개가 넘는 요소로 대규모로 발생합니다. 더 흥미로운 점은 MSDN 문서가 읽은 것입니다. "ArrayList 클래스를 사용하는 대신 목록 (t) 클래스의 유형 별 구현을 사용하는 것이 유리합니다 ...."

기본적으로 목록 (t)은 Arraylist이지만 더 좋습니다. Arraylist의 "일반 등가"입니다. ArrayList와 마찬가지로 정렬 될 때까지 정렬되는 것은 보장되지 않습니다 (GO 그림). 목록 (t)에는 일부 기능이 추가되었습니다.

Answer 7

나는 질문에 동정합니다 - 나도 발견 한 (찾기?) 선택의 여지가 있는데, 그래서 나는 어떤 데이터 구조가 가장 빠른지를 보려고 과학적으로 설정했습니다 (VB를 사용하여 테스트를했지만 두 언어가 모두 동일하다고 생각합니다. 두 언어는 모두 동일하다고 생각합니다. CLR 수준에서 똑같은 일을하십시오). 너는 볼 수있어 여기에서 수행 한 일부 벤치마킹 결과 (어떤 상황에서 사용하기에 가장 적합한 데이터 유형에 대한 논의도 있습니다).

Answer 8

그들은 Intellisense에서 꽤 잘 설명되어 있습니다. 그냥 입력하십시오 시스템 수집. 또는 System.collections. 세대 (선호) 및 사용 가능한 내용에 대한 목록과 간단한 설명이 나타납니다.

Answer 9

해시 가능/사전은 O (1) 성능으로 성능이 크기의 함수가 아니라는 것을 의미합니다. 아는 것이 중요합니다.

편집 : 실제로 해시 가능/사전 <> 조회의 평균 시간 복잡성은 O (1)입니다.

Answer 10

제네릭 컬렉션은 특히 많은 항목을 반복 할 때 비 게 니 릭에 비해보다 나은 성능을 발휘합니다. 권투와 무역이 더 이상 발생하지 않기 때문입니다.

Answer 11

고주파 체계적인 거래 엔지니어링을위한 해시 테이블 대 사전에 대한 중요한 메모 : 스레드 안전 문제

Hashtable은 여러 스레드에서 사용하기에 안전합니다. 사전 공개 정적 멤버는 스레드 안전하지만 인스턴스 멤버는 보장되지 않습니다.

따라서 해시 테이블은 이와 관련하여 '표준'선택으로 남아 있습니다.

Answer 12

제네릭 컬렉션과 비 지성 컬렉션 사이에는 미묘하고 더 보이지 않는 차이가 있습니다. 그들은 단지 다른 기본 데이터 구조를 사용합니다. 예를 들어, HashTable은 동기화없이 한 작가-매니 리더를 보장합니다. 사전은 그렇지 않습니다.

Answer 13

사실, 나는 생각합니다 MSDN 이 모든 질문에 대한 좋은 답변을 제공하는 데 도움이됩니다. .NET 컬렉션을 찾으십시오.

Answer 14

가장 인기 있는 C# 데이터 구조 및 컬렉션

• 정렬
• 배열목록
• 목록
• 링크드리스트
• 사전
• 해시세트
• 스택
• 대기줄
• 정렬된 목록

C#.NET 예를 들어 가장 일반적인 데이터 구조 중 하나는 배열입니다.그러나 C#에는 더 많은 기본 데이터 구조가 제공됩니다.사용할 올바른 데이터 구조를 선택하는 것은 잘 구조화되고 효율적인 프로그램을 작성하는 것의 일부입니다.

이 기사에서는 C#.NET 3.5에 도입된 새로운 데이터 구조를 포함하여 기본 제공 C# 데이터 구조를 살펴보겠습니다.이러한 데이터 구조 중 다수는 다른 프로그래밍 언어에도 적용됩니다.

정렬

아마도 가장 간단하고 가장 일반적인 데이터 구조는 배열일 것입니다.C# 배열은 기본적으로 개체 목록입니다.이를 정의하는 특징은 모든 객체가 동일한 유형(대부분의 경우)이고 특정 개수가 있다는 것입니다.배열의 특성상 목록(인덱스라고도 함) 내의 위치를 ​​기반으로 요소에 매우 빠르게 액세스할 수 있습니다.C# 배열은 다음과 같이 정의됩니다.

[object type][] myArray = new [object type][number of elements]

몇 가지 예:

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

위의 예에서 볼 수 있듯이 배열은 요소 없이 또는 기존 값 집합에서 초기화될 수 있습니다.값이 맞기만 하면 배열에 값을 삽입하는 것은 간단합니다.배열의 크기보다 요소가 많아지면 배열을 확장해야 하는 경우 작업 비용이 많이 듭니다.모든 기존 요소를 더 큰 새 배열로 복사해야 하기 때문에 시간이 더 오래 걸립니다.

배열목록

C# 데이터 구조인 ArrayList는 동적 배열입니다.이것이 의미하는 바는 ArrayList가 원하는 양의 객체와 유형을 가질 수 있다는 것입니다.이 데이터 구조는 배열에 새 요소를 추가하는 프로세스를 단순화하도록 설계되었습니다.내부적으로 ArrayList는 공간이 부족할 때마다 크기가 두 배로 늘어나는 배열입니다.내부 배열의 크기를 두 배로 늘리는 것은 장기적으로 요소 복사 양을 줄이는 매우 효과적인 전략입니다.여기서는 이에 대한 증거를 다루지 않겠습니다.데이터 구조는 사용하기 매우 간단합니다.

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

ArrayList 데이터 구조의 단점은 검색된 값을 원래 유형으로 다시 캐스팅해야 한다는 것입니다.

int arrayListValue = (int)myArrayList[0]

여기에서 찾을 수 있는 출처 및 추가 정보 :

• C# 데이터 구조
• 컬렉션과 데이터 구조
• 목록 대 IEnumerable 대 IQueryable 대 ICollection 대 ​​IDictionary
• System.Collections.Generic 네임스페이스
• System.Collections 네임스페이스