[C#] Dictionary<TKey,TValue>란 무엇인가?

System.Collections.Generic.Dictionary<TKey,TValue>에 대해 공부하다가 알게된 정보를 정리한 글입니다.
주로 어떤 원리로 작동되는 지 공부해 정리하였습니다.

Dictionary<TKey,TValue>란?

• Dictionary를 Key와 Value를 저장하는 자료구조이다
• Key를 Hash로 계산하여 빠르게 관련된 값에 접근할 수 있다
• 내부에 2가지 배열을 가지고 있다
  • int[] buckets : Hash를 통해 연결되는 Entry의 entries의 인덱스를 저장하는 배열
  • Entry[] entries : 데이터인 Entry를 저장하는 배열

Entry

• Key와 Value를 저장하는 타입
• Dictionary<TKey,TValue> 내부에서 데이터를 Entry 타입으로 저장한다
• 내부 데이터
  • key : Key값
  • value : Value값
  • next : 다음 Entry Index
  • hash : hash값

생성자

 Dictionary()

• 내부 배열은 null인 상태 (바로 배열 할딩이 이루어 지는 것은 아님)
• 첫번째 요소가 추가될 때 Initialize() 될 때 배열이 할당된다

 Dictionary(int capacity)

• capacity 이상의 소수를 크기로 가진 배열을 할당한다

 Dictionary(IDictionary<TKey, TValue> dictionary)

• dictionary 요소를 담을 수 있는 크기의 배열을 할당해 요소를 복사한다

요소 추가

• 먼저 알아야 하는 정보
  • buckets의 추가되는 순서는 일정하지 않다 (0, 9, 10, 2 이런 식으로 추가될 수 있다)
  • entries의 추가되는 순서는 일정하다 (0, 1, 2, 3, 4, 5 이런 식으로 앞에 비어있는 부분부터 추가된다)
• Key의 Hash % buckets.Length 의 결과 값을 buckets의 인덱스로 사용한다
• buckets[결과값] 의 값은 entries의 인덱스를 의미한다
  • 만약 값이 -1이면 Hash충돌이 없는 상태이고 0이상이면 같은 Hash를 가진 Entry를 가르키는 것(Hash충돌)이다
• entries에 같은 Key를 가진 요소가 있다면 Value만 바꿔준다
• 같은 Key를 가진 요소가 없다면 entries에 요소를 추가하고 인덱스를 buckets 값에 저장한다
  • Hash충돌이 없는 경우는 추가된 Entry.next가 -1이지만 Hash충돌이 있는 경우 기존에 가르키고 있던 Entry 인덱스를 저장한다
  • 연결리스트와 비슷하다고 생각하면 된다
• 추가하기 전에 entries의 여유 공간이 없을 경우 Resize() 한다
• 순회한 횟수를 확인했을 때 일정 횟수 이상이면 Resize() 한다
  • Hash충돌이 많다면 성능이 저하되기 때문에

요소 제거

• buckets[Hash] 값이 -1이면 Hash가 같은 Entry가 없으므로 false 반환
• 0 이상이면 Entry.next를 순회하면서 같은 Key를 가진 Entry를 탐색
  • 찾았으면 해당 Entry를 기본값으로 초기화
  • Entry가 next를 가르키고 있는 경우 이전 Entry가 가르키도록 변경

Resize

• 더 큰 크기를 가진 배열을 할당해 요소들을 복사 후 참조한다
• 크기는 단순 2배가 아닌 2배보다 큰 소수를 선택해 크기를 정한다
• 이 과정을 통해 더 많은 요소를 저장할 수 있고 Hash충돌도 적어질 가능성이 높다

왜 소수인가?

• 소수를 선택한 경우가 소수를 선택하지 않는 경우보다 요소들이 균등하게 분포되기 때문이다

내부 배열에 변경이 생겼을 때

• Clear, Insert, Remove 등등
• version이 올라감
• version은 Enumerator를 사용할 때 유효성 검사 목적으로 사용됨

출처

• Microsoft 공식 문서
• Microsoft Reference Source

---

💻 열심히 공부해서 작성 중이니 오류나 틀린 부분이 있을 경우 
  언제든지 댓글 혹은 메일로 알려주시면 감사하겠습니다! 😸

맨 위로 이동하기

CSharp 카테고리 내 다른 글 보러가기