HashSet

HashSet<int> hashSetA = new HashSet<int>();

HashSet<int> hashSetB = new HashSet<int>(100);

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

• System.Collections.Generic
• Dictionary에서 Key-Value Pair 구조를 버리고 하나의 Value가 해시 식별자(Key)의 역할과 저장되는 값(Value)의 역할을 동시에 수행하는 형태
• 2개의 배열
  • int[] _buckets : 각 bucket 체인의 첫 Entry 인덱스
  • Entry[] _entries : 실제 Value 데이터가 저장되는 배열
    • Entry구조체
      • int hashCode : 해시 코드
      • int next : 다음 데이터가 있는 Slot의 _slots 배열의 인덱스
        • head insertion chaining
      • T value
• 해시 알고리즘
  • O(1)
  1. Key의 해시값 생성 (GetHashCode)
  2. bucket index 계산
  3. bucket을 통해 entries 접근
  4. 충돌 시 next 인덱스를 따라 탐색
• 수학적 집합 연산
  • 해시 테이블을 사용해 빠르게
  • IntersectWith (교집합), UnionWith (합집합), ExceptWith (차집합), SymmetricExceptWith (대칭 차집합) : O(N)
• 시간 복잡도
  • 추가, 삭제, 탐색 : 평균 O(1) ~ 최악 O(N)
    • 인덱스 탐색이 아닌 해시 탐색이라 빠르다
    • 모든 Value가 같은 entry이라면 O(N)
• Add
  • hashCode 계산 → bucket index 계산 → bucket 체인 탐색 → 중복 검사 → Add → bucket 최신화
  • 중복 Add는 false 반환
    • 삽입 + 중복 검사 = O(1)

HashSet 메모리 점유 지도

본체 : HashSet

메모리 주소	크기	변수 이름 / 역할	저장된 값
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		사용된 Entry 갯수
0x102C	4	_version		수정 횟수
0x1030	4	_freeList		삭제된 Entry의 인덱스
0x1034	4	_freeCount		삭제된 Entry의 갯수