Dictionary

// 빈 딕셔너리 생성
Dictionary<string, int> dictA = new Dictionary<string, int>();

// 초기 용량 설정
Dictionary<string, int> dictB = new Dictionary<string, int>(100);

https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/Dictionary.cs

• System.Collections.Generic
• 해시 테이블 기반 자료구조
• 2개의 배열
  • int[] _buckets : 각 bucket 체인의 첫 Entry 인덱스
  • Entry[] _entries : 실제 Key-Value 데이터가 저장되는 배열
    • Entry 구조체
      • int hashCode : 해시 코드
      • int next : 다음 데이터가 있는 Entry의 _entries 배열의 인덱스
        • head insertion chaining
      • TKey key
      • TValue value
  • ⇒ 충돌 체인 관리 & 캐시 친화적
• 해시 알고리즘
  • O(1)
  1. Key의 해시값 생성 (GetHashCode)
  2. bucket index 계산
  3. bucket을 통해 entries 접근
  4. 충돌 시 next 인덱스를 따라 탐색
• 시간 복잡도
  • 추가, 삭제, 탐색 : O(1) ~ O(N)
    • 인덱스 탐색이 아닌 해시 탐색이라 빠르다
  • 모든 Key가 같은 bucket이라면 O(N)
• Separate Chaining
  • 해시 충돌시 발생
  • 메모리 주소 대신 entries 배열의 인덱스 사용
  • 추가적인 객체 생성이 없기 때문에 GC 부담 적음
  • entries 배열 내부 메모리에 연속적으로 존재하기 때문에 캐시 친화적
• Rehash
  • O(N)
  • entries에 빈 공간이 없고, freeList도 없을 때 발생
  • 과정
    1. 새 capacity 선택
       • 보통 0 → 3 → 7 → 17 → 37 (두 배보다 큰 다음 소수)
    2. 새 buckets와 entries 생성
    3. 기존 entries 복사
       • entries의 순서는 변경되지 않는다.
    4. 모든 Entry의 hashCode를 이용해 bucket index를 다시 계산하여 buckets와 next 재구성
  • ⇒ 초기 용량 적절하게 지정하는 것이 좋다
    • 너무 작으면 충돌의 빈도가 증가
    • 너무 크면 메모리 낭비
• freeList와 freeCount
  • 삭제된 Entry를 재사용하기 위한 구조
  • Remove 했을 때 체인의 구조를 유지하기 위해 배열을 정리하지 않고 관리
  • freeList : 삭제된 Entry들을 next 인덱스로 연결한 free list의 시작 인덱스
  • freeCount : 현재 재사용 가능한 Entry 갯수

Dictionary 메모리 점유 지도

ex) 3번 Add + 1번 Remove 한 상황 예시

• 본체 : Dictionary<string, int>

메모리 주소	크기	변수 이름 / 역할	저장된 값
0x1000	8 Byte	Object Header	(시스템 정보)
0x1008	8	MethodTable Pointer	(타입 정보 주소)
0x1010	8	_buckets	0x2000	_buckets 배열 주소
0x1018	8	_entries	0x3000	_entries 배열 주소
0x1020	8	_comparer	(주소)	해시 비교기
0x1028	4	_count	3	사용된 Entry 갯수
0x102C	4	_version	4	변경 횟수
0x1030	4	_freeList	1	삭제된 Entry의 인덱스
0x1034	4	_freeCount	1	삭제된 Entry의 갯수

• buckets 배열 : int[] _buckets

메모리 주소	크기	변수 이름 / 역할	저장된 값
0x2000	8 Byte	Object Header	(시스템 정보)
0x2008	8	MethodTable Pointer	(타입 정보 주소)
0x2010	4	Length	3	배열 용량
0x2014	4	Padding	(빈 값)
0x2018	4	buckets[0]	2	“A”, “C”
0x201C	4	buckets[1]	-1	“B” (removed)
0x2020	4	buckets[2]	-1
0x2024	4	Padding	(빈 값)

• entries 배열 : Entry[] _entries

메모리 주소	크기	변수 이름 / 역할	저장된 값
0x3000	8 Byte	Object Header	(시스템 정보)
0x3008	8	MethodTable Pointer	(타입 정보 주소)
0x3010	4	Length	3	배열 용량
0x3014	4	Padding	(빈 값)
0x3018	24	_entries[0]		“A”
0x3030	24	_entries[1]		“B” (Removed)
0x3048	24	_entries[2]		“C”

• _entries[0] “A” : Entry

메모리 주소	크기	변수 이름 / 역할	저장된 값
0x3018	4 Byte	hashCode	hash(A)
0x301C	4	next	-1
0x3020	8	key	“A”
0x3028	4	value	1
0x302C	4	padding	(빈 값)

• _entries[1] “B” (removed) : Entry

메모리 주소	크기	변수 이름 / 역할	저장된 값
0x3030	4 Byte	hashCode	-1
0x3034	4	next	-1
0x303C	8	key	null
0x3040	4	value	0
0x3044	4	padding	(빈 값)

• _entries[2] “C” : Entry

메모리 주소	크기	변수 이름 / 역할	저장된 값
0x3048	4 Byte	hashCode	hash(C)
0x304C	4	next	0
0x3050	8	key	“C”
0x3058	4	value	3
0x305C	4	padding	(빈 값)

_count가 Count가 아니다 ?

public int Count ⇒ _count - _freeCount;

• _count = 지금까지 사용된 Entry 갯수
  • 최고 수위선 (high water mark)
  • Entry의 상태 : 사용 중 / 삭제됨(freeList) / 아직 사용 안됨
• Q. 제거할 때 _count를 줄이지 않는 이유 ?
  • ⇒ freeList로 관리하여 entries 배열을 압축하지 않고 O(1)의 삭제 성능을 유지하기 위해
• Dictionary는 배열을 압축하지 않고 삭제된 Entry를 freeList로 관리하여 재사용한다

읽으면 좋은 참조

How C# Dictionary Actually Works